1 引言

HashMap 的遍历顺序与插入顺序不一定是一致的，LinkedHashMap 继承了 HashMap，扩展了一些功能，用于维护插入顺序。

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

与 TreeMap 对比，他们相同的地方在于都可以维护 key 的顺序，只是 LinkedHashMap 底层是基于双向链表来实现顺序，TreeMap 是基于红黑树来实现。

LinkedHashMap 与 HashMap 基本操作和原理相似，主要区别在于插入、覆盖、删除的时候，会使用双向链表来记录 key-value 对的顺序，在遍历的时候按照这个顺序来遍历。

2 核心属性

// 双向链表头节点, 旧数据存在头节点。
transient LinkedHashMap.Entry<K,V> head;

// 双向链表尾节点，新数据存在尾节点。
transient LinkedHashMap.Entry<K,V> tail;

// 是否按访问顺序排序，如果为false则按插入顺序存储元素，如果是true则按访问顺序存储元素。
final boolean accessOrder;

3 核心原理

3.1 put

在调用 LinkedHashMap 的 put() 方法的时候，一定会调用到 HashMap 的 put() 方法里面去，调用完 put() 方法，插入一个 key-value 对之后，其实就会调用 afterNodeInsertion(evict)，这个方法就会去回调 LinkedHahsMap 里面的子类的实现。

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

evict 只有在构建 Map 的时候才为 false，在这里为 true。

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

另外还有一个子类实现 afterNodeAccess(Node<K,V> e) 方法：

当一个节点被访问时，如果 accessOrder 为 true，则会将该节点移到链表尾部。也就是说指定为 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;
    }
}

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

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

3.2 accessOrder

覆盖，如果是你再次将某个key的值覆盖一下，会怎么样呢？

LinkedHashMap 有一个带参的构造函数：

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

accessOrder，默认是false，此时访问这个元素，并不会改变顺序。

但是如果accessOrder是true的话，那么 get 一个 key，或者是覆盖这个 key 的值，就会导致个 key-value 对顺序会在链表里改变，它会被挪动到链表的尾部去。

3.3 总结

• LinkedHashMap继承自HashMap，具有HashMap的所有特性；
• LinkedHashMap内部维护了一个双向链表存储所有的元素；
• 如果accessOrder为false，则可以按插入元素的顺序遍历元素；
• 如果accessOrder为true，则可以按访问元素的顺序遍历元素；
• LinkedHashMap的实现非常精妙，很多方法都是在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法；
• 默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略；
• LinkedHashMap可以用来实现LRU缓存淘汰策略；

4 使用 LinkedHashMap 实现 LRU

class LRU<K, V> extends LinkedHashMap<K, V> {

        private int capacity;

        public LRU(int capacity, float loadFactor) {
            super(capacity, loadFactor, true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > capacity;
        }
}