写在前面
- 由于个人水平有限,故部分内容可能会出现错误,还请包涵
LinkedHashMap
1 | public class LinkedHashMap<K,V> |
LinkedHashMap 在 HashMap 的基础上,通过一个双向链表来维护 Map 中节点的顺序,在每次插入数据,或者访问、修改数据时,会增加节点、或调整链表的节点顺序。以决定迭代时输出的顺序
LinkedHashMap 内存放的节点元素定义如下
1 | // next 用于维护 HashMap 各个桶中 Entry 的连接顺序 |
同时类中有两个属性 head 和 tail,分别指向内部双向链表的头和尾
1 | // The head (eldest) of the doubly linked list. |
默认情况,遍历时的顺序是按照插入节点的顺序。这也是其与 HashMap(HashMap 遍历的方式是按数组的方式依次遍历 table 中的元素,然后再以链表或红黑树的方式遍历 table 中的单个元素) 最大的区别
也可以在构造时传入 accessOrder (值为 true 时,表示按照访问顺序迭代;值为 false 时,表示按照插入顺序迭代)参数,使得其遍历顺序按照访问的顺序输出,默认为 false
LinkedHashMap 的一个重要应用就是实现 LRU(Least Recently Used)算法,是一种缓存技术,在 LRU 算法中,会将 accessOrder 设为 true
put
LinkedHashMap 中并没有重写 put 方法,而是重写了生成新节点的 newNode 方法,newNode 方法最终会被 put 方法调用
1 | Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { |
在每次构建新节点(即调用 newNode 方法)时,通过 linkNodeLast(p) 方法将新节点链接在内部双向链表的尾部
1 | // 普通的将元素链接在链表尾部的方法,没什么好分析的 |
同时 HashMap 中为 LinkedHashMap 预定义了三个用于维护内部链表的方法
1 | // Callbacks to allow LinkedHashMap post-actions |
在这里我们先分析 afterNodeAccess
和 afterNodeInsertion
1 | // 将当前访问的节点移至内部链表尾部 |
1 | void afterNodeInsertion(boolean evict) { // possibly remove eldest |
remove
同样的,LinkedHashMap 中也没有重写 remove 方法,而是通过重写 afterNodeRemoval
方法来变相地实现 remove 重写
1 | // 简单的删除链表中某个节点 |
get
在 LinkedHashMap 重写了 get 方法,不过主要流程和 HashMap 中差不多,区别在于在其中加入了维护链表的功能,若 accessOrder
为 false,则和 HashMap 的 get 方法一致
1 | public V get(Object key) { |
值得注意的是,afterNodeAccess() 函数中,会修改 modCount,因此当你正在 accessOrder=true 的模式下,迭代 LinkedHashMap 时,如果同时查询访问数据,也会导致 fail-fast
,因为迭代的顺序已经改变
遍历
LinkedHashMap 重写了 entrySet 方法,通过遍历内部链表的方式来遍历 LinkedHashMap,而遍历内部链表则是通过 LinkedEntryIterator
1 | final class LinkedEntryIterator extends LinkedHashIterator |
而 LinkedHashIterator 则是 LinkedHashMap 中的一个内部抽象类
1 | abstract class LinkedHashIterator { |