LinkedHashMap源码及LRU实现原理

基本认识

LinkedHashMap位于java.util包，于JDK1.4引入，属于Java Collections Framework的成员。查看其UML关系如下图所示：
HashMap在很多场景下都满足K-V的存取，而且在非多线程的场景下也能保持不错的性能，但是HashMap有一个缺点就是不能保证元素的顺序，相比之下，LinkedHashMap就满足了这点，可以保证元素的插入顺序。
LinkedHashMap的数据结构实现如下图所示：
LinkedHashMap也是Java中多态思想的一个重要运用，其底层实现可以看作是HashMap和LinkedList的结合，使用HashMap来存储数据，使用LinkedList来维护链表的顺序，一定程度上也增加了时间和空间的消耗。

源码解析

相关变量

在LinkedHashMap中有一个重要的成员变量，用来标志元素的排序规则，默认为false。

/**
 * 双向链表的头部(最老的)。
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 双向链表的尾部(最小的)。
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 用来指定LinkedHashMap的迭代排序方法：访问顺序为true ，插入顺序为false。
 */
final boolean accessOrder;

LinkedHashMap中的节点继承自HashMap.Node，采用的是双向链表的结构，因此支持双向遍历。

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共有5个构造方法，在不指定成员变量accessOrder作为构造入参时，都被显式的声明为false，这也说明了在默认情况下，LinkedHashMap是按照插入顺序进行排序。
由于继承自HashMap，因此构造方法入参也可以指定初始容量initialCapacity和加载因子loadFactor。

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

public LinkedHashMap() {
    super();
    accessOrder = false;
}

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

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

实现原理

HashMap的底层数据结构为哈希表，这种结构的特点为数组+链表或者是数组＋红黑树的结构，初始化容量指定的为数组的容量，每一个数组的下标位置被称为一个bucket，每个bucket处的头节点之后为链表或者红黑树，在进行元素查找时可以达到O(1)、O(logN)、O(N)的时间复杂度，具有较高的性能。
LinkedHashMap在添加元素时直接调用的时HashMap的put实现，在HashMap中预留了对节点的后置操作回调函数，如下所示：

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }

查看HashMap中put方法的源码实现：

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // ......省略片段
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
    	// ......省略片段
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 对链表的节点进行后置增强操作
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 在节点插入之后所做的操作，HashMap中该方法未有任何实现，在LinkedashMap中
    // 实现了该方法，用于处理节点添加后的后置操作，evict该参数默认为true，是否驱逐节点
    afterNodeInsertion(evict);
    return null;
}

// HashMap在链表操作中调用了afterNodeAccess方法，用来在添加元素节点后进行，节点顺序排列
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果accessOrder为true并且当前元素不是链表的尾结点，将当前节点移动至链表尾部
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // ......省略片段，链表操作
    }
}

查看afterNodeInsertion方法的实现，源码如下：

// 该方法的作用是在新的元素插入后，可能会移除旧的节点
// 因此LinkedHashMap很适合用来做LRU Cache
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
	// evict默认为true，removeEldestEntry在LinkedHashMap中的实现默认为false
    // 在LinkedHashMap中默认不会移除，但是预留了扩展来实现缓存淘汰方案
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // 移除添加时间最久的节点
        removeNode(hash(key), key, null, false, true);
    }
}

// 该方法是一个可以被继承实现的方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

关于节点的删除操作，查看removeNode方法的具体实现

// 移除节点 movable为true,matchValue为false
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        //......省略
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            //......省略
            // LinkedHashMap实现，移除节点后的回调函数
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

查看节点移除后的后置操作

// 移除节点后
void afterNodeRemoval(Node<K,V> e) { // unlink
    // 临时节点p记录当前节点，a指向p的后一个节点，b指向p的前一个节点
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 当前节点移除后，p的前一个、后一个节点都指向null
    p.before = p.after = null;
    
    // 处理head指向
    // 如果前一个结点为null，当前节点被移除，所以head指向当前节点的后一个节点
    if (b == null)
        head = a;
    else
        // 如果前一个节点不为null，当前节点被移除后，当前节点上一个节点指向下一个节点即可
        b.after = a;
    
    // 处理tail指向
    // 如果当前节点的下一个节点为null，说明当前节点为头节点，当前节点被移除，tail指向下一个
    if (a == null)
        tail = b;
    else
        // 当前节点的下一个节点不为null，直接进行节点追加
        a.before = b;
}

LRU实现

在操作系统中，物理内存不可能同时加载所需的所有数据页，只能加载正在或最近要使用的内存页，这也就伴随着页面的更换，页面更换的目标是，尽量替换掉不再使用或者一段时间内不再使用的内存页，要不然会很容易触发缺页中断，该操作代价较大，涉及到从磁盘加载，因此页面更换可不是随便的事情。在内存不够的场景下，会进行内存淘汰的机制，随之也出现了各种淘汰算法，大致可以分为以下两大类：

• 公平算法：随机算法、FIFO算法、时钟算法。
• 非公平算法：NRU算法、LRU算法、工作集算法。

LRU即Least Recently Used，最近最少使用算法，当缓存满了，会优先淘汰那些最近最不常访问的数据。在Java中利用LinkedHashMap可以很容易的实现LRU，在一些开源软件方案中也随处可见基于LinkedHashMap实现的LRU方案，如下面两个代码案例：

/**
 * MySQL Driver LRU实现
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    protected int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        this.maxElements = maxSize;
    }

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return this.size() > this.maxElements;
    }
}

/**
 * Druid LRU实现
 */
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    private final int maxSize;

    public LRUCache(int maxSize) {
        this(maxSize, 16, 0.75F, false);
    }

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

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        return this.size() > this.maxSize;
    }
}

以上代码可以看出，实现的代码大同小异。下面使用具体案例来演示使用的过程：

import java.util.LinkedHashMap;
import java.util.Map.Entry;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private static final long serialVersionUID = 1L;
    protected int maxElements;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75F, true);
        this.maxElements = maxSize;
    }

    protected boolean removeEldestEntry(Entry<K, V> eldest) {
        // 当HashMap的size大于预设的最大容纳元素数量maxElements时移除旧的元素
        return this.size() > this.maxElements;
    }
    
    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);
        cache.put("k1", 1);
        cache.put("k2", 2);
        cache.put("k3", 3);
        print(cache);

        cache.get("k3");
        cache.get("k2");
        cache.get("k1");
        print(cache);

        cache.put("k4",4);
        print(cache);
    }

    public static void print(LRUCache<String, Integer> cache) {
        cache.forEach((k, v) -> System.out.println(k + " : " + v));
    }
}

输出结果：

k1 : 1
k2 : 2
k3 : 3
    
k3 : 3
k2 : 2
k1 : 1
    
k2 : 2
k1 : 1
k4 : 4

可以看到Cache中最大容纳元素数量为设定数量3，超过3的元素会被丢弃，缓存中的数据也是按照访问顺序进行排序，访问顺序包含put、get两种操作。其工作原理如下图所示：

总结

• HashMap利用哈希表进行数据存取，其底层实现结构为数组+链表或者数组+红黑树，LinkedHashMap在使用HashMap进行数据存储的过程中，又维护了一个双向链表来维持顺序，通过accessOrder支持链表的双向遍历。
• 基于LinkedHashMap可以巧妙的实现缓存LRU。既可以按照访问顺序，也可以按照插入顺序进行数据的淘汰。
• 相比HashMap的访问操作，put、get方法，LinkedHashMap在进行元素访问后都会调用回调函数afterNodeAccess进行元素排序操作，在put元素后还会额外调用afterNodeInsertion回调方法进行后续操作，并且根据removeEldestEntry方法的返回结果判定是否进行旧元素移除，默认不进行删除。