Java集合12 - JDK1.7中的LinkedHashMap

阳光穿透心脏的1/2处 2022-12-30 04:00 232阅读 0赞

**目录**

1.LinkedHashMap是什么

2.LinkedHashMap的底层结构

3.LinkedHashMap的特性

4.LinkedHashMap的数据迁移

--------------------

### 1.LinkedHashMap是什么 ###

一个基于LinkedList和HashMap实现的Map，继承自HashMap，实现了Map接口。源码上的注释告诉了我们以下几件事：

**       底层实现**：基于LinkedList和HashMap实现，允许null元素，内部维护了一个贯穿所有内部节点的双向链表，可以通过构造函数来指定其迭代顺序（插入顺序/访问顺序）。

**       性能：**与HashMap一样，add、contains、remove提供恒定的时间性能，假设hash函数在bucket之间适当地分散元素。性能可能略低于HashMap，这是因为维护链表会增加额外的开销。LinkedHashMap有两个影响其性能的参数：初始容量和负荷系数。但请注意，对于这个类来说，为初始容量选择一个过高的值的惩罚要比HashMap要轻，因为这个类的迭代次数不受容量的影响。

**同步机制：**LinkedHashMap的实现是不同步的，如果多个线程同时访问LinkedHashMap实例，并且至少有一个线程在结构上进行了修改，则必须在外部同步。（结构修改是添加或删除一个或多个映射的任何操作，或者在访问有序的LinkedHashMap情况下，影响迭代顺序的任何操作。在保证插入顺序的LinkedHashMap中，仅更改与映射中已包含的键相关联的值不是结构修改。**在LinkedHashMap中，仅仅使用get查询映射是一种结构修改** ），这通常是通过在LinkedHashMap实例对象上进行同步来实现。 如果不存在这样的对象，应使用Collections.synchronizedMap(new LinkedHashMap(...))来创建线程同步的集合。

**fail-fast特性：**迭代器为快速失败，用迭代器遍历LinkedHashMap时，迭代器的remove()和add()会抛出ConcurrentModificationException异常，迭代器的fail-fast行为在不同步的并发修改时不能得到硬性保证，fail fast行为应仅用于检测错误，不要依赖此异常进行编程。

### 2.LinkedHashMap的底层结构 ###

既然是由双向链表维护的内部结构，那么我们先来看一下其基础存储结构：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70][]

果然在HashMap的基础上增加了前后两个指针，其实LinkedHashMap底层存储原理如下图所示：

![format_png][]

### 3.LinkedHashMap的特性 ###

LinkedHashMap最主要的特性为迭代元素的时候支持按照插入顺序或访问顺序迭代，什么是插入顺序和访问顺序呢？插入顺序：![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1][]

![20201224102224487.png][]

可以看到元素的迭代顺序完全按照元素的插入顺序来迭代，访问顺序：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2][]

![20201224102414994.png][]

当我们在构造函数中给accessOrder变量传入true后会发现，元素的迭代顺序会按照我们的访问顺序来迭代(先访问的最后迭代)。accessOrder变量就是控制LinkedHashMap元素迭代顺序的开关，True为按照元素访问顺序迭代，False为按照元素插入顺序迭代。那LinkedHashMap是如何实现这个功能的呢？LinkedHashMap在构造的时候，先调用HashMap构造函数初始化了一个Entry\[\] table，然后调用自身重写过的init()初始化了一个只有头结点的双向链表：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3][]

接下来我们查看LinkedHashMap的put方法，可以看到其内部并无put方法，而是使用的HashMap的put方法，只是重写了其中的recordAccess()和addEntry()方法：

//HashMap中的put方法
    public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);//LinkedHashMap对recordAccess方法进行了重写
                    return oldValue;
                }
            }
            modCount++;
            addEntry(hash, key, value, i);//LinkedHashMap对addEntry方法进行了重写
            return null;
        }

看到这不得不佩服JDK的设计如此巧妙，接下来我们重点看一下addEntry()：

void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }
    void createEntry(int hash, K key, V value, int bucketIndex) {
            HashMap.Entry<K,V> old = table[bucketIndex];
            Entry<K,V> e = new Entry<>(hash, key, value, old);
            table[bucketIndex] = e;
            e.addBefore(header);
            size++;
        }
    private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }

由源码可知LinkedHashMap首先调用了HashMap中的addEntry()方法，并对HashMap中的createEntry()方法进行了重写，先将元素添加至table数组(添加过程为HashMap的添加过程)，然后将新增结点添加至双向链表中。举个例子：首先是只加入一个元素Entry1，假设index为0：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4][]

当再加入一个元素Entry2，假设index为15：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5][]

当再加入一个元素Entry3, 假设index也是0：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6][]

recordAccess()方法我们去get()的源码中查看：LinkedHashMap的get()显示调用的hashmap的getEntry()，随后调用了LinkedHashMap.Entry的recordAccess方法，进行重新排序，把get的Entry移动到双向链表的表尾(顺序访问)。

public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }
    void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                //把更新的Entry从双向链表中移除
                remove();
                // 再把更新的Entry加入到双向链表的表尾
                addBefore(lm.header);
            }
    }

在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会对更新的Entry进行重新排序，而如果是插入顺序模式时，不会重新排序，这里的排序跟在HashMap中存储没有关系，只是指在双向链表中的顺序。eg：开始时，HashMap中有Entry1、Entry2、Entry3，并设置LinkedHashMap为访问顺序，则更新Entry1时，会先把Entry1从双向链表中删除，然后再把Entry1加入到双向链表的表尾，而Entry1在HashMap结构中的存储位置没有变化，对比图如下所示：

![format_png 1][]

### 4.LinkedHashMap的数据迁移 ###

LinkedHashMap重写了HashMap中扩容后数据迁移的方法transfer()：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7][]

可以看到和HashMap的区别为：

**HashMap：**先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry后重新计算其在数组中的位置，然后存放到新table的对应位置。

**LinkedHashMap：**遍历的双向链表，取得每一个Entry后重新计算其在数组中的位置，然后存放到新table的对应位置。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70]: /images/20221120/aa64e61b3a6b47cda5755308cf958696.png
[format_png]: /images/20221120/6fd5c6ff169d463da972061b7c1781ae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 1]: /images/20221120/29e906996e5d4a88a619da000c8318f0.png
[20201224102224487.png]: https://img-blog.csdnimg.cn/20201224102224487.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201224102400652.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[20201224102414994.png]: https://img-blog.csdnimg.cn/20201224102414994.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/2020122410312423.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020122410355990.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201224103620162.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20201224103641190.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy80ODQzMTMyLWJhNmZjNDcwYzA0NWZmYTMucG5n?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20201224104302169.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzU2Njgy,size_16,color_FFFFFF,t_70