LinkedHashMap就这么简单【源码剖析】

亦凉 2021-09-15 05:14 524阅读 0赞

# 前言 #

> 声明，本文用得是jdk1.8

前面已经讲了Collection的总览和剖析List集合以及散列表、Map集合、红黑树还有HashMap基础了：

*  [Collection总览][Collection]
 *  [List集合就这么简单【源码剖析】][List]
 *  [Map集合、散列表、红黑树介绍][Map]
 *  [HashMap就是这么简单【源码剖析】][HashMap]

本篇**主要讲解LinkedHashMap**~

看这篇文章之前最好是有点数据结构的基础：

*  [Java实现单向链表][Java]
 *  [栈和队列就是这么简单][Link 1]
 *  [二叉树就这么简单][Link 2]

当然了，如果讲得有错的地方还请大家多多包涵并不吝在评论去指正～

# 一、LinkedHashMap剖析 #

LinkedHashMap数据结构图：

![ly8oJrh.png][]

ps：图片来源网络，侵删~

首先我们来看看类继承图：

![7RtgQHz.png][]

我简单翻译了一下顶部的注释(我英文水平渣，如果有错的地方请多多包涵~欢迎在评论区下指正)

![w4f7R4U.png][]

从顶部翻译我们就可以归纳总结出HashMap几点：

*  底层是散列表和双向链表
 *  允许为null，不同步
 *  插入的顺序是有序的(底层链表致使有序)
 *  装载因子和初始容量对LinkedHashMap影响是很大的~

同时也给我带了几个疑问：

*  access-ordered和insertion-ordered具体的使用和意思
 *  为什么说初始容量对遍历没有影响？

希望可以在看源码的过程中可以解决掉我这两个疑问~那接下来就开始吧~

## 1.1LinkedHashMap的域 ##

![d7KbmHn.png][]

## 1.2LinkedHashMap重写的方法 ##

下面我列举就这两个比较重要的：

![nWT6GlL.png][]

这就印证了我们的LinkedHashMap\*\*底层确确实实是散列表和双向链表\*\*~

*  在构建新节点时，构建的是`LinkedHashMap.Entry` 不再是`Node`.

## 1.3构造方法 ##

可以发现，LinkedHashMap有**5个构造方法**：

![TIONUtT.png][]

下面我们来看看构造方法的定义是怎么样的：

![K4CoeOK.png][]

从构造方法上我们可以知道的是：**LinkedHashMap默认使用的是插入顺序**

## 1.4put方法 ##

原本我是想要找put方法，看看是怎么实现的，**后来没找着，就奇了个怪**~

![ldzUdNA.png][]

再顿了一下，原来LinkedHashMap和HashMap的put方法是一样的！LinkedHashMap继承着HashMap，LinkedHashMap没有重写HashMap的put方法

所以，LinkedHashMap的put方法和HashMap是一样的。

如果没看过[HashMap就是这么简单【源码剖析】][HashMap]的同学，可进去看看~

当然了，**在创建节点的时候，调用的是LinkedHashMap重写的方法**~

![6xAuYZU.png][]

## 1.5get方法 ##

![TvMRo20.png][]

![yWszu8D.png][]

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);
            }
        }

测试一波：

![MY7s22E.png][]

接着，我们来测试一下以**访问顺序**来进行插入和遍历：

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);
            }
    
        }

代码**看似**是没有问题，但是运行会出错的！

![SPJ88Xm.png][]

前面在看源码注释的时候我们就发现了：**在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 );
            }
    
        }

测试结果：

![LuxPF9J.png][]

以下是**插入顺序的测试**(代码就不贴了，和上面几乎一样)：

![PwGzTij.png][]

我们可以这样理解：**最常用的将其放在链表的最后，不常用的放在链表的最前**~

这个知识点以我的理解而言，它这个**访问顺序在LinkedHashMap如果不重写用处并不大**~它是用来给别的实现进行**扩展**的

*  **因为最常被使用的元素再遍历的时候却放在了最后边，在LinkedHashMap中我也没找到对应的方法来进行调用**~
 *  一个`removeEldestEntry(Map.Entry<K,V> eldest)`方法，**重写它可以删除最久未被使用的元素**！！
 *  还有一个是`afterNodeInsertion(boolean evict)`方法，**新增时判断是否需要删除最久未被使用的元素**！！

![1yfqLcu.png][]

去网上搜了几篇资料，都是讲LRUMap的实现的(也就是对LinkedHashMap进行扩展)，有兴趣的同学可参考下列链接：

*  [https://blog.csdn.net/exceptional\_derek/article/details/11713255][https_blog.csdn.net_exceptional_derek_article_details_11713255]
 *  [http://www.php.cn/java-article-362041.html][http_www.php.cn_java-article-362041.html]
 *  [https://www.jianshu.com/p/1a66529e1a2e][https_www.jianshu.com_p_1a66529e1a2e]
 *  [https://mp.weixin.qq.com/s?\_\_biz=MzI4Njc5NjM1NQ%3D%3D&chksm=ebd639d5dca1b0c3ba5a26bd46d265544f4fdd468df6465e54d93da230c3457d4947e79eaf0c&idx=1&mid=2247485177&sn=93cfa2c2e6f3e5092e5850bdb5ea4cc3][https_mp.weixin.qq.com_s_biz_MzI4Njc5NjM1NQ_3D_3D_chksm_ebd639d5dca1b0c3ba5a26bd46d265544f4fdd468df6465e54d93da230c3457d4947e79eaf0c_idx_1_mid_2247485177_sn_93cfa2c2e6f3e5092e5850bdb5ea4cc3]

## 1.6remove方法 ##

对于remove方法，在LinkedHashMap中也没有重写，它调用的还是父类的HashMap的`remove()`方法，在LinkedHashMap中重写的是：`afterNodeRemoval(Node<K,V> e)`这个方法

![9fEBMci.png][]

当然了，在remove的时候会涉及到上面重写的方法：

![sjDgbOL.png][]

## 1.7遍历的方法 ##

`Set<Map.Entry<K,V>> entrySet()`是被重写的了

![V3N3j1O.png][]

![75epJdR.png][]

看到了这里，我们就知道为啥注释说：**初始容量对遍历没有影响**

因为它遍历的是**LinkedHashMap内部维护的一个双向链表**，而不是散列表(当然了，链表双向链表的元素都来源于散列表)

# 二、总结 #

LinkedHashMap比HashMap多了一个双向链表的维护，在数据结构而言它要复杂一些，阅读源码起来比较轻松一些，因为大多都由HashMap实现了..

阅读源码的时候我们会发现多态是无处不在的~子类用父类的方法，子类重写了父类的**部分**方法即可达到不一样的效果！

*  比如：LinkedHashMap并没有重写put方法，而put方法内部的`newNode()`方法重写了。LinkedHashMap调用父类的put方法，里面回调的是重写后的`newNode()`，从而达到目的！

LinkedHashMap可以设置两种遍历顺序：

*  访问顺序（access-ordered）
 *  插入顺序（insertion-ordered）
 *  **默认是插入顺序的**

对于访问顺序，它是LRU(最近最少使用)算法的实现，要使用它要么**重写LinkedListMap的几个方法**(`removeEldestEntry(Map.Entry<K,V> eldest)`和`afterNodeInsertion(boolean evict)`)，要么是**扩展**成LRUMap来使用，不然设置为访问顺序（access-ordered）的用处不大~

**LinkedHashMap遍历的是内部维护的双向链表**，所以说初始容量对LinkedHashMap遍历是不受影响的

参考资料：

*  《Core Java》
 *  [https://blog.csdn.net/zxt0601/article/details/77429150][https_blog.csdn.net_zxt0601_article_details_77429150]
 *  [https://blog.csdn.net/panweiwei1994/article/details/76555359][https_blog.csdn.net_panweiwei1994_article_details_76555359]
 *  [https://zhuanlan.zhihu.com/p/28216267][https_zhuanlan.zhihu.com_p_28216267]
 *  [https://blog.csdn.net/fan2012huan/article/details/51097331][https_blog.csdn.net_fan2012huan_article_details_51097331]
 *  [https://www.cnblogs.com/chinajava/p/5808416.html][https_www.cnblogs.com_chinajava_p_5808416.html]

--------------------

明天要是无意外的话，可能会写TreeMap，敬请期待哦~~~~

![XwQ6WVq.jpg][]

**文章的目录导航**：[https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang][https_zhongfucheng.bitcron.com_post_shou-ji_wen-zhang-dao-hang]

> 如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以**关注微信公众号:Java3y**。为了大家方便，刚新建了一下**qq群：742919422**，大家也可以去交流交流。谢谢支持了！希望能多介绍给其他有需要的朋友

[Collection]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484122&idx=1&sn=c3bd6436b3e661ae15cb9d7154d82b89&chksm=ebd743dbdca0cacdcb272576f4be48c466bd73160a87227314e8fb21d5e4f9156c23902198ab#rd
[List]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484130&idx=1&sn=4052ac3c1db8f9b33ec977b9baba2308&chksm=ebd743e3dca0caf51b170fd4285345c9d992a5a56afc28f2f45076f5a820ad7ec08c260e7d39#rd
[Map]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484135&idx=1&sn=be2221572ffc82f5792dd4ef1ea8e309&chksm=ebd743e6dca0caf00f188cabafc73665b875bf1cbe92cf3626cedb4f80313bb20a7429b8ec3f#rd
[HashMap]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484139&idx=1&sn=bb73ac07081edabeaa199d973c3cc2b0&chksm=ebd743eadca0cafc532f298b6ab98b08205e87e37af6a6a2d33f5f2acaae245057fa01bd93f4#rd
[Java]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484086&idx=1&sn=24127ceb5e0fed7f832f82579c4fbc19&chksm=ebd743b7dca0caa1dce912d47251548225aa59b4b48742a963ac52b05e13ec923a738ebcb836#rd
[Link 1]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484090&idx=1&sn=d46205eed74e9b253ec08796124192c1&chksm=ebd743bbdca0caad2129f0d76f002b7e14e125900ecac1fa9a3a433e3a9bcd2831275a1e260c#rd
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzI4Njg5MDA5NA==&mid=2247484064&idx=1&sn=ba783e3e83b8007fcdf129ec0839b6c2&chksm=ebd743a1dca0cab7eed0ba42d1c5d343d88858c17e90a803e0ce9e6644187e5297b29ffbb020#rd
[ly8oJrh.png]: https://i.imgur.com/ly8oJrh.png
[7RtgQHz.png]: https://i.imgur.com/7RtgQHz.png
[w4f7R4U.png]: https://i.imgur.com/w4f7R4U.png
[d7KbmHn.png]: https://i.imgur.com/d7KbmHn.png
[nWT6GlL.png]: https://i.imgur.com/nWT6GlL.png
[TIONUtT.png]: https://i.imgur.com/TIONUtT.png
[K4CoeOK.png]: https://i.imgur.com/K4CoeOK.png
[ldzUdNA.png]: https://i.imgur.com/ldzUdNA.png
[6xAuYZU.png]: https://i.imgur.com/6xAuYZU.png
[TvMRo20.png]: https://i.imgur.com/TvMRo20.png
[yWszu8D.png]: https://i.imgur.com/yWszu8D.png
[MY7s22E.png]: https://i.imgur.com/MY7s22E.png
[SPJ88Xm.png]: https://i.imgur.com/SPJ88Xm.png
[LuxPF9J.png]: https://i.imgur.com/LuxPF9J.png
[PwGzTij.png]: https://i.imgur.com/PwGzTij.png
[1yfqLcu.png]: https://i.imgur.com/1yfqLcu.png
[https_blog.csdn.net_exceptional_derek_article_details_11713255]: https://blog.csdn.net/exceptional_derek/article/details/11713255
[http_www.php.cn_java-article-362041.html]: http://www.php.cn/java-article-362041.html
[https_www.jianshu.com_p_1a66529e1a2e]: https://www.jianshu.com/p/1a66529e1a2e
[https_mp.weixin.qq.com_s_biz_MzI4Njc5NjM1NQ_3D_3D_chksm_ebd639d5dca1b0c3ba5a26bd46d265544f4fdd468df6465e54d93da230c3457d4947e79eaf0c_idx_1_mid_2247485177_sn_93cfa2c2e6f3e5092e5850bdb5ea4cc3]: https://mp.weixin.qq.com/s?__biz=MzI4Njc5NjM1NQ%3D%3D&chksm=ebd639d5dca1b0c3ba5a26bd46d265544f4fdd468df6465e54d93da230c3457d4947e79eaf0c&idx=1&mid=2247485177&sn=93cfa2c2e6f3e5092e5850bdb5ea4cc3
[9fEBMci.png]: https://i.imgur.com/9fEBMci.png
[sjDgbOL.png]: https://i.imgur.com/sjDgbOL.png
[V3N3j1O.png]: https://i.imgur.com/V3N3j1O.png
[75epJdR.png]: https://i.imgur.com/75epJdR.png
[https_blog.csdn.net_zxt0601_article_details_77429150]: https://blog.csdn.net/zxt0601/article/details/77429150
[https_blog.csdn.net_panweiwei1994_article_details_76555359]: https://blog.csdn.net/panweiwei1994/article/details/76555359
[https_zhuanlan.zhihu.com_p_28216267]: https://zhuanlan.zhihu.com/p/28216267
[https_blog.csdn.net_fan2012huan_article_details_51097331]: https://blog.csdn.net/fan2012huan/article/details/51097331
[https_www.cnblogs.com_chinajava_p_5808416.html]: https://www.cnblogs.com/chinajava/p/5808416.html
[XwQ6WVq.jpg]: https://i.imgur.com/XwQ6WVq.jpg
[https_zhongfucheng.bitcron.com_post_shou-ji_wen-zhang-dao-hang]: https://zhongfucheng.bitcron.com/post/shou-ji/wen-zhang-dao-hang