源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）

谁借莪１个温暖的怀抱￠ 2023-06-21 07:16 64阅读 0赞

# 1、概述 #

LinkedHashMap容器是Java容器框架中从很早的版本就开始提供的（JDK 1.4+），该容器又被这样认为：“LinkedHashMap = HashMap + LinkedList”。LinkedHashMap容器的主要继承体系如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
LinkedHashMap容器继承自HashMap容器，也就是说前者的基本结构和后者一致，在这样的基本结构下LinkedHashMap容器提供了一个新的特性，就是保证容器内部各个结点可以以一种顺序进行遍历（迭代器支持）：

*  这个顺序可以基于结点添加到容器的时间（insertion-order）：也就是说先添加到容器的K-V键值对对象，在使用LinkedHashMap容器的迭代器进行遍历时，将会首先被遍历。这个遍历顺序和K-V键值对对象属于哪一个桶结构，该桶结构具体是按照单向链表排列的，还是按照红黑树排列的都没有关系。
 *  这个顺序也可以是该结点在容器中最后一次被操作（读操作或写操作）的时间（access-order）：当LinkedHashMap容器指定的K-V键值对对象被进行了操作（无论是修改还是读取操作），它都会被重新排列到遍历结果的最后。

以上两种遍历顺序，完全基于LinkedHashMap容器实例化时的设定参数，我们首先来看一些实际的使用示例：

//......
    // 默认的LinkedHashMap容器将采用K-V键值对的添加顺序（access-order），作为遍历顺序
    LinkedHashMap<String, String> accessOrderMap = new LinkedHashMap<>();
    accessOrderMap.put("key1", "value1");
    accessOrderMap.put("key2", "value2");
    accessOrderMap.put("key3", "value3");
    accessOrderMap.put("key4", "value4");
    accessOrderMap.put("key5", "value5");
    accessOrderMap.put("key6", "value6");
    accessOrderMap.put("key7", "value7");
    accessOrderMap.put("key8", "value8");
    Set<Entry<String, String>> accessOrderSets = accessOrderMap.entrySet();
    System.out.println("//accessOrderSets===================第一次遍历顺序");
    for (Entry<String, String> entry : accessOrderSets) {
        
      System.out.println("current entry : " + entry);
    }
    // 当对某一个键值对的信息进行修改时，不会引起遍历顺序的变化
    accessOrderMap.put("key4", "value44");
    // 这次遍历顺序将与上次遍历顺序一致
    System.out.println("//accessOrderSets===================第二次遍历顺序");
    for (Entry<String, String> entry : accessOrderSets) {
        
      System.out.println("current entry : " + entry);
    }
    
    // 如果使用以下实例化方式的话
    // LinkedHashMap容器将采用K-V键值对的操作顺序（insertion-order），作为遍历顺序
    LinkedHashMap<String, String> insertionOrderMap = new LinkedHashMap<>(16, 0.75f, true);
    insertionOrderMap.put("key1", "value1");
    insertionOrderMap.put("key2", "value2");
    insertionOrderMap.put("key3", "value3");
    insertionOrderMap.put("key4", "value4");
    insertionOrderMap.put("key5", "value5");
    insertionOrderMap.put("key6", "value6");
    insertionOrderMap.put("key7", "value7");
    insertionOrderMap.put("key8", "value8");
    Set<Entry<String, String>> insertionOrderSets = insertionOrderMap.entrySet();
    System.out.println("//insertionOrderSets===================第一次遍历顺序");
    for (Entry<String, String> entry : insertionOrderSets) {
        
      System.out.println("current entry : " + entry);
    }
    // 当对某一个键值对的信息进行修改，就会引起遍历顺序的变化
    insertionOrderMap.put("key4", "value44");
    // 对某一个键值对信息进行读取操作，同样会引起遍历顺序的变化
    insertionOrderMap.get("key7");
    // 这次遍历顺序将与上次遍历顺序不一致
    System.out.println("//insertionOrderSets===================第二次遍历顺序");
    for (Entry<String, String> entry : insertionOrderSets) {
        
      System.out.println("current entry : " + entry);
    }
    //......

以下为输出结果：

//accessOrderSets===================第一次遍历顺序
    current entry : key1=value1
    current entry : key2=value2
    current entry : key3=value3
    current entry : key4=value4
    current entry : key5=value5
    current entry : key6=value6
    current entry : key7=value7
    current entry : key8=value8
    //accessOrderSets===================第二次遍历顺序
    current entry : key1=value1
    current entry : key2=value2
    current entry : key3=value3
    current entry : key4=value44
    current entry : key5=value5
    current entry : key6=value6
    current entry : key7=value7
    current entry : key8=value8
    //insertionOrderSets===================第一次遍历顺序
    current entry : key1=value1
    current entry : key2=value2
    current entry : key3=value3
    current entry : key4=value4
    current entry : key5=value5
    current entry : key6=value6
    current entry : key7=value7
    current entry : key8=value8
    //insertionOrderSets===================第二次遍历顺序
    current entry : key1=value1
    current entry : key2=value2
    current entry : key3=value3
    current entry : key5=value5
    current entry : key6=value6
    current entry : key8=value8
    current entry : key4=value44
    current entry : key7=value7

以上代码输出结果的意义就不再赘述了。下面我们就来详细LinkedHashMap容器的源码原理，先从LinkedHashMap容器结点的结构开始介绍。

## 1.1、LinkedHashMap容器结点结构 ##

![在这里插入图片描述][20191216192239495.png]  
如上图所示，是LinkedHashMap容器中构造每个结点所使用的LinkedHashMap.Entry的继承体系。从上图我们就知道了LinkedHashMap.Entry继承自HashMap.Node，再结合LinkedHashMap.Entry类源代码中各属性的描述，我们可以知道LinkedHashMap容器中每一个结点具有哪些属性了。结点的定义代码如下所示：

// HashMap.Node结点的属性定义，上文已经介绍过了，这里就不再进行赘述了
    static class Node<K,V> implements Map.Entry<K,V> {
        
      final int hash;
      final K key;
      V value;
      // next属性，保证了HashMap容器在进行红黑树到链表的转换过程中，提高转换效率
      Node<K,V> next;
    }

// TreeNode结点的属性在上文中也已经介绍过了
    // 当HashMap中某个桶结构为红黑树时，使用这样的结点定义
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        
      // 记录了当前红黑树结点父结点
      TreeNode<K,V> parent; 
      // 记录了当前红黑树结点的左儿子结点
      TreeNode<K,V> left;
      // 记录了当前红黑树结点的右儿子结点
      TreeNode<K,V> right;
      // 这是红黑树结构中隐含的一个双向链表结构
      // 该属性记录了单向链表向红黑树转换后，记录的前置结点
      TreeNode<K,V> prev;
      // 该属性表示当前结点是红色还是黑色
      boolean red;
    }

static class Entry<K,V> extends HashMap.Node<K,V> {
        
      // LinkedHashMap容器中的结点可以互相引用连接起来，变成一个双向链表
      // 该属性记录了当前LinkedHashMap容器中，双向链表的前一个结点；
      Entry<K,V> before;
      // 该属性记录了当前LinkedHashMap容器中，双向链表的后一个结点；
      Entry<K,V> after;
    }

下图进一步说明了LinkedHashMap容器中的每一个结点拥有的各个属性，注意要分为两种情况考虑：如果当前LinkedHashMap容器中指定的位置（table数组的某个索引位）的桶结构存储的是单向链表，那么对应的结点结构如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]  
如果LinkedHashMap容器中指定的桶位置存储的是红黑树结构，那么对应的结点结构如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]

## 1.2、LinkedHashMap容器整体构造 ##

分析完LinkedHashMap容器中每个K-V键值对对象属性的扩展后，我们再来看看LinkedHashMap容器定义层面上又做了哪些扩展。以下代码片段示意了LinkedHashMap容器扩展的属性内容：

// LinkedHashMap容器的基本属性定义
    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
        
      // ......
      /**
       * 双向链表的头结点引用
       * The head (eldest) of the doubly linked list.
       */
      transient LinkedHashMap.Entry<K,V> head;
      /**
       * 双向链表的尾结点应用，根据上文提到的LinkedHashMap容器的构造设定
       * 这里的尾结点可能是最后添加到LinkedHashMap容器的结点，也可能是LinkedHashMap容器中被最新访问的结点
       * The tail (youngest) of the doubly linked list.
       */
      transient LinkedHashMap.Entry<K,V> tail;
      /**
       * 该属性表示LinkedHashMap容器中特有的双向链表总结点的排序特点。
       * 如果为false（默认为false），将按照结点被添加到LinkedHashMap容器的顺序进行排序；
       * 如果为true，将按照结点最近被操作（修改操作或者读取操作）的顺序进行排序
       */
      final boolean accessOrder;
      // ......
    }

除了以上LinkedHashMap容器的属性定义外，由于LinkedHashMap容器和HashMap容器的继承关系，前者当然也就具有了后者的属性定义，例如HashMap容器中用于存储桶结构的数组变量table。我们可以用以下示例图描述一个LinkedHashMap容器的结点存储效果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]  
通过LinkedHashMap容器中每个结点的before、after属性形成的双向链表，将串联上容器中的所有结点；**这些结点在双向链表中的顺序和这些结点处于哪一个桶结构中，桶结构本身是单向链表结构还是红黑树结构并没有关系，有关系的只是这个结点代表的K-V键值对在时间维度上被添加到LinkedHashMap容器中的顺序**。

通过LinkedHashMap容器层面的head属性和tail属性，保证了被串联的结点可以跨越不同的桶结构。请注意根据LinkedHashMap容器的初始化设定，head属性和tail属性指向的节点是可能会发生变化的。

============  
（接后文《源码阅读(24)：Java中其它主要的Map结构——LinkedHashMap容器（下）》）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191216201428105.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[20191216192239495.png]: https://img-blog.csdnimg.cn/20191216192239495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191216195531892.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191216200150618.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191216210722568.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70