前篇：【Java容器源码】LinkedHashMap 实现 LRU 策略源码分析

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

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

• 迭代 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 的逐桶遍历迭代器，而是自己重写了基于链表遍历的迭代器。