Map 大家族的那点事儿 ( 6 ) ：LinkedHashMap详解编程语言

LinkedHashMap继承HashMap并实现了Map接口，同时具有可预测的迭代顺序（按照插入顺序排序）。它与HashMap的不同之处在于，维护了一条贯穿其全部Entry的双向链表（因为额外维护了链表的关系，性能上要略差于HashMap，不过集合视图的遍历时间与元素数量成正比，而HashMap是与buckets数组的长度成正比的），可以认为它是散列表与链表的结合。

/** 
 * 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; 
/** 
 * 迭代顺序模式的标记位，如果为true，采用访问排序，否则，采用插入顺序 
 * 默认插入顺序（构造函数中默认设置为false） 
 */ 
final boolean accessOrder; 
/** 
 * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance 
 * with the default initial capacity (16) and load factor (0.75). 
 */ 
public LinkedHashMap() { 
    super(); 
    accessOrder = false; 
}

LinkedHashMap的Entry实现也继承自HashMap，只不过多了指向前后的两个指针。

/** 
 * HashMap.Node subclass for normal LinkedHashMap entries. 
 */ 
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); 
    } 
}

你也可以通过构造函数来构造一个迭代顺序为访问顺序（accessOrder设为true）的LinkedHashMap，这个访问顺序指的是按照最近被访问的Entry的顺序进行排序（从最近最少访问到最近最多访问）。基于这点可以简单实现一个采用LRU（Least Recently Used）策略的缓存。

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

LinkedHashMap复用了HashMap的大部分代码，所以它的查找实现是非常简单的，唯一稍微复杂点的操作是保证访问顺序。

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

还记得这些afterNodeXXXX命名格式的函数吗？我们之前已经在HashMap中见识过了，这些函数在HashMap中只是一个空实现，是专门用来让LinkedHashMap重写实现的hook函数。

   // 在HashMap.removeNode()的末尾处调用 
   // 将e从LinkedHashMap的双向链表中删除 
   void afterNodeRemoval(Node<K,V> e) { // unlink 
       LinkedHashMap.Entry<K,V> p = 
           (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; 
       p.before = p.after = null; 
       if (b == null) 
           head = a; 
       else 
           b.after = a; 
       if (a == null) 
           tail = b; 
       else 
           a.before = b; 
   } 
   // 在HashMap.putVal()的末尾处调用 
   // evict是一个模式标记，如果为false代表buckets数组处于创建模式 
   // HashMap.put()函数对此标记设置为true 
   void afterNodeInsertion(boolean evict) { // possibly remove eldest 
       LinkedHashMap.Entry<K,V> first; 
       // LinkedHashMap.removeEldestEntry()永远返回false 
       // 避免了最年长元素被删除的可能（就像一个普通的Map一样） 
       if (evict && (first = head) != null && removeEldestEntry(first)) { 
           K key = first.key; 
           removeNode(hash(key), key, null, false, true); 
       } 
   } 
   // HashMap.get()没有调用此函数，所以LinkedHashMap重写了get() 
// get()与put()都会调用afterNodeAccess()来保证访问顺序 
   // 将e移动到tail，代表最近访问到的节点 
   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，这时它的行为与普通的Map无异。如果你把removeEldestEntry()重写为永远返回true，那么就有可能使LinkedHashMap处于一个永远为空的状态（每次put()或者putAll()都会删除头节点）。

一个比较合理的实现示例：

protected boolean removeEldestEntry(Map.Entry eldest){ 
    return size() > MAX_SIZE; 
}

LinkedHashMap重写了newNode()等函数，以初始化或连接节点到它内部的双向链表：

// 链接节点p到链表尾部（或初始化链表） 
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; 
    } 
} 
// 用dst替换掉src 
private void transferLinks(LinkedHashMap.Entry<K,V> src, 
                           LinkedHashMap.Entry<K,V> dst) { 
    LinkedHashMap.Entry<K,V> b = dst.before = src.before; 
    LinkedHashMap.Entry<K,V> a = dst.after = src.after; 
    // src是头节点 
    if (b == null) 
        head = dst; 
    else 
        b.after = dst; 
    // src是尾节点 
    if (a == null) 
        tail = dst; 
    else 
        a.before = dst; 
}    
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; 
} 
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { 
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; 
    LinkedHashMap.Entry<K,V> t = 
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next); 
    transferLinks(q, t); 
    return t; 
} 
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { 
    TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); 
    linkNodeLast(p); 
    return p; 
} 
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { 
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; 
    TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); 
    transferLinks(q, t); 
    return t; 
}

遍历LinkedHashMap所需要的时间与Entry数量成正比，这是因为迭代器直接对双向链表进行迭代，而链表中只会含有Entry节点。迭代的顺序是从头节点开始一直到尾节点，插入操作会将新节点链接到尾部，所以保证了插入顺序，而访问顺序会通过afterNodeAccess()来保证，访问次数越多的节点越接近尾部。

abstract class LinkedHashIterator { 
    LinkedHashMap.Entry<K,V> next; 
    LinkedHashMap.Entry<K,V> current; 
    int expectedModCount; 
    LinkedHashIterator() { 
        next = head; 
        expectedModCount = modCount; 
        current = null; 
    } 
    public final boolean hasNext() { 
        return next != null; 
    } 
    final LinkedHashMap.Entry<K,V> nextNode() { 
        LinkedHashMap.Entry<K,V> e = next; 
        if (modCount != expectedModCount) 
            throw new ConcurrentModificationException(); 
        if (e == null) 
            throw new NoSuchElementException(); 
        current = e; 
        next = e.after; 
        return e; 
    } 
    public final void remove() { 
        Node<K,V> p = current; 
        if (p == null) 
            throw new IllegalStateException(); 
        if (modCount != expectedModCount) 
            throw new ConcurrentModificationException(); 
        current = null; 
        K key = p.key; 
        removeNode(hash(key), key, null, false, false); 
        expectedModCount = modCount; 
    } 
} 
final class LinkedKeyIterator extends LinkedHashIterator 
    implements Iterator<K> { 
    public final K next() { return nextNode().getKey(); } 
} 
final class LinkedValueIterator extends LinkedHashIterator 
    implements Iterator<V> { 
    public final V next() { return nextNode().value; } 
} 
final class LinkedEntryIterator extends LinkedHashIterator 
    implements Iterator<Map.Entry<K,V>> { 
    public final Map.Entry<K,V> next() { return nextNode(); } 
}