源码|jdk源码之LinkedHashMap分析

2018-09-07

HashMap作为一种经典的数据结构，其根据key定位元素能达到平均O(1)的时间复杂度。但是，存储于HashMap中的元素显然是无序的，遍历HashMap的顺序得看脸。。。
那如何使得HashMap里的元素变得有序呢？一种思路是，将存放HashMap元素的节点，使用指针将他们串起来。换言之，就像在HashMap里面“嵌入”了一个链表一样。
实际上，jdk的LinkedHashMap就是使用这种思路实现的。

1. 继承HashMap

LinkedHashMap中的代码不算多，这是因为，jdk的设计使用继承复用了代码，在jdk的设计中，LinkedHashMap是HashMap的扩展：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    /* ... */
}

2. 对节点进行扩展

2.1. 父类HashMap中的节点

回想一下HashMap的实现方式中，将key和value打包成的节点有两种：
第一种，传统分离链表法的链表节点。

1
2
3

static class Node<K,V> implements Map.Entry<K,V> {
    /* ... */
}

第二种，HashMap为进行优化，一定情况下会将链表重构为红黑树。第二种节点是红黑树节点：

1
2
3

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    /* ... */
}

突然发现，HashMap的TreeNode是继承至LinkedHashMap的Entry的。。。
个人观点是jdk这种做法不是很优雅，本身LinkedHashMap继承HashMap就使得两者之间的逻辑混在了一起，而这里的内部实现又反过来继承，逻辑搞得很混乱。

2.2. 扩展节点

LinkedListHashMap需要将节点串成一个“嵌入式”双向链表，因此需要给这两种节点增加两个字段：

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

扩展HashMap.Node，增加双向链表字段。
由于TreeNode是继承自LinkedListMap.Entry的，所以它也有这两个字段。

2.3. 属性

再来看下LinkedHashMap中的属性，很少：

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

记录双向链表的表头和表尾。从注释中可以看出，head节点是最老的，tail节点是最新的，也即链表按照由老到新的顺序串起来。

最后，由于LinkedHashMap是可以设置它组织元素的顺序。一种是链表中的元素是按插入时候的顺序排序，另外一种是按照访问的顺序排序。

1 2	// 指定顺序是按照访问顺序来，还是插入顺序来 final boolean accessOrder;

这个accessOrder指定是否按插入顺序来。

3. 重写创建节点的函数

由于对Map中的节点进行了扩展，因此，在创建节点时不能使用原来的节点了，而应该使用重新创建后的。
HashMap将创建节点的操作抽取出来放到了单独的函数中，LinkedHashMap重写即可：

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;
}
// HashMap的TreeNode是继承自LinkedHashMap.Entry的，因此能够参与组织双向链表
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;
}

4. 在获取、插入、删除元素时维护双向链表

接下来，则需要在LinkedHashMap的操作时维护双向链表。

4.1. 删除

回顾下HashMap的源代码，我们知道，HashMap在删除节点后，会调用afterNodeRemoval函数。
这个函数在HashMap中是空的，实际上jdk是将它设计为一个hook，果然，在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;
}

4.2. 插入

按照类似的思路，HashMap中在插入元素后会调用afterNodeInsertion，那是不是LinkedHashMap也在这里实现了相关逻辑，插入元素后维护双向链表节点呢？

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

然而，实际上在LinkedHashMap中该函数似乎没有什么用。因为：

1
2
3

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

removeEldestEntry始终返回false，afterNodeInsertion相当于什么也没做。这个逻辑设计目的是什么，还不能很清楚。也许也是为了让谁去继承？以后再探究。

那插入元素后的在哪里维护了双向链表呢？回到之前的newNode和newTreeNode：

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;
}
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;
}
// 尾插双向链表节点
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中调用newNode时候都是为了装新插入的元素，所以在这里维护双向链表。
感觉耦合是不是太紧了。。。如果HashMap由于某个操作需要临时搞个newNode借用下，岂不是会出问题？

下面是replacementNode和replacementTreeNode。
replacementNode在HashMap中的作用是，该K V之前是被TreeNode包装的，现在需要拿Node包装它。这也势必会影响双向链表的结构，所以这里也需要额外维护下。

4.3. 获取

获取的时候，同样，是重写了`afterNodeAccess`钩子，这样在HashMap的获取逻辑结束后，这里的逻辑会被执行，维护双向链表。
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;
    }
}

LinkedHashMap中的顺序有访问序和插入序，只有访问序才需要在访问的时候更新双向链表结构。也即accessOrder为true才会执行这段逻辑。

最后，注意到：

1 2	++modCount; }

一般来说，只有修改了Map结构的操作，才需要修改modCount以让正在迭代的迭代器感知到了变化。
但是这里，由于迭代器是使用这里的“嵌入式”双向链表进行迭代，而在这里会改变双向链表的结构，若迭代器继续迭代会造成不可预测的结果。
所以，这里需要改变modCount，阻止迭代器继续迭代。

5. 典型应用场景

LinkedHashMap的一个典型应用场景是LRU算法。

由于现在夜已深，现在不敢熬夜身体吃不消，想睡觉了。所以这个坑以后再填

6. 最后

LinkedHashMap还有其它的一些实现细节，如：

clear的时候也要同时维护双向链表；
根据双向链表实现迭代器。

最后，总结下jdk中对LinkedHashMap中的实现思路：

扩展HashMap实现。
扩展HashMap的节点（包括Node和TreeNode），加入两个域组织额外的双向链表保存顺序。
在产生插入、删除、访问的地方维护双向链表，通过重写某些方法实现。
实现迭代器相关逻辑，因为迭代器是根据双向链表顺序迭代的。