声明,本文用得是jdk1.8
前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树还有HashMap基础了:
本篇 主要讲解LinkedHashMap ~
看这篇文章之前最好是有点数据结构的基础:
当然了,如果讲得有错的地方还请大家多多包涵并不吝在评论去指正~
LinkedHashMap数据结构图:
ps:图片来源网络,侵删~
首先我们来看看类继承图:
我简单翻译了一下顶部的注释(我英文水平渣,如果有错的地方请多多包涵~欢迎在评论区下指正)
从顶部翻译我们就可以归纳总结出HashMap几点:
同时也给我带了几个疑问:
希望可以在看源码的过程中可以解决掉我这两个疑问~~~那接下来就开始吧~~~
下面我列举就这两个比较重要的:
这就印证了我们的LinkedHashMap 底层确确实实是散列表和双向链表 ~
LinkedHashMap.Entry
不再是 Node
. 可以发现,LinkedHashMap有 5个构造方法 :
下面我们来看看构造方法的定义是怎么样的:
从构造方法上我们可以知道的是: LinkedHashMap默认使用的是插入顺序
原本我是想要找put方法,看看是怎么实现的, 后来没找着,就奇了个怪 ~
再顿了一下,原来LinkedHashMap和HashMap的put方法是一样的!LinkedHashMap继承着HashMap,LinkedHashMap没有重写HashMap的put方法
所以,LinkedHashMap的put方法和HashMap是一样的。
如果没看过 HashMap就是这么简单【源码剖析】 的同学,可进去看看~
当然了, 在创建节点的时候,调用的是LinkedHashMap重写的方法 ~
get方法也是多了: 判断是否为访问顺序 ~~~
讲到了这里,感觉我们可以简单测试一波了:
首先我们来看看已 插入顺序 来进行插入和遍历:
public static void insertOrder() { // 默认是插入顺序 LinkedHashMap<Integer,String> insertOrder = new LinkedHashMap(); String value = "关注公众号Java3y"; int i = 0; insertOrder.put(i++, value); insertOrder.put(i++, value); insertOrder.put(i++, value); insertOrder.put(i++, value); insertOrder.put(i++, value); //遍历 Set<Integer> set = insertOrder.keySet(); for (Integer s : set) { String mapValue = insertOrder.get(s); System.out.println(s + "---" + mapValue); } }
测试一波:
接着,我们来测试一下以 访问顺序 来进行插入和遍历:
public static void accessOrder() { // 设置为访问顺序的方式 LinkedHashMap<Integer,String> accessOrder = new LinkedHashMap(16, 0.75f, true); String value = "关注公众号Java3y"; int i = 0; accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); // 遍历 Set<Integer> sets = accessOrder.keySet(); for (Integer key : sets) { String mapValue = accessOrder.get(key); System.out.println(key + "---" + mapValue); } }
代码 看似 是没有问题,但是运行会出错的!
前面在看源码注释的时候我们就发现了: 在AccessOrder的情况下,使用get方法也是结构性的修改 !
为了简单看出他俩的区别,下面我就 直接用key来进行看了 ~
以下是 访问顺序的测试 :
public static void accessOrder() { // 设置为访问顺序的方式 LinkedHashMap<Integer,String> accessOrder = new LinkedHashMap(16, 0.75f, true); String value = "关注公众号Java3y"; int i = 0; accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); accessOrder.put(i++, value); // 访问一下key为3的元素再进行遍历 accessOrder.get(3); // 遍历 Set<Integer> sets = accessOrder.keySet(); for (Integer key : sets) { System.out.println(key ); } }
测试结果:
以下是 插入顺序的测试 (代码就不贴了,和上面几乎一样):
我们可以这样理解: 最常用的将其放在链表的最后,不常用的放在链表的最前 ~
这个知识点以我的理解而言,它这个 访问顺序在LinkedHashMap如果不重写用处并不大 ~它是用来给别的实现进行 扩展 的
removeEldestEntry(Map.Entry<K,V> eldest)
方法, 重写它可以删除最久未被使用的元素 !! afterNodeInsertion(boolean evict)
方法, 新增时判断是否需要删除最久未被使用的元素 !!
去网上搜了几篇资料,都是讲LRUMap的实现的(也就是对LinkedHashMap进行扩展),有兴趣的同学可参考下列链接:
对于remove方法,在LinkedHashMap中也没有重写,它调用的还是父类的HashMap的 remove()
方法,在LinkedHashMap中重写的是: afterNodeRemoval(Node<K,V> e)
这个方法
当然了,在remove的时候会涉及到上面重写的方法:
Set<Map.Entry<K,V>> entrySet()
是被重写的了
看到了这里,我们就知道为啥注释说: 初始容量对遍历没有影响
因为它遍历的是 LinkedHashMap内部维护的一个双向链表 ,而不是散列表(当然了,链表双向链表的元素都来源于散列表)
LinkedHashMap比HashMap多了一个双向链表的维护,在数据结构而言它要复杂一些,阅读源码起来比较轻松一些,因为大多都由HashMap实现了..
阅读源码的时候我们会发现多态是无处不在的~子类用父类的方法,子类重写了父类的 部分 方法即可达到不一样的效果!
newNode()
方法重写了。LinkedHashMap调用父类的put方法,里面回调的是重写后的 newNode()
,从而达到目的! LinkedHashMap可以设置两种遍历顺序:
对于访问顺序,它是LRU(最近最少使用)算法的实现,要使用它要么 重写LinkedListMap的几个方法 ( removeEldestEntry(Map.Entry<K,V> eldest)
和 afterNodeInsertion(boolean evict)
),要么是 扩展 成LRUMap来使用,不然设置为访问顺序(access-ordered)的用处不大~
LinkedHashMap遍历的是内部维护的双向链表,所以说初始容量对LinkedHashMap遍历是不受影响的
参考资料:
明天要是无意外的话,可能会写TreeMap,敬请期待哦
文章的目录导航 : https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang
如果文章有错的地方欢迎指正,大家互相交流。习惯在微信看技术文章,想要获取更多的Java资源的同学,可以 关注微信公众号:Java3y 。为了大家方便,刚新建了一下 qq群:742919422 ,大家也可以去交流交流。谢谢支持了!希望能多介绍给其他有需要的朋友