【Java容器源码】LinkedHashMap 基于链表的迭代器源码分析

朴灿烈づ我的快乐病毒、 2022-10-31 00:54 142阅读 0赞

> 前篇：[【Java容器源码】LinkedHashMap 实现 LRU 策略源码分析][Java_LinkedHashMap _ LRU]

在上一篇文章，我们说了，LinkedHashMap 继承自 HashMap，而 HashMap 提供了基于**逐桶遍历**策略的 KeyIterator、ValueIterator、EntryIterator，来分别对 key、value、entry 进行迭代（可以参考[这篇文章][Link 1]）。

而 LinkedHashMap 除了哈希表之外，还有一条贯穿了所有结点双向链表，所以，它重写了获取迭代器的三个方法，返回基于**链表遍历**策略的迭代器。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]

*  迭代 key：LinkedHashMap\#keySet()–> LinkedKeySet\#iterator()–> LinkedKeyIterator
 *  迭代 value：LinkedHashMap\#values()–> LInkedValues\#iterator()–> LinkedValueIterator
 *  迭代 entry：LinkedHashMap\#entrySet()–> LinkedEntrySet\#iterator()–> LinkedEntryIterator

我们下面来看看这些 Linked~~Iterator 到底是什么样子。

### Linked~~Iterator ###

final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        
        public final K next() {
         return nextNode().getKey(); } // 调用父类nextNode方法，返回node中的Key
    }
    
    final class LinkedValueIterator extends LinkedHashIterator
        implements Iterator<V> {
        
        public final V next() {
         return nextNode().value; } // 调用父类nextNode方法，返回node中的value
    }
    
    final class LinkedEntryIterator extends LinkedHashIterator
        implements Iterator<Map.Entry<K,V>> {
        
        public final Map.Entry<K,V> next() {
         return nextNode(); } // 调用父类nextNode方法，直接返回node
    }

可以看到，虽然是不同的迭代器，但是它们本质上却没有区别：

1.  都继承了 LinkedHashIterator
2.  都只有一个方法：next()，而且里面调用的都是 LinkedHashIterator.nextNode()，只不过最后在node中取值不同

我们下面就来看看 LinkedHashIterator。

### LinkedHashIterator ###

abstract class LinkedHashIterator {
        
         
            LinkedHashMap.Entry<K,V> next; // 下一个节点
            LinkedHashMap.Entry<K,V> current; // 当前节点
            int expectedModCount;  // 目标操作数（即开始迭代前的操作数）
    
            // 初始化时，默认从头节点开始访问
            LinkedHashIterator() {
        
                next = head;
                expectedModCount = modCount;
                current = null;
            }
         	
         	// 核心方法nextNode()，根据链表进行迭代！！
         	final LinkedHashMap.Entry<K,V> nextNode() {
        
                LinkedHashMap.Entry<K,V> e = next;
                // 校验 如果迭代过程中对Map进行操作，报错
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                if (e == null)
                    throw new NoSuchElementException();
                current = e;
                // 通过链表的 after 结构，找到下一个迭代的节点
                next = e.after; 
                return e;
    		}
    }

LinkedHashIterator 和 HashIterator 的比较

1.  不同点：nextNode方法，也即迭代策略
    
     *  HashIterator的迭代策略是：逐桶遍历，可理解成外层是遍历数组，内层是遍历链表（红黑树）
     *  LinkedHashIterator：只用按照链表从头到尾遍历所有node即可
2.  相同点：hasNext方法和remove方法完全相同，所以下面代码也就没有列举这两个方法

**总结，对于 LinkedHashMap而言，它继承了HashMap，但它没有使用 HashMap 的逐桶遍历迭代器，而是自己重写了基于链表遍历的迭代器。**

[Java_LinkedHashMap _ LRU]: https://blog.csdn.net/weixin_43935927/article/details/108512608
[Link 1]: https://blog.csdn.net/weixin_43935927/article/details/113885561
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/890c8f7fa6674da881c2e91cf9888c95.png