Java源码学习--LinkedHashMap

JDK版本：1.8

LinkedHashMap内部维护了一个双向链表来保存元素。

一、重要属性

LinkedHashMap继承了HashMap，父类中的几个属性都原封不动的照用，除此之外，LinkedHashMap也有几个自己的属性：

• head：是一个LinkedHashMap.Entry<K,V>类型对象，之后会说这个LinkedHashMap.Entry继承自HashMap.Node，是LinkedHashMap针对自己所定制的；这里代表内部所维护的双向链表的头部
• tail：同head属性，这里代表双向链表的尾部
• accessOrder：该属性是一个final修饰的boolean，主要作用目前已知是决定是否在访问了(put和get方法)某一个存在的key-value之后，将他们置于双向链表的尾部

二、Entry类

该类继承了HashMap.Node，是LinkedHashMap为自己量身打造的单位数据存储类型：

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

可以看到，只是添加了两个属性：after和before来实现双向链表；从这里也可以看出LinkedHashMap实现的一些端倪：LinkedHashMap中有两个链表(确切的说是两种)，一个是由Entry中before和after属性共同实现的双链表；另一个是继承自HashMap中的Node的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;
}  

可见，默认都是将accessOrder设置为了false

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

关于构造器，就不多说了。

想要实现双链表，有一些必要的辅助方法不得不先说

1. linkNodeLast

该方法的作用是将所put的节点，添加到双链表的尾部：

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中在put方法调用的时候，会检查该key是否存在，之后才会决定是添加一个新的key-value对，还是覆盖原来key所对应的value。那么这个linkNodeLast显然只有在前者所对应的情况下才应该被调用，因此其被调用的位置就不得不斟酌斟酌：

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

而LinkedHashMap选择在newNode方法中来调用这个方法，在HashMap的putVal方法中确实在需要添加新的key-value对的时候会调用newNode方法新建一个节点这里是LinkedHashMap覆盖了父类的newNode方法。

2. transferLinks

该方法的作用是将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;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}  

注意，虽然将dst插入到了src所在的位置，但是src.before和src.after还是单方面的指向的原来的元素，这点并没有改变

3. afterNodeRemoval

该方法同afterNodeInsertion、afterNodeAccess都在HashMap中被定义，只是HashMap并没有去实现它们。

而这里的afterNodeRemoval在HashMap中调用的时机是在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;
}  

实际上猜也能猜到，这里肯定是将其从双向链表中删除的。

4. afterNodeAccess

该方法的调用时机是在HashMap调用putVal方法，且所对应的key已经存在的情况，从而覆盖原value后：

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

这个方法的作用是将被修改了的节点置为双向链表的表尾

5. afterNodeInsertion

该方法的调用时机是在HashMap调用putVal方法，且最终在table中添加了一个新的节点：

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

奇怪的是该方法的if语句的最后一个条件在LinkedHashMap中的实现为：

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

所以，afterNodeInsertion相当于啥也没干

6. get

HashMap的常用方法中，LinkedHashMap只重写了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;
}  

可见和HashMap相比，只是多了第二个if语句而已。

LinkedHashMap每次get方法都会调用afterNodeAccess方法来将访问的节点置于双向链表的表尾，如果不想要这个效果，请将accessOrder设置为false

7. containsValue

该方法请勿和HashMap的containsKey混淆，HashMap只提供了containsKey方法，而containsValue方法是LinkedHashMap独创的：

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}  

该方法就是遍历双向链表来查找是否有目标value，其显然比containsKey要慢一些(因为containsKey首先会通过hash缩小范围)

四、非重要方法

LinkedHashMap只是重写了HashMap的entrySet、keySet、values三个，而他们各自对应的类，基本只是将其forEach方法从原来的for循环嵌套遍历改为了一个for循环遍历双向链表而已。

五、总结

重要知识点：

1. LinkedHashMap中有两个链表：双向链表通过Entry的after和before属性构成；单项链表则继承自HashMap中Node的next属性。二者相互独立，没有交集
2. LinkedHashMap中每次访问(put和get方法)已存在的key-value对之后，提供将他们置于双向链表表尾的服务，开启这个服务需要调用三个参数的构造器，将accessOrder置为true
3. LinkedHashMap提供了containsValue方法共我们使用

一些收获：

最大的收获是LinkedHashMap对HashMap的继承，及HashMap优雅的结构。在HashMap中，预留了三个方法afterNodeInsertion、afterNodeAccess、afterNodeRemoval，而且在其对应的位置调用；因此LinkedHashMap只需实现这三个预留的方法即可，而不用覆盖HashMap的put方法。

要是我来写的话，可能不会再HashMap中预留出一些方法供子类调用，只会在子类中去单独定义，而且还会完全重写父类的put方法。显然使得子类变得臃肿，不够优雅。