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

落日映苍穹つ 2023-06-23 14:29 19阅读 0赞

（接上文《[源码阅读(23)：Java中其它主要的Map结构——LinkedHashMap容器（上）][23_Java_Map_LinkedHashMap]》）

# 2、LinkedHashMap容器主要操作 #

## 2.1、LinkedHashMap容器的实例化方式 ##

LinkedHashMap容器一共有5个构造函数，除了和HashMap容器基本一致的4个构造函数以外，还有一个可以设定accessOrder排序模式的构造函数。下面本文对这几个构造函数进行描述，注意accessOrder属性的意义已经在上文中介绍过，这里就不再赘述了。

// 默认的构造函数
    // super()将调用继承的父类HashMap的对应构造函数
    // 使用默认构造函数，将支持insertion-order模式的迭代器遍历操作
    public LinkedHashMap() {
        
      super();
      accessOrder = false;
    }
    
    // 该构造函数将可以设定初始的桶大小，请注意，并不是initialCapacity值和桶大小的关系在本专题介绍HashMap容器时，已经说明
    // 愿意了解的读者可以参见前文。
    // loadFactor为负载因子
    // 使用该构造函数，将支持insertion-order模式的迭代器遍历操作
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        
      super(initialCapacity, loadFactor);
      accessOrder = false;
    }
    
    // 该构造函数将可以通过initialCapacity值设定桶大小
    // loadFactor负载因子
    // 该构造函数还可以设置LinkedHashMap容器的迭代器遍历操作模式，为true时，将采用access-order模式
    // 其它情况下将采用insertion-order模式
    public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder;
    }
    
    // 该构造函数将可以通过initialCapacity值设定桶大小
    // 使用该构造函数，将支持insertion-order模式的迭代器遍历操作
    public LinkedHashMap(int initialCapacity) {
        
      super(initialCapacity);
      accessOrder = false;
    }
    
    // 该构造函数将可以传入其它构造形式的K-V键值对集合。
    // 并将这些K-V键值对对象作为当前LinkedHashMap容器中的初始K-V键值对对象
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        
      super();
      accessOrder = false;
      putMapEntries(m, false);
    }

以上构造函数的过程都很好理解，这里我们在详细介绍一下putMapEntries(Map)这个方法。该方法实际上是HashMap容器中的方法，它不止在构造函数中被调用，还在诸如putAll(Map)这样的方法中被调用：

// 注意，传入的map容器不能为null
    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        
      // 参照集合的当前大小赋值给s
      int s = m.size();
      
      if (s > 0) {
        
        // 当在LinkedHashMap/HashMap容器的构造函数中调用putMapEntries方法时，table就是为null
        // 这个时候就初始化LinkedHashMap/HashMap容器的容量
        // 注意其中的threshold变量，这是一个全局变量，主要指容器下一次应该扩容的大小
        if (table == null) {
         
          float ft = ((float)s / loadFactor) + 1.0F;
          int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
          // 这个条件当在LinkedHashMap/HashMap容器的构造函数中调用putMapEntries方法时，一定是成立的，
          // 因为threshold变量的值为0
          if (t > threshold)
            threshold = tableSizeFor(t);
        }
        // 如果条件成立，说明当前LinkedHashMap/HashMap容器已经存储了一些K-V键值对对象
        // 并且当前需要新增加到容器的参考集合的大小，已经大于了LinkedHashMap/HashMap容器下一次应该扩容的大小
        // 所以在新增前，需要进行LinkedHashMap/HashMap容器的扩容操作
        else if (s > threshold)
          resize();
        
        // 准备好所需要的LinkedHashMap/HashMap容器空间后，
        // 就是用putVal方法，将参考集合中的对象一个一个添加到当期的LinkedHashMap/HashMap容器中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
        
          K key = e.getKey();
          V value = e.getValue();
          putVal(hash(key), key, value, false, evict);
        }
      }
    }

通过以上的描述，我们知道了LinkedHashMap容器的构造函数，基本上基于HashMap容器的构造函数进行扩展，理解难度不大。

## 2.2、LinkedHashMap容器的迭代器 ##

LinkedHashMap容器的源代码中，实际上定义了多种迭代器，这完全是因为LinkedHashMap容器根据不同的调用要求，可以提供多种不同的迭代方式——可以按照容器中K-V键值对对象的key信息进行迭代器遍历；可以按照容器中K-V键值对对象的value信息进行迭代器遍历；还可以按照容器中K-V键值对对象直接进行迭代器遍历

*  获取容器中K-V键值对对象的key信息集合，并取得迭代器

// ......
    // 该方法用于获取key信息集合
    public Set<K> keySet() {
        
      // keySet是由AbstractMap类定义的全局变量
      // 用来指向当前已经实例化的key信息集合
      Set<K> ks = keySet;
      // 如果当前keySet没有值，则生成一个LinkedKeySet的实例
      if (ks == null) {
        
        ks = new LinkedKeySet();
        keySet = ks;
      }
      return ks;
    }
    
    // 以下是LinkedKeySet类的主要定义。
    final class LinkedKeySet extends AbstractSet<K> {
        
      // key信息集合的大小
      public final int size() {
         return size; }
      // ......  
    
      // 获取一个LinkedKeyIterator实例的迭代器
      public final Iterator<K> iterator() {
        
        return new LinkedKeyIterator();
      }
      // ......
      
      // 通过该方法，可以调用当前的key信息删除当前容器中对应的K-V键值对信息
      // 这个方法实际上是调用的HashMap父类中的removeNode方法
      public final boolean remove(Object key) {
        
        return removeNode(hash(key), key, null, false, true) != null;
      }
      // ......
      
      // Set.forEach
      public final void forEach(Consumer<? super K> action) {
        
        if (action == null)
          throw new NullPointerException();
        int mc = modCount;
        for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
          action.accept(e.key);
        if (modCount != mc)
          throw new ConcurrentModificationException();
      }
    }
    
    // LinkedHashMap容器中，基于K-V键值对对象的key信息集合工作的迭代器，
    final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> {
        
      public final K next() {
         return nextNode().getKey(); }
    }

由此我们可以看出LinkedHashMap容器中主要的迭代器实现逻辑是在LinkedHashIterator子类中——这个子类本身并没有实现Iterator接口，但是它将LinkedHashMap容器中多个种类迭代器的共性放在了一起。以下是该子类的定义：

abstract class LinkedHashIterator {
        
      // 该变量指向当前迭代结点的下一个结点
      LinkedHashMap.Entry<K,V> next;
      // 该变量指向当前迭代器正在处理的结点
      LinkedHashMap.Entry<K,V> current;
      int expectedModCount;
      
      // 请注意LinkedHashIterator 的构造函数
      LinkedHashIterator() {
        
        // 全局变量head，来自于当前的的LinkedHashMap容器实例，它代表了LinkedHashMap容器中存在的全局双向链表的开始结点
        next = head;
        // 全局变量modCount，来自于当前的LinkedHashMap容器实例，它代表当前LinkedHashMap容器实例被进行写操作的次数
        expectedModCount = modCount;
        current = null;
      }
      
      // 如果next变量不为空，都认为有下一个迭代要处理的结点
      public final boolean hasNext() {
        
        return next != null;
      }
    
      // 该方法获取迭代器中下一个要处理的结点
      final LinkedHashMap.Entry<K,V> nextNode() {
        
        // 这个局部变量e，就是要被返回的
        LinkedHashMap.Entry<K,V> e = next;
        // 如果条件成立，说明当前LinkedHashMap容器实例在遍历过程中，被额外进行了写操作处理
        // 这个写操作可能是当前线程执行的，也可能是其它线程执行的
        // 但这是不被允许的（除非写操作也同时变更了expectedModCount的记录值），因为这很可能会更改结点应有的迭代顺序
        if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
        // 如果当前迭代器中没有了还可以遍历处理的节点，则也要抛出异常
        if (e == null)
          throw new NoSuchElementException();
        current = e;
        // 将当前结点中after属性应用的结点作为下一个要处理的结点，引用给next变量
        next = e.after;
        return e;
      }
      // ......
    }

基于这样的介绍，我们可以得到LinkedHashMap容器中三种迭代器获取场景的类图结构：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]  
如上图所示：无论是根据LinkedHashMap容器中K-V键值对对象的key信息获取迭代器，还是按照容器中K-V键值对对象的value信息获取迭代器，又或者是按照容器中K-V键值对对象直接获取迭代器，它们的获取方式都可以得到一个特定类型的Set集合（或其它容器），并且这个特定类型的Set集合（或其它容器）都依赖了一种特定工作模式的Iterator迭代器定义方式。**而多种特定工作模式的Iterator迭代器，其基本工作原理基本类似，差异只在于其next()方法的实现细节上**。接下来我们大致给出这些不同的代码逻辑差异，如下所示：

*  获取容器中K-V键值对对象的value信息集合，并取得迭代器

public Collection<V> values() {
        
      Collection<V> vs = values;
      // 如果条件成比例，则实例化一个LinkedValues类的对象。
      // 和keys()方法中实例化LinkedKeySet类的对象的场景类似
      if (vs == null) {
        
        vs = new LinkedValues();
        values = vs;
      }
      return vs;
    }
    
    // 以下是LinkedValues类的定义，其基本逻辑与LinkedKeySet类中的逻辑类似
    // 不同的是它继承了AbstractCollection类
    final class LinkedValues extends AbstractCollection<V> {
        
      public final int size() {
         return size; }
      public final void clear() {
         LinkedHashMap.this.clear(); }
      // LinkedValues类中获取的迭代器是LinkedValueIterator类的实例。
      public final Iterator<V> iterator() {
        
        return new LinkedValueIterator();
      }
      // ......
      
      public final void forEach(Consumer<? super V> action) {
        
        // ......
      }
    }
    
    // 以下是LinkedValueIterator类的定义，和LinkedKeyIterator类定义不同的是
    // 前者next()方法中返回的是迭代器当前遍历结点的value值
    final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> {
        
      public final V next() {
         return nextNode().value; }
    }

*  按照容器中K-V键值对对象获取迭代器

public Set<Map.Entry<K,V>> entrySet() {
        
      Set<Map.Entry<K,V>> es;
      return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
    }
    
    final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
        
      public final int size() {
         return size; }
      public final void clear() {
         LinkedHashMap.this.clear(); }
      public final Iterator<Map.Entry<K,V>> iterator() {
        
        // 这里创建了LinkedEntryIterator类的实例
        return new LinkedEntryIterator();
      }
      
      // ......
      
      public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
        
        // ......
      }
    }
    
    // 以下是LinkedValueIterator类的定义
    final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> {
        
      public final Map.Entry<K,V> next() {
         return nextNode(); }
    }

[23_Java_Map_LinkedHashMap]: https://yinwj.blog.csdn.net/article/details/103493843
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020010518395397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95aW53ai5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70