超详细LinkedHashMap解析

LinkedHashMap概述

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

LinkedHashMap继承自HashMap，它的多种操作都是建立在HashMap操作的基础上的。同HashMap不同的是，LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序。这也是Linked的含义。结构图如下：

加入插入顺序为key1，key2，key3，key4，那么就会维护一个红线所示的双向链表。

为了实现双向链表，LinkedHashMap中提供了如下的Entry：

 / * LinkedHashMap中的node直接继承自HashMap中的Node。并且增加了双向的指针 */ 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); } } 

如果可以说，LinkedHashMap=HashMap+双向链表

LinkedHashMap原理

主要元素

 / * 头指针，指向第一个node */ transient LinkedHashMap.Entry<K,V> head; / * 尾指针，指向最后一个node */ transient LinkedHashMap.Entry<K,V> tail; / * 一个条件变量，它控制了是否在get操作后需要将新的get的节点重新放到链表的尾部 * LinkedHashMap可以维持了插入的顺序，但是这个顺序不是不变的，可以被get操作打乱。 * * @serial */ final boolean accessOrder; 

其他的元素就是直接继承HashMap中的。

构造函数

 / * Constructs an empty insertion-ordered LinkedHashMap instance * with the specified initial capacity and load factor. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity, float loadFactor) { 
    super(initialCapacity, loadFactor); accessOrder = false; } / * 构造一个空的，按插入序（accessOrder = false）的LinkedHashMap，使用默认初始大小和负载因子0.75 * * @param initialCapacity the initial capacity * @throws IllegalArgumentException if the initial capacity is negative */ public LinkedHashMap(int initialCapacity) { 
    super(initialCapacity); accessOrder = false; } / * 默认构造函数也是关闭了get改变顺序，使用插入序。 */ public LinkedHashMap() { 
    super(); accessOrder = false; } / * Constructs an insertion-ordered LinkedHashMap instance with * the same mappings as the specified map. The LinkedHashMap * instance is created with a default load factor (0.75) and an initial * capacity sufficient to hold the mappings in the specified map. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public LinkedHashMap(Map<? extends K, ? extends V> m) { 
    super(); accessOrder = false; putMapEntries(m, false); } / * 这个构造方法指定了accessOrder * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode - true for * access-order, false for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { 
    super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } 

注意，构造函数如果不明确传入accessOrder的话，默认都是按插入序的。

维护链表的操作

维护链表主要使用三个方法。

afterNodeRemoval，afterNodeInsertion，afterNodeAccess。这三个方法的主要作用是，在删除，插入，获取节点之后，对链表进行维护。简单来说，这三个方法中执行双向链表的操作：

afterNodeRemoval

顾名思义，在节点remove操作后进行调用：

 //在节点删除后，维护链表，传入删除的节点 void afterNodeRemoval(Node<K,V> e) { 
    // unlink //p指向待删除元素，b执行前驱，a执行后驱 LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //这里执行双向链表删除p节点操作，很简单。 p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } 

afterNodeAccess

 //在节点被访问后根据accessOrder判断是否需要调整链表顺序 void afterNodeAccess(Node<K,V> e) { 
    // move node to last LinkedHashMap.Entry<K,V> last; //如果accessOrder为false，什么都不做 if (accessOrder && (last = tail) != e) { 
    //p指向待删除元素，b执行前驱，a执行后驱 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; //这里执行将p放到尾部 if (last == null) head = p; else { 
    p.before = last; last.after = p; } tail = p; //保证并发读安全。 ++modCount; } } 

afterNodeInsertion

这是一个很奇葩的方法，虽然名字是在插入之后进行的维护链表的操作，但是默认实际上这个什么都没做，看代码：

 void afterNodeInsertion(boolean evict) { 
    // possibly remove eldest LinkedHashMap.Entry<K,V> first; //removeEldestEntry(first)默认返回false，所以afterNodeInsertion这个方法其实并不会执行 if (evict && (first = head) != null && removeEldestEntry(first)) { 
    K key = first.key; removeNode(hash(key), key, null, false, true); } } protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
    return false; } 

为什么不执行也可以呢，这个要到put操作的时候就能看出来了。

那么removeEldestEntry这个方法有什么用呢，看名字可以知道是删除最久远的节点，也就是head节点，这个方法实际是给我们自己扩展的。默认是没有用的，接下来实现LRU的代码中将可以看到它的作用。

get操作

LinkedHashMap重写了HashMap的get方法，如下：

 / * 调用hashmap的getNode方法获取到值之后，维护链表 * @param key * @return */ 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; } 

这个方法的实现简单易懂。

put操作

LinkedHashMap没有重写HashMap的put方法，所以执行put操作的时候，还是使用的是HashMap的put方法。那么这样如何保证链表的逻辑呢？原因就是HashMap的putVal方法中实际调用了维护链表的方法，下面是关键代码：HashMap的putVal()方法

HashMap#putVal(…)

 //默认的传入的evict是true final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { 
    ................ ................ ................ ................ if (e != null) { 
    // existing mapping for key //如果e不为null，此时的e指向的就是在map中的那个插入点，所以这个时候来赋值。 V oldValue = e.value; // onlyIfAbsent入口参数，为true，则不更新value（前面已说明）。 //这个地方的主要作用主要控制如果map中已经有那个key了，是否需要需要更新值 if (!onlyIfAbsent || oldValue == null) e.value = value; //这里其实是插入成功后执行的，获得的效果就是将e放到了链表结尾。 //所以afterNodeInsertion方法就算什么都不做也可以。 //但是如果accessOrder为false，那么我们新插入的节点，都不会进入链表了 afterNodeAccess(e); return oldValue; } } //fast-fail机制的实现，为了保证并发读安全。 ++modCount; //容器中的键值对数自增，如果大于了阈值，开始扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; } 

在put方法中，HashMap会在合适的位置使用 afterNodeAccess(e)，和afterNodeInsertion(evict);方法。因为在HashMap中也定义了这三个函数，但是都是为空函数，在LInkedHashMap中只是重写了这3个方法。我们在使用map.put(key,value)的时候，实际调用HashMap#putVal(key,value)方法，然后再调用afterNodeAccess方法，那么这个时候调用的会是子类的afterNodeAccess方法吗？

这个就要涉及到多态的知识了，可以从虚拟机方面去解释：在虚拟机加载类的解析过程中，对方法调用有两种分派方式，静态分派对应重载，动态分派对应重写。这里对应的就是动态分派。动态分配是在运行时发生的，它对于方法是按照实际类型来首先寻找的。找不到再往父类走。这里的实际类型其实值new 后面跟着的类。所以这里不用担心会调用到父类的方法。

afterNodeInsertion方法不是没有用，而是留给扩展用的，下面会展示。

还有一点，put操作中使用afterNodeAccess来将新插入的节点放到尾部。但是这个方法要受到accessOrder的控制，如果accessOrder为false（默认就为false）那么新插入的节点应该就不能插入到链表中了。这样设计有什么特殊的意义吗？

Remove操作

HashMap#removeNode(…)

和put操作一样，也是直接使用HashMap的方法来完成的：

 final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) { 
    Node<K,V>[] tab; Node<K,V> p; int n, index; //判断table是否为空，该key对应的桶是否为空 if ((tab = table) != null && (n = tab.length) > 0 && (p = tab[index = (n - 1) & hash]) != null) { 
    Node<K,V> node = null, e; K k; V v; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) node = p; else if ((e = p.next) != null) { 
    if (p instanceof TreeNode) node = ((TreeNode<K,V>)p).getTreeNode(hash, key); else { 
    do { 
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) { 
    node = e; break; } p = e; } while ((e = e.next) != null); } } //到这里了其实node就已经指向了要删除的节点了 //matchValue的作用是指现在是否需要值匹配。因为可能没有传入value，所以判断一下 if (node != null && (!matchValue || (v = node.value) == value || (value != null && value.equals(v)))) { 
    if (node instanceof TreeNode) ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable); else if (node == p) tab[index] = node.next; else p.next = node.next; ++modCount; --size; //调用维护链表的操作 afterNodeRemoval(node); return node; } } return null; } 

LinkedHashMap用作实现LRU

LRU，即最近最少使用。LRU中保存的数据如果满了，那么就会将最近最少使用的数据删除。

LinkedHashMap通过使accessOrder为true，可以满足这种特性。代码如下：

leetcode 146. LRU缓存机制

class LRUCache extends LinkedHashMap { 
    private int capacity; public LRUCache(int capacity) { 
    //accessOrder为true super(capacity, 0.75F, true); this.capacity = capacity; } public int get(int key) { 
    return (int)super.getOrDefault(key, -1); } public void put(int key, int value) { 
    super.put(key, value); } protected boolean removeEldestEntry(Map.Entry eldest) { 
    return size() > capacity; } } 

这里重写了removeEldestEntry方法，然后removeEldestEntry方法在afterNodeInsertion中被调用，如果这个方法返回真，那么就会删除head指向的节点。根据每次get的节点都会放到尾部的特性，所以head指向的节点就是最久没有使用到的节点，所以可以删除。由于我们每次put完（HashMap#putVal()）都会调用这个afterNodeInsertion方法，所以可以上面的设计可以使put过后如果size超了，将删除最久没有使用的一个节点，从而腾出空间给新的节点。

总结

一句话总结，LinkedHashMap就是HashMap中将其node维护成了一个双向链表。只要搞懂了HashMap就可以很容易搞懂LinkedHashMap。

借鉴：https://hestyle.blog.csdn.net/article/details/