LinkedHashMap
extends HashMap<K,V> implements Map<K,V>
LinkedHashMap继承了HashMap,通过重写HashMap的插入访问的后置方法,实现了可以按照访问顺序排序的容器
-
容器实体
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
* 变成了双向链表
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
用途
LRU(Least Recent Used)
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// 设置accessOrder为true,这样在get()时也会改变元素顺序,使之成为最近访问的。
super(capacity, 0.75f, true);
this.capacity = capacity;
}
// 每次添加的后置处理
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
public static void main(String[] args) {
LRUCache<Integer, String> lru = new LRUCache<>(5);
lru.put(1, "one");
lru.put(2, "two");
lru.put(3, "three");
lru.put(4, "four");
lru.put(5, "five");
System.out.println(lru.get(2)); // Outputs: "two"
lru.put(6, "six"); // This will remove the key "1" from the cache because of the capacity limit.
System.out.println(lru.get(1)); // Outputs: null
}
}
LRU的实现
//将被访问的节点放到最后
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;
}
}