LinkedHashMap源码分析

简介

LinkedHashMap可以看错成HashMap+LinkedList
LinkedHashMap内部维护了一个双向链表，能保证元素按插入的顺序访问，也能以访问顺序访问，可以实现LRU缓存策略

LinkedHashMap继承体系

属性

/**
 * 双向链表头节点
 */
transient LinkedHashMap.Entry<K,V> head;

/**
 * 双向链表尾节点
 */
transient LinkedHashMap.Entry<K,V> tail;

/**
 * 是否按访问顺序排序
 */
final boolean accessOrder;

内部类

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

构造函数

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

afterNodeInsertion

在节点插入之后做些什么，在HashMap中的putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。

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);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

evict，驱逐的意思。
如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；
HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；
默认removeEldestEntry()方法返回false，也就是不删除元素

afterNodeAccess

在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 如果accessOrder为true，并且访问的节点不是尾节点
    if (accessOrder && (last = tail) != e) {
        // 定义当前节点p
        // 当前节点前一个节点b
        // 当前节点后一个节点a
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // 把p节点从双向链表中移除
        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;
        }
        // 尾节点等于p
        tail = p;
        ++modCount;
    }
}

如果accessOrder为true，并且访问的节点不是尾节点；
拿到当前节点，当前的上一节点和当前的下一节点；
当前的上一节点为空，那么这个节点是首节点，设置首节点为当前的下一节点；
当前的上一节点不为空，那么就设置上一节点的next为当前节点的下一个节点；
当前的下一节点为空的，那么这个节点是尾节点，设置当前节点的上一节点为尾节点；
当前的下一节点不为空，那么久设置下一节点的pre为当前节点的上一节点；

afterNodeRemoval

在节点被删除之后调用的方法。

void afterNodeRemoval(Node<K,V> e) { // unlink
    // 当前节点p
    // 上一节点b
    // 下一节点a
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 设置当前节点前后置空，协助GC
    p.before = p.after = null;
    // 删除的是首节点，设置当前下一节点为首节点
    if (b == null)
        head = a;
    else
        // 设置上一节点的next为下一节点
        b.after = a;
    // 删除的是尾节点，把上一节点设置为尾节点
    if (a == null)
        tail = b;
    else
        // 不是尾节点，设置上一节点的后一节点为尾节点
        a.before = b;
}

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为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。

总结

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

基于LinkedHashMap的LRU

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

public class LRUTest {
    public static void main(String[] args) {
        // 创建一个只有5个元素的缓存
        LRU<Integer, Integer> lru = new LRU<>(5, 0.75f);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.put(5, 5);
        lru.put(6, 6);
        lru.put(7, 7);

        System.out.println(lru.get(4));

        lru.put(6, 666);

        // 输出: {3=3, 5=5, 7=7, 4=4, 6=666}
        // 可以看到最旧的元素被删除了
        // 且最近访问的4被移到了后面
        System.out.println(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;
    }

    /**
    * 重写removeEldestEntry()方法设置何时移除旧元素
    * @param eldest
    * @return
    */
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        // 当元素个数大于了缓存的容量, 就移除元素
        return size() > this.capacity;
    }
}

简介