Java 源码系列 3——LinkedHashMap
什么是LinkedHashMap?
LinkedHashMap
是 HashMap
的有序实现。LinkedHashMap
用一条双向链表来维护顺序,迭代的时候也使用自己实现的迭代器。
输出
底层数组结构
HashMap的底层是由数组,链表,红黑树组成的。数组用来存储节点,当出现哈希碰撞时使用链表存储,当链表超过一定长度后会优化成红黑树。
LinkedHashMap 的底层除了继承自 HashMap 的数组,链表,红黑树,还多了链接所有节点的双向链表(图中红色和绿色箭头),用于存储各个节点的顺序。
Entry的继承关系
LinkedHashMap.Entry
继承了 HashMap.Node
,多维护了 before 和 after 两个指针,这两个属性指向该Entry的前一个Entry和后一个Entry,也就是那条用于存储顺序的双向链表。
但是 LinkedHashMap 中确没有覆写 HashMap 中 TreeNode 的代码,那红黑树中各个节点的顺序是如何存储的。
我们可以从 HashMap.TreeNode
的继承关系中找出端倪:
呦吼,这一小家子也真够乱的,子类继承了父类的内部类,父类的内部类又继承了子类的内部类,上演一出鸡生蛋,蛋生鸡的戏码。
为什么 HashMap.TreeNode
要继承 LinkedHashMap.Entry
,继承过来的 before 和 after 指针在 HashMap 中也没有被用到,何不直接继承 HashMap.Node
?
这样的继承关系其实并不是为 HashMap 设计的,在 HashMap 中确实没什么用。但在 LinkedHashMap 中,就可以直接使用继承过来的 HashMap.TreeNode
,因为 TreeNode 这个类通过继承已经拥有了 before 和 after 指针。
这就是为什么,LinkedHashMap
中有一个继承了 HashMap.Node
的内部类,却没有继承 HashMap.TreeNode
的内部类。
链表的创建过程
链表的创建过程是在第一个元素插入的时候才开始的,一开始链表的头部(head)和尾巴(tail)都为null。
LinkedHashMap
没有覆写父类的put方法,元素的插入流程基本相同,只是 HashMap
插入的是 Node
类型的节点,LinkedHashMap
插入的是 Entry
类型的节点,并且更新链表。
那么 LinkedHashMap
是怎么插入节点,并且更新链表的呢?
从代码里可以很明显的看出,LinkedHashMap 中索引的计算,桶的赋值,哈希碰撞时链表或者红黑树的创建,都使用的 HashMap 的实现。LinkedHashMap 只需要覆写节点的创建,并且在创建节点的时候,更新储存顺序的链表。真的是把复用利用到了极致。
节点的删除
与插入操作一样,LinkedHashMap 也是使用的父类的删除操作,然后覆写了回调方法 afterNodeRemoval
,用于维护双向链表。
访问顺序的维护
如果我们在初始化 LinkedHashMap 时,把 accessOrder 参数设为 true,那么我们不仅在插入的时候会维护链表,在访问节点的时候也会维护链表。
当我们调用 get, getOrDefault, replace
等方法时,会更新链表,把访问的节点移动到链表尾部。
使用测试代码体验一下效果
竟然报错了
看一下 LinkedHashMap 覆写的迭代器代码
ConcurrentModificationException
这个报错是为了防止并发条件下,遍历的同时链表发生变化。因为我们在遍历的时候又调用了 get 方法,导致链表发生变化,才会抛这个错。
accessOrder 为 true 时的正确遍历姿势如下,使用 LinkedHashMap 覆写forEach
方法,就不会在读取值的时候修改顺序链表了。
使用 LinkedHashMap 实现简单的 LRU
LRU 全称 Least Recently Used,也就是最近最少使用的意思,是一种内存管理算法,该算法最早应用于 Linux 操作系统。
这个算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大。因此,当数据所占内存达到一定阈值时,我们要移除最近最少被使用的数据。
下面我们介绍一下前置知识。
afterNodeInsertion
是一个回调方法,在插入元素的时候回调。LinkedHashMap 覆写了这个方法,主要用来判断是否需要将链表的 head 移除。
下面我们将继承 LinkedHashMap,通过覆写 removeEldestEntry
,达到当 Map 的节点个数超过指定阈值时,删除最少访问的节点。从而实现 LRU 缓存策略。
测试结果如下:
总结
本文围绕 LinkedHashMap 如何维护存储顺序的双向链表展开,介绍了 LinkedHashMap 和 HashMap 节点类的继承关系,介绍了新增,删除,访问时,LinkedHashMap 如何在复用 HashMap 的同时,维护双向链表。最后通过继承 LinkedHashMap 很简单的实现了 LRU 缓存策略。
全文的代码量较多,但都较为好理解。理解JDK的设计思路,探寻背后的实现原理,也是一件很有趣的事。
本文讨论的源代码都基于JDK1.8版本。
参考资料
【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解
源码系列文章
Java源码系列4——HashMap扩容时究竟对链表和红黑树做了什么?
本文首发于我的个人博客 https://chaohang.top
作者张小超
转载请注明出处
欢迎关注我的微信公众号 【超超不会飞】,获取第一时间的更新。
版权声明: 本文为 InfoQ 作者【超超不会飞】的原创文章。
原文链接:【http://xie.infoq.cn/article/58212e9843f2418d0ae83fc9f】。文章转载请联系作者。
评论