LinkedHashMap源码解析

一 成员变量解析

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

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

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

/**
 * true按访问排序 false按插入排序
 */
final boolean accessOrder;

二 关键方法解析

1 添加元素

//该方法继承于HashMap，LinkedHashMap只重写了newNode()和afterNodeAccess()
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)
        // LinkedHashMap重写newNode()方法
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // LinkedHashMap重写该方法
            // 如果key对应的entry存在，按访问更新链表顺序
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

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

// 将节点插入链表尾部，保证插入的顺序不变
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // 如果尾部为null 则将p设为头部
    if (last == null)
        head = p;
    else {
        // 如果last不为null 则将p放到last后面，至此p为尾部节点
        p.before = last;
        last.after = p;
    }
}

// LinkedHashMap将此函数重写，用于当访问某一节点后，将该节点放到尾部
// 所以最近最少访问的节点在头部，最频繁访问的节点在尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // 若accessOrder为true且节点e不是尾节点，则设置e为tail节点 
    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;
    }
}

2 获取元素

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    // 若accessOrder为true，则将访问的节点放入链表尾部
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

LinkedHashMap 继承了 HashMap，是 HashMap 的子类，所以其他方法和 HashMap 基本相同，在此不必赘述

三 LinkedHashMap可以实现LRU缓存调度算法

前面讲了LinkedHashMap添加元素，删除、修改元素就不说了，比较简单，和HashMap+LinkedList的删除、修改元素大同小异，下面讲一个新的内容。
LinkedHashMap可以用来作缓存，比方说LRUCache，看一下这个类的代码，很简单，就十几行而已：

public class LRUCache extends LinkedHashMap {
    public LRUCache(int maxSize)
    {
        super(maxSize, 0.75F, true);
        maxElements = maxSize;
    }
 
    protected boolean removeEldestEntry(java.util.Map.Entry eldest)
    {
        return size() > maxElements;
    }
 
    private static final long serialVersionUID = 1L;
    protected int maxElements;
}

LinkedHashMap 可以实现LRU算法的缓存基于两点：

1. LinkedList 首先它是一个 Map，Map是基于K-V的，和缓存一致
2. LinkedList 提供了一个 boolean 值可以让用户指定是否实现LRU
   那么，首先我们了解一下什么是LRU：LRU即Least Recently Used，最近最少使用，也就是说，当缓存满了，会优先淘汰那些最近最不常访问的数据。比方说数据a，1天前访问了；数据b，2天前访问了，缓存满了，优先会淘汰数据b。
   我们看一下LinkedList带boolean型参数的构造方法：

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

就是这个accessOrder，它表示：
（1）false，所有的Entry按照插入的顺序排列
（2）true，所有的Entry按照访问的顺序排列
第二点的意思就是，如果有1，2，3这3个Entry，那么访问了1，就把1移到尾部去，即2，3，1。每次访问都把访问的那个数据移到双向队列的尾部去，那么每次要淘汰数据的时候，双向队列最头的那个数据不就是最不常访问的那个数据了吗？换句话说，双向链表最头的那个数据就是要淘汰的数据。
“访问”，这个词有两层意思：
（1）根据Key拿到Value，也就是get方法
（2）修改Key对应的Value，也就是put方法