LinkedHashMap – 双向链表实现 LRU 的有序性

在不涉及线程安全的情况下，HashMap 在一般情况基本上都比较适用，但是有一个问题：HashMap 进行 forEach 迭代的顺序是无序的（也就是不是放进去的顺序或者访问的顺序）。LinkedHashMap 正是为了这种场景诞生的。

核心：在 Map.Entry 之间维护双向链表，保证插入的元素维护了插入的先后顺序或者访问的顺序。

LinkedHashMap 基本结构

继承结构

LinkedHashMap 是 HashMap 的子类，在 HashMap 基础上用 LinkedList 维护插入元素的先后顺序

public class LinkedHashMap<K,V>  
    extends HashMap<K,V>  
    implements Map<K,V>

Map.Entry 实现

先看 HashMap 中对于每个 Map.Entry<K,V> 的实现：

static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  
    final K key;  
    V value;  
    Node<K,V> next;
    ...
}

再看 LinkedHashMap 中对其的实现：

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

可以看出，LinkedHashMap 中的 Entry 重写了 HashMap 中的 Node，在其基础之上提供了指向 before 节点和 after 节点的路径，实际上构成了一个双向链表的结构。这个设计很类似于大名鼎鼎的 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;  

/**  
 * The iteration ordering method for this linked hash map: <tt>true</tt>  
 * for access-order, <tt>false</tt> for insertion-order.  
 * * @serial  
 */  
final boolean accessOrder;

维护头节点和尾节点，方便于后续插入新节点以及按顺序遍历
通过 accessOrder 提供两种顺序模式：插入顺序（insertion-order）、访问顺序（access-order），这一点的具体作用在 get() 方法中体现。

Map 核心方法 put & get

put() 如何保持顺序？

LinkedHashMap 并没有重写 HashMap 的 put() 方法，也就是操作完全一样。保证顺序的精髓在于多态的思想：

HashMap.put() 中通过调用 newNode() 来创建新节点，在 LinkedHashMap 中重写了这个方法：

// HashMap
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {  
    return new Node<>(hash, key, value, next);  
}

// LinkedHashMap
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {  
    LinkedHashMap.Entry<K,V> p =  
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);  
    linkNodeLast(p);  
    return p;  
}

// link at the end of list  
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {  
    LinkedHashMap.Entry<K,V> last = tail;  
    tail = p;  
    if (last == null)  
        head = p;  
    else {  
        p.before = last;  
        last.after = p;  
    }  
}

可以看出，创建新的 Entry 的方式沿用 HashMap，通过调用 linkNodeLast() 方法来将新节点接到链尾，这和无哨兵的 LRU 的思路是完全一致的。

get() 在读取中维护 LRU 关系

接下来，让我们看一下 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;  
 }

通过核心字段 accessOrder 判断顺序模式，如果是访问顺序，就需要将访问的节点放到链表尾的位置，在 afterNodeAccess() 中实现：

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

这段代码核心就是在没有哨兵的情况下进行的节点向链表尾的移动，不再详细解释。

扩展：LRUCache

从上文中看出，LinkedHashMap 实际上就是在 HashMap 中融入了一个 最近最久未使用（LRU） 的缓存排序思想。实际上，很多组件依赖的 LRUCache 类的实现就是基于 LinkedHashMap 。比如下面是一个提供的构造方法：

public LRUCache(int maxSize) {  
    // true 表示的就是 accessOrder， 设置为访问顺序
    super(maxSize, 0.75F, true);  
    this.maxElements = maxSize;  
}