LinkedHashMap

内部结构

内部维护了一个双向链表,用来维护插入顺序或者 LRU 顺序。

/**
* 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;

accessOrder

accessOrder决定了顺序，默认为false，此时维护的是插入顺序。
如果设置为true,那么维护的就是 LRU 顺序

afterNodeAccess()

当一一个节点被访问时,如果 accessOrder 为 true,则会将该节点移到链表尾部。也就是说指定为 LRU 顺序之后,在每次访问一个节点时,会将这个节点移到链表尾部,保证链表尾部是最近访问的节点,那 么链表首部就是最近最久未使用的节点。

afterNodeInsertion()

在 put 等操作之后执行,当 removeEldestEntry() 方法返回 true 时会移除最晚的节点,也就是链表首部 节点 first。

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);
    }
}

removeEldestEntry() 默认为 false,如果需要让它为 true,需要继承 LinkedHashMap 并且覆盖这个方 法的实现,这在实现 LRU 的缓存中特别有用,通过移除最近最久未使用的节点,从而保证缓存空间足 够,并且缓存的数据都是热点数据。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

例子

以下是使用 LinkedHashMap 实现的一个 LRU 缓存:

• 设定最大缓存空间 MAX_ENTRIES 为 3;
• 使用用 LinkedHashMap 的构造函数将 accessOrder 设置为 true,开启 LRU 顺序;
• 覆盖 removeEldestEntry() 方法实现,在节点多于 MAX_ENTRIES 就会将最近最久未使用的数据移 除。 ```java class LRUCache extends LinkedHashMap { private static final int MAX_ENTRIES = 3; protected boolean removeEldestEntry(Map.Entry eldest) {

    return size() > MAX_ENTRIES;

  } }

LRUCache() {super(MAX_ENTRIES, 0.75f, true);}

public static void main(String[] args) { LRUCache cache = new LRUCache<>(); cache.put(1, “a”); cache.put(2, “b”); cache.put(3, “c”); cache.get(1); cache.put(4, “d”); System.out.println(cache.keySet()); } // [3, 1, 4] ```