Map实现（2）| LinkedHashMap

1. LinkedHashMap的特点

• 有序性：LinkedHashMap可以按照访问顺序（默认）或者插入顺序来排序元素。
• 预测迭代顺序：由于其内部链表的维护，LinkedHashMap可以提供可预测的迭代顺序。
• 性能：提供了与HashMap相似的性能，除了在每次插入时会有轻微的开销用于维护链表顺序。

2. 源码分析

LinkedHashMap内部使用了一个双向链表来维持元素的插入顺序或访问顺序。这个链表和哈希表是同步更新的；每当发生一次访问，链表中对应的节点就会被移动到链表的末尾，这样就确保了链表始终按照访问顺序排列。

2.1 内部结构

LinkedHashMap内部使用一个双向链表来维护一个运行于所有条目上的双链列表。这个链表定义在Entry类内部，每个Entry包含对键、值以及前驱和后继条目的引用。

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    Entry<K,V> before, after;
    ...
}

2.2 插入元素

当向LinkedHashMap中插入新元素时，除了在哈希表中添加键值对之外，还会在双向链表中添加一个新的节点。

2.3 访问元素

每次访问LinkedHashMap中的一个元素时，该元素的对应链表节点会被移到链表的末尾，从而更新其访问顺序。

2.4 删除元素

删除元素时，除了从哈希表中移除键值对，也会从双向链表中移除对应的节点。

3. 适用范围

LinkedHashMap适用于以下场景：

• 有序映射：当你需要保持元素插入的顺序或者访问的顺序时。
• 缓存：可以用作具有自动淘汰策略的缓存实现，通过访问顺序淘汰最老的元素。
• 顺序统计：当需要多次遍历并且关心遍历顺序时，如某些算法的执行步骤记录。

4. 工作原理

LinkedHashMap的工作原理结合了HashMap和双向链表两者的特性：

• 当插入新元素时，它被添加到哈希表和链表的末尾。
• 当元素被访问时，它在链表中的位置会被更新到链表末尾，而其在哈希表中的位置保持不变。
• 当元素被删除时，它将同时从哈希表和链表中移除。

5. 总结

作为HashMap的一个扩展，LinkedHashMap提供了额外的有序性功能，这使其成为需要保持元素排序的映射场景中的理想选择。它的设计允许快速访问和预测的迭代顺序，同时还继承了HashMap高效存储和检索的优点。