Map (二)：LinkedHashMap 解析

写在前面

由于个人水平有限，故部分内容可能会出现错误，还请包涵

LinkedHashMap

1
2
3

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

LinkedHashMap 在 HashMap 的基础上，通过一个双向链表来维护 Map 中节点的顺序，在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序

LinkedHashMap 内存放的节点元素定义如下

// next 用于维护 HashMap 各个桶中 Entry 的连接顺序
// before、after 用于维护 Entry 插入的先后顺序
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);
        
    }
    
}

同时类中有两个属性 head 和 tail，分别指向内部双向链表的头和尾

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

默认情况，遍历时的顺序是按照插入节点的顺序。这也是其与 HashMap（HashMap 遍历的方式是按数组的方式依次遍历 table 中的元素，然后再以链表或红黑树的方式遍历 table 中的单个元素）最大的区别

也可以在构造时传入 accessOrder (值为 true 时，表示按照访问顺序迭代；值为 false 时，表示按照插入顺序迭代)参数，使得其遍历顺序按照访问的顺序输出，默认为 false

LinkedHashMap 的一个重要应用就是实现 LRU（Least Recently Used）算法，是一种缓存技术，在 LRU 算法中，会将 accessOrder 设为 true

put

LinkedHashMap 中并没有重写 put 方法，而是重写了生成新节点的 newNode 方法，newNode 方法最终会被 put 方法调用

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

在每次构建新节点（即调用 newNode 方法）时，通过 linkNodeLast(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;
        
    }
    
}

同时 HashMap 中为 LinkedHashMap 预定义了三个用于维护内部链表的方法

// Callbacks to allow LinkedHashMap post-actions
// evict if false, the table is in creation mode
void afterNodeAccess(Node<K,V> p) { }

void afterNodeInsertion(boolean evict) { }

void afterNodeRemoval(Node<K,V> p) { }

在这里我们先分析 afterNodeAccess 和 afterNodeInsertion

// 将当前访问的节点移至内部链表尾部
void afterNodeAccess(Node<K,V> e) { 

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

void afterNodeInsertion(boolean evict) { // possibly remove eldest

    LinkedHashMap.Entry<K,V> first;
    
    // 在 LinkedHashMap 类中，removeEldestEntry 总是返回 false
    // 而在 LRU 中若缓存达到上限时 removeEldestEntry 会返回 true
    if (evict && (first = head) != null && removeEldestEntry(first)) {
    
        K key = first.key;
        
        removeNode(hash(key), key, null, false, true);
        
    }
    
}

remove

同样的，LinkedHashMap 中也没有重写 remove 方法，而是通过重写 afterNodeRemoval 方法来变相地实现 remove 重写

// 简单的删除链表中某个节点
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;
        
}

get

在 LinkedHashMap 重写了 get 方法，不过主要流程和 HashMap 中差不多，区别在于在其中加入了维护链表的功能，若 accessOrder 为 false，则和 HashMap 的 get 方法一致

public V get(Object key) {

    Node<K,V> e;
    
    // 调用的是 HashMap 中的 getNode 方法
    if ((e = getNode(hash(key), key)) == null)
        return null;
        
    if (accessOrder)
        afterNodeAccess(e);
        
    return e.value;
    
}

值得注意的是，afterNodeAccess() 函数中，会修改 modCount，因此当你正在 accessOrder=true 的模式下，迭代 LinkedHashMap 时，如果同时查询访问数据，也会导致 fail-fast，因为迭代的顺序已经改变

遍历

LinkedHashMap 重写了 entrySet 方法，通过遍历内部链表的方式来遍历 LinkedHashMap，而遍历内部链表则是通过 LinkedEntryIterator

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K,V>> {
    
    public final Map.Entry<K,V> next() { return nextNode(); }
    
}

而 LinkedHashIterator 则是 LinkedHashMap 中的一个内部抽象类

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

    // 在 LinkedEntryIterator 中的 next 方法中被调用，相当于 next 方法
    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;
        
        // 核心还是 HashMap 中定义的 removeNode 方法
        removeNode(hash(key), key, null, false, false);
        
        expectedModCount = modCount;
        
    }
    
}