LinkedHashMap实现LRU缓存
LinkedHashMap实现LRU缓存
最近在面试的过程中，遇到了需要设计能实现LRU缓存的数据结构。不考虑时间复杂度，可以使用LinkedList实现，但是缓存需要考虑时间复杂度，所以，需要再加上HashMap的结构，这样就能实现增、查的时间复杂度都是O(1)。
JDK的集合框架中正好提供了一个这样的数据结构：LinkedHashMap，它继承了HashMap。在HashMap中有三个方法是没有实现的：
- afterNodeAccess：访问节点之后调用的方法
- afterNodeInsertion：插入节点之后调用的方法
- afterNodeRemoval：删除节点之后调用的方法
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { } //访问节点之后调用的方法
void afterNodeInsertion(boolean evict) { } //插入节点之后调用的方法
void afterNodeRemoval(Node<K,V> p) { } //删除节点之后调用的方法
这三个方法都是在put、get、remove方法中回调的方法。在学习HashMap的时候，我并没有注意到这三个方法，现在才知道他们的重要性，目前这三个方法只在LinkedHashMap中实现了。
LinkedHashMap默认是按照节点的插入顺序，即先进先出，但是通过实例化时设置参数(AccessOrder = true)，可以修改为按访问顺序进出。
LRU：最近最少访问，实现原理是：
- 当访问元素时，先在HashMap中找到该节点，再将该节点移动到链表的末尾；
- 当添加元素时，先在HashMap中定位，将节点插入到HashMap中，同时将节点插入到链表的末尾；
- 因为缓存是有大小的，如果插入的节点数目超过了缓存大小，就需要删除最近最少使用的节点，即在HashMap中删除节点，同时删除链表的表头节点；
1，afterNodeAccess(Node<K,V> p) { } //访问节点之后调用的方法
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
看过HashMap源码的同学应该知道，这个方法在put方法中被调用，具体是在当put()是更新操作时，即put的key已经存在。这个方法的具体作用就是：在对节点进行访问之后，会更新链表，将节点移动到链表的尾部，表示最近被访问过。细心的同学会问，那调用get方法进行访问的时候，该怎么办呢？是的，因为HashMap的get方法并没有回调这个方法，所以LInkedHashMap自己实现了get方法（下面介绍）。
2，afterNodeInsertion(boolean evict) { } //插入节点之后调用的方法
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
这个方法是在HashMap中的put方法中被调用，具体是当put方法是添加操作时，即put的key不存在。这个方法的具体作用是：在插入新节点后，因为缓存不够，需要删除最近最少使用的节点。
这里的删除操作还是HashMap中实现的removeNode方法，只是在removeNode方法中调用了 afterNodeRemoval方法（下面介绍）。这里需要用户实现removeEldestEntry(first)方法，即如果需要进行删除的话，将这个方法重写。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
这个方法默认是返回false，即不进行删除操作。用户如果需要的话，就可以重写该方法，根据自己的条件返回true即可，比如return size() > cacheSize。
3，afterNodeRemoval(Node<K,V> p) { } //删除节点之后调用的方法
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
因为在HashMap的removeNode方法中，只是删除了HashMap中的节点，并没有在链表中删除。所以在removeNode中，回调了这个方法，将该节点从链表中删除（这里是删除的头结点，因为头结点是最早进入或者最近最久未使用的）。
get和put方法
LinkedHashMap自己并没有重写put方法，上面已经介绍过。但是为了访问，所以LinkedHashMap自己实现了get方法：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
这里的getNode()方法是HashMap中的方法，这里只是多了一个判断：if(accessOrder)，即如果需要按照访问顺序进行迭代，就调用afterNodeAccess方法，将节点移动到链表的末尾。
containsValue方法有改进
在LinkedHashMap中，containsValue时间复杂度更低，因为使用了链表，所以时间复杂度只有O(n)，而HashMap中使用了双重循环。
/**
*LinkedHashMap中
*/
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
/**
* HashMap中
*/
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
代码实现LRU1：类似内部类
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by on 19-4-13
*/
public class LRUCache2 {
public static void main(String[] args) {
final int cacheSize = 3;
Map<String, Integer> map = new LinkedHashMap<String, Integer>((int) Math.ceil(cacheSize / 0.75f) + 1,
0.75f, true){
@Override
protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
return size() > cacheSize;
}
@Override
public String toString() {
for (Map.Entry<String, Integer> map : entrySet()){
System.out.print(String.format("%s:%s ", map.getKey(), map.getValue()));
}
System.out.println();
return null;
}
};
map.put("政治", 5);
map.put("语文", 1);
map.put("英文", 3);
System.out.println(map.toString());
map.get("政治");
map.put("地理", 6);
System.out.println(map.toString());
}
}
运行结果：
LRU实现2：标准实现
import java.util.LinkedHashMap;
import java.util.Map;
/**
* Created by on 19-4-12
*/
public class LRUCache<K, V> extends LinkedHashMap<K, V>{
private final int MAX_CACHE_SIZE;
public LRUCache(int cacheSize){
super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
MAX_CACHE_SIZE = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > MAX_CACHE_SIZE;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for(Map.Entry<K, V> entry : entrySet()){
sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue()));
}
return sb.toString();
}
public static void main(String[] args) {
LRUCache<String, Integer> lruCache = new LRUCache<>(3);
lruCache.put("政治", 5);
lruCache.put("语文", 1);
lruCache.put("英文", 3);
System.out.println(lruCache.toString());
lruCache.get("政治");
lruCache.put("地理", 6);
System.out.println(lruCache.toString());
}
}
运行结果：