Java 集合框架系列十四：JDK 1.8 LinkedHashMap 详解

小咪咪 2022-12-04 08:59 175阅读 0赞

## LinkedHashMap 继承关系 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]  
LinkedHashMap 直接继承自 HashMap，是 HashMap 的子类，可以联想到 LinkedHashMap 是在 HashMap 的基础上做的扩展，LinkedHashMap 也具备 HashMap 的诸多特性。，添加了一些新的特性。具体是哪些特性下面来进行了解。

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

## 类文档解读 ##

老规矩，先通过 LinkedHashMap 的类文档了解一下能得到哪些信息。

*  LinkedHashMap 是基于哈希表和链表的实现，与 HashMap 的不同之处在于它维护了一个双端链表，该链表默认维护了映射的插入顺序作为迭代顺序，而 HashMap 是无序的。注意，*对 LinkedHashMap 已存在的 key 进行重新插入(put)，不会影响其插入顺序*。
 *  LinkedHashMap 是有序的集合，其维护迭代顺序的成本要低于 TreeMap。
 *  LinkedHashMap 除了支持插入顺序，还提供了一个构造方法支持按照映射的访问顺序来维护其迭代顺序，访问顺序非常适合用来实现 LRU 缓存 。put、putIfAbsent、get、getOrDefault、computeIfAbsent、computeIfPresent、merge、replace 方法都会记录对元素的访问从而影响其迭代顺序，但是对集合视图的操作不会对访问顺序产生影响。
 *  子类可以重写此类的 removeEldestEntry方法，以便在将新的映射添加到 Map 时，自动执行删除过时映射的策略。
 *  LinkedHashMap 允许键值对为 null。由于需要维护一个双端链表所以其性能可能略低于 HashMap，但是 LinkedHashMap 的迭代性能要高于 HashMap。
 *  影响 LinkedHashMap 性能的参数有两个：初始容量和负载因子。这点和 HashMap 一样。为 LinkedHashMap 设置一个过高的初始容量比 HashMap 的惩罚要轻，因为 LinkedHashMap 迭代的次数不受容量影响。说明初始容量对 LinkedHashMap 没有那么重要，因为链表不需要像数组那样必须先声明足够的空间。
 *  LinkedHashMap 是非线程安全的，如果希望使用线程安全的实现，可以使用Map m = Collections.synchronizedMap(new LinkedHashMap(…));返回同步的集合。
 *  LinkedHashMap 返回的迭代器也是支持 fail-fast 策略的。

## LinkedHashMap API ##

### 成员变量 ###

// 双端链表的头节点
        transient LinkedHashMap.Entry<K,V> head;
    
        // 双端链表的尾节点
        transient LinkedHashMap.Entry<K,V> tail;
    
        // 迭代器的顺序，true 表示访问顺序，false 表示插入顺序
        final boolean accessOrder;

LinkedHashMap 维护了一个 静态内部类 Entry 继承了 HashMap.Node，在其基础上添加了 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);
            }
        }

回顾一下，HashMap 内部定义了一个 TreeNode 继承自 LinkedHashMap.Entry，而 Entry 又继承自 HashMap.Node，HashMap.Node 继承自 Map.Entry，通过类图看一下。  
![在这里插入图片描述][20200907180844857.png_pic_center]

### 数据结构图 ###

LinkedHashMap 内部的数据结构大概如图所示，与 HashMap 不同的地方就是它的 before 和 after 指针将所有节点链接成一个循环双端链表，保证了存储元素的顺序。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]

### 构造方法 ###

// 使用插入顺序作为迭代顺序，默认初始容量 15，负载因子 0.75
        public LinkedHashMap() { 
            super();
            accessOrder = false;
        }
    	// 使用插入顺序作为迭代顺序，指定初始容量，负载因子 0.75
        public LinkedHashMap(int initialCapacity) { 
            super(initialCapacity);
            accessOrder = false;
        }
    	
    	// 使用插入顺序作为迭代顺序，指定初始容量和负载因子
        public LinkedHashMap(int initialCapacity, float loadFactor) { 
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
    	
    	
        // 指定迭代顺序、初始容量、负载因子 
        public LinkedHashMap(int initialCapacity,float loadFactor,
                             boolean accessOrder) { 
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }
        
        // 将指定 Map 映射添加到当前 Map
    	public LinkedHashMap(Map<? extends K, ? extends V> m) { 
            super();
            // 使用插入顺序
            accessOrder = false;
            // 调 HashMap 的 putMapEntries 方法
            putMapEntries(m, false);
        }

### 增加映射 ###

LinkedHashMap 仍然使用 HashMap 的 put 方法，但是重写了构建新节点的 newNode() 方法，或者是通过 replacementNode 来替换值。在树化时也有两个对应的方法，分别是 newTreeNode 和 replacementTreeNode。在每次构建新节点时，通过 linkNodeLast 方法将新节点链接在内部双向链表的尾部。也就是说使用 HashMap 时内部使用的是 HashMap.Node 类型的节点，使用 LinkedHashMap 时其内部使用的类型就变成了 LinkedHashMap.Entry，而 LinkedHashMap.Entry 又是 HashMap.Node 的子类，所以这是没有任何问题的，这里充分利用了面向对象的语言特点。

//在构建新节点时，构建的是 LinkedHashMap.Entry 不再是 Node
    	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;
        }
    	// 将新增的节点，连接在链表的尾部
    	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;
            }
        }
    	// 替换链表节点
    	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 类型
    	// 但是多了 linkNodeLast(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;
        }
    	// 依然使用 HashMap.TreeNode 类型
    	// 但是多了 linkNodeLast(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;
        }
    	// 调整链表顺序
    	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;
        }

还记得 HashMap 提供了三个空方法给 LinkedHashMap 实现，作为回调方法在添加、删除、访问元素后做一些特殊的操作。

// 访问后回调
    	void afterNodeAccess(Node<K,V> p) {  }
    	// 插入节点回调
        void afterNodeInsertion(boolean evict) {  }
        // 删除节点回调
        void afterNodeRemoval(Node<K,V> p) {  }

#### afterNodeInsertion ####

此方法作为节点被插入后的回调方法，在 HashMap 的 putVal、computeIfAbsent、compute 、merge 中调用了此方法。

void afterNodeInsertion(boolean evict) {  // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            // LinkedHashMap 默认返回 false 则不删除节点
            if (evict && (first = head) != null && removeEldestEntry(first)) { 
                K key = first.key;
                // 调 HashMap 的 remove 方法
                removeNode(hash(key), key, null, false, true);
            }
        }
        // LinkedHashMap 默认返回false 则不删除节点
        // 返回 true 代表要删除最早的节点 
        // 通常构建一个 LRU 缓存会在达到缓存的上限时返回 true
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { 
            return false;
        }

### 删除映射 ###

LinkedHashMap 也没有重写 remove() 方法，因为它的删除逻辑和 HashMap 并无区别。但它重写了 afterNodeRemoval() 这个回调方法。

#### afterNodeRemoval ####

//在删除节点 e 时，同步将 e 从双向链表上删除
        void afterNodeRemoval(Node<K,V> e) {  // unlink
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //待删除节点 p 的前置后置节点都置空
            p.before = p.after = null;
            //如果前置节点是null，则现在的头结点应该是后置节点a
            if (b == null)
                head = a;
            else//否则将前置节点b的后置节点指向a
                b.after = a;
            //同理如果后置节点时null ，则尾节点应是b
            if (a == null)
                tail = b;
            else//否则更新后置节点a的前置节点为b
                a.before = b;
        }

### 查询 ###

LinkedHashMap 重写了 get() 和 getOrDefault() 方法。对比 HashMap 中的实现 LinkedHashMap 只是增加了在 accessOrder 为 true 的情况下，要去回调 afterNodeAccess 方法。

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;
        }
        public V getOrDefault(Object key, V defaultValue) { 
           Node<K,V> e;
           if ((e = getNode(hash(key), key)) == null)
               return defaultValue;
           if (accessOrder)
           		// 按照访问顺序调整链表
               afterNodeAccess(e);
           return e.value;
       }

#### afterNodeAccess ####

此方法在 HashMap 中的 putVal、replace、computeIfAbsent、computeIfPresent、compute、merge 中，是在 key 被访问后的回调方法。在 LinkedHashMap 中，get、getOrDefault 方法会调此方法。

// 将当前被访问到的节点e，移动至内部的双向链表的尾部
    	void afterNodeAccess(Node<K,V> e) {  // move node to last
            LinkedHashMap.Entry<K,V> last;//原尾节点
            //如果accessOrder 是true ，且原尾节点不等于e
            if (accessOrder && (last = tail) != e) { 
                //节点e强转成双向链表节点p
                LinkedHashMap.Entry<K,V> p =
                    (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
                //p现在是尾节点， 后置节点一定是null
                p.after = null;
                //如果p的前置节点是null，则p以前是头结点，所以更新现在的头结点是p的后置节点a
                if (b == null)
                    head = a;
                else//否则更新p的前直接点b的后置节点为 a
                    b.after = a;
                //如果p的后置节点不是null，则更新后置节点a的前置节点为b
                if (a != null)
                    a.before = b;
                else//如果原本p的后置节点是null，则p就是尾节点。 此时 更新last的引用为 p的前置节点b
                    last = b;
                if (last == null) //原本尾节点是null 则，链表中就一个节点
                    head = p;
                else { //否则 更新 当前节点p的前置节点为 原尾节点last， last的后置节点是p
                    p.before = last;
                    last.after = p;
                }
                //尾节点的引用赋值成p
                tail = p;
                //修改modCount。
                ++modCount;
            }
        }

#### containsValue ####

LinkedHashMap 重写了该方法，相比 HashMap 的实现更为高效。

public boolean containsValue(Object value) { 
            //遍历一遍链表，去比较有没有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;
        }

对比 HashMap，是用两个 for 循环遍历，相对低效。

public boolean containsValue(Object value) { 
            Node<K,V>[] tab; V v;
            if ((tab = table) != null && size > 0) { 
          	  // 遍历数组
                for (int i = 0; i < tab.length; ++i) { 
                	// 遍历链表
                    for (Node<K,V> e = tab[i]; e != null; e = e.next) { 
                        if ((v = e.value) == value ||
                            (value != null && value.equals(v)))
                            return true;
                    }
                }
            }
            return false;
        }

### 遍历 ###

LinkedHashMap 重写了 entrySet() 方法，返回的 LinkedEntrySet 集合视图是 LinkedHashMap 的内部类。

public Set<Map.Entry<K,V>> entrySet() { 
            Set<Map.Entry<K,V>> es;
            //返回 LinkedEntrySet
            return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
        }
        
        final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> { 
            public final Iterator<Map.Entry<K,V>> iterator() { 
                return new LinkedEntryIterator();
            }
        }

LinkedEntryIterator 是 LinkedHashMap 的内部类，继承了 LinkedHashIterator

final class LinkedEntryIterator extends LinkedHashIterator
            implements Iterator<Map.Entry<K,V>> { 
            public final Map.Entry<K,V> next() {  return nextNode(); }
        }
    
        abstract class LinkedHashIterator { 
            //下一个节点
            LinkedHashMap.Entry<K,V> next;
            //当前节点
            LinkedHashMap.Entry<K,V> current;
            int expectedModCount;
    
            LinkedHashIterator() { 
                //初始化时，next 为 LinkedHashMap内部维护的双向链表的扁头
                next = head;
                //记录当前modCount，以满足fail-fast
                expectedModCount = modCount;
                //当前节点为null
                current = null;
            }
            //判断是否还有next
            public final boolean hasNext() { 
                //就是判断next是否为null，默认next是head 表头
                return next != null;
            }
            //nextNode() 就是迭代器里的next()方法 。
            //该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。
            final LinkedHashMap.Entry<K,V> nextNode() { 
                //记录要返回的e。
                LinkedHashMap.Entry<K,V> e = next;
                //判断fail-fast
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                //如果要返回的节点是null，异常
                if (e == null)
                    throw new NoSuchElementException();
                //更新当前节点为e
                current = e;
                //更新下一个节点是e的后置节点
                next = e.after;
                //返回e
                return e;
            }
            //删除方法 最终还是调用了HashMap的removeNode方法
            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;
                removeNode(hash(key), key, null, false, false);
                expectedModCount = modCount;
            }
        }

值得注意的就是：nextNode() 就是迭代器里的 next() 方法 。该方法的实现可以看出，迭代LinkedHashMap，就是从内部维护的双链表的表头开始循环输出。

## 总结 ##

LinkedHashMap 相对于 HashMap 的源码是很简单的。因为它继承了 HashMap，仅重写了几个方法，以改变它迭代遍历时的顺序。这也是其与 HashMap 相比最大的不同。

*  在每次插入数据，或者访问、修改数据时，会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序。
 *  accessOrder 默认是 false，则迭代时输出的顺序是插入节点的顺序。若为 true，则输出的顺序是按照访问节点的顺序。为 true 时可以在这基础之上构建一个 LruCache.
 *  accessOrder=true 的模式下，在 afterNodeAccess() 方法中，会将当前被访问到的节点e，移动至内部的双向链表的尾部。afterNodeAccess() 方法会修改 modCount，因此在accessOrder=true 的模式下迭代 LinkedHashMap 时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
 *  LinkedHashMap 与 HashMap 比还有一个小小的优化，重写了 containsValue() 方法，直接遍历内部链表去比对 value 值是否相等。
 *  LinkedHashMap 的数据结构包括：数组+链表+红黑树+双端循环链表，LinkedHashMap 是在 HashMap 的基础上添加了对顺序维护的功能。
 *  HashMap 在数据的存储和查找性能卓越，但是因为 HashMap 是无序的，所以在大量需要遍历的场景下性能略差。LinkedHashMap 由于在存储时需要对双端列表进行维护所以性能略差但是其迭代性能比 HashMap 好，LinkedHashMap 映射减少了 HashMap 排序中的混乱，且不会导致 TreeMap 的性能损失。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/2b4b541265ec46e79d347e472adbf210.png
[20200907180844857.png_pic_center]: /images/20221123/cf407a96223b47ad9e234c2fff464a7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dZQTE5OTM_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/fb3e236293b04b32bbbe6f7498f211db.png