浅谈HashMap，LinkedHashMap，ConcurrentHashMap、synchronizedMap（二.LinkedHashMap）

青旅半醒 2022-05-28 11:19 152阅读 0赞

说完HashMap，我们我们如果想要有序的Map怎么办。取出来之后再排序，不是太复杂。  
所以我们有LinkedHashMap。

## LinkedHashMap ##

既然LinkedHashMap是有序的，那么为什么是有序的？首先我们从名字上分析，LinkedHashMap和HashMap不是继承就是实现，那么数据结构应该也是类似的，采用hash表（数组+链表的形式）。等下，HashMap中既然存在链表问什么不是有序的？让我们带着问题看源码吧。

### 类关系 ###

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

从源码可知，LinkedHashMap继承HashMap。

### 属性 ###

/** * HashMap中的Node节点，在LinkedHashMap中变成了entry。 * 同时增加了before和after属性。 */
        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);
            }
        }
    
        private static final long serialVersionUID = 3801124242820219131L;
    
        /** * 双链表的头结点 */
        transient LinkedHashMap.Entry<K,V> head;
    
        /** * 双链表尾节点 */
        transient LinkedHashMap.Entry<K,V> tail;
    
        /** * 用来判断丽链表排序顺序： * true：插入顺序排序 * fasle：LRU算法（Least recently used，最近最少使用）。 */
        final boolean accessOrder;

我们看下不仅Entry属性有befor和after字段，而且有双链表头结点属性，尾节点属性。很容易就想到双链表啊！！所以LinkedHashMap数据结构，不仅仅是数组加链表。而且还有双链表。

### 数据结构 ###

![数据结构][70]  
总结一下，LinkedHashMap在Hash表的结构上增加了双向链表，类似于上图。但其实有没有想过，Hash表中其实已经存在链表的结构，为什么还要增加双向链表。在印象中，链表就是有序的。那Hash表中的链表和LinkedHashMap中的链表有什么不同呢？我认为有以下几点：

1.  桶中的链表是散列表结构的一部分；而双向链表是LinkedHashMap的额外引入；
2.  桶中的链表只做数据存储，因为生了hash碰撞，导致数据散落在一个桶中，用链表给予存储。没有存储顺序的概念；而LinkedHashMap的双向链表，是将插入Map的数据，按插入顺序（默认）存储起来。所以有序。

### 构造函数 ###

/** * 按照输入的大小以及加载因子创建对象。 * accessOrder = false;，默认不开启LRU规则，按照插入循序排序。 */
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
    
        /** * 按照给定的大小创建对象。加载因子为默认大小：0.75f。 * accessOrder = false;，默认不开启LRU规则，按照插入循序排序。 */
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
    
        /** * 按照默认的大小以及默认的加载因子大小创建对象。 * accessOrder = false;，默认不开启LRU规则，按照插入循序排序。 */
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
    
        /** * 新建一个哈希表，同时将另一个map m 里的所有元素加入表中。 * 默认加载因子以及足够大的容量。如果m为空，报NullPointerException。 * accessOrder = false;，默认不开启LRU规则，按照插入循序排序。 */
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }
    
        /** * 按照给定的大小，加载因子创建对象。 * 如果accessOrder = false;，不开启LRU规则，按照插入循序排序。 * 否则开启LRU规则，最近访问放在双向链表最后面。 */
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

既然是集成了HashMap那么一定会继承或者重写一些方法。  
我们没有在源码中看到put以及remove方法。由此可知，put以及remove是继承了HashMap的方法，并没有重写，直接调用。那既然要维护双向链表，所以在HahsMap源码中，有三个方法没有实现。但是在LinkedHashMap中实现了

## 重写方法 ##

### afterNodeAccess ###

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

这段代码的意思简洁明了，就是把当前节点e移至链表的尾部。因为使用的是双向链表，所以在尾部插入可以以O（1）的时间复杂度来完成。并且只有当accessOrder设置为true时，才会执行这个操作。在HashMap的putVal方法中，就调用了这个方法。

### afterNodeInsertion ###

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

afterNodeInsertion方法是在哈希表中插入了一个新节点时调用的，它会把链表的头节点删除掉，删除的方式是通过调用HashMap的removeNode方法。想一想，通过afterNodeInsertion方法和afterNodeAccess方法，是不是就可以简单的实现一个基于最近最少使用（LRU）的淘汰策略了？当然，我们还要重写removeEldestEntry方法，因为它默认返回的是false。

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

afterNodeInsertion()由于removeEldestEntry()所返回的false无执行意义。也就意味着如果想要让它有意义必须重写removeEldestEntry()。

### afterNodeRemoval ###

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删除一个键值对时调用的，它会把在HashMap中删除的那个键值对一并从链表中删除，保证了哈希表和链表的一致性。

### get ###

public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(e);我IE䦹·
            return e.value;
        }

LinkedHashMap同样重写了get，如果afterNodeAccess为true，调用afterNodeAccess方法，维护LRU规则。

## 总结 ##

因为HashMap不具备顺序性，所以产生了LinkedHashMap。继承HashMap，增加属性。同时其内部比HashMap增加了双向链表。并重写了部分HashMap方法。来确保其内部有序。

[70]: /images/20220528/85ea723688974b5e91edada534a7b193.png