Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap-白红宇

Java容器源码分析-HashMap vs TreeMap vs LinkedHashMap

阅读量：7208 次

发布时间：2019-06-29

本文共 2185 字，大约阅读时间需要 7 分钟。

这里我采用的分析方式是帖子博客加上自己翻看jdk源码。有些情况下写一些测试的算法小例子加深印象。我这里只描述一下自己的总结想法

上一篇文章我们研究了set接口下的几个容器，由于其Set集合设计时底层的数据模型是Map，Set的实现是基于Map的、所以先搞懂Map、才能去理解Set、否则的话、直接去弄Set会觉得云里雾里、最后发现是浪费时间。这一节介绍关于Map的相关接口、抽象类的功能。

一、Map集合结构体系图（网络图，侵删）

这篇文章主要对TreeMap,HashMap和LinkedHashMap做分析，其他不常用的先不进行分析，另外针对HashTable和ConcurrentHashMap这两个线程安全的Map着重开一章去整理

二、源码分析

1、HashMap源码分析

上帖子：http://www.cnblogs.com/chengxiao/p/6059914.html

总结：

（1）首先重点了解一下哈希表的数据结构，

哈希表（散列）主要利用数组和链表的方式。利用这种方式就可以避免单个数组出现的修改删除的高时间复杂度，又避免了聊表查询的高时间复杂度，具体实现方式请参看上边的博客，具体的讲解了目前的主要数据结构以及哈希表结构

（2）知道了哈希表的数据结构，就能理解HashMap的存储方式了，HashMap就是利用数组+链表的方式进行数据存储。博客中也对主要的添加，删除，修改方法进行了源码详解。在看源码的过程中注意细节

对于hash碰撞是如何处理的，
Hashmap里面的bucket出现了单链表的形式，散列表要解决的一个问题就是散列值的冲突问题，通常是两种方法：链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位；开放地址法是通过一个探测算法，当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式，链表是单向链表。
hash碰撞的产生和解决：http://blog.csdn.net/luo_da/article/details/77507315

hash与hashCode的重写
重写对象的equels必须重写hashCode方法，不然比对后无法识别是不是同一个对象
hashCode重写例子：http://blog.csdn.net/woshixuye/article/details/8189398

2、LinkedHashMap源码分析

发布一个描述LinkedHashMap的博客：http://www.cnblogs.com/chenpi/p/5294077.html

LinkedHashMap也采用数组加链表的方式，只不过LinkedHashMap在散列表基础上多维护了一个有序双向链表，所以LinkedHashMap支持排序。可以按照插入循序排序和访问数序排序
源码分析：http://www.cnblogs.com/chenpi/p/5294077.html

3、TreeMap源码分析

发布一个描述TreeMap的博客：http://www.cnblogs.com/wzyxidian/p/5204879.html

三、区别对比

1、相同点

2、不同点

HashMap存储是无序的，LinkedHashMap可以按照插叙顺序排序，TreeMap按照key的自然排序或者自定义排序（只需要key定制排序Comparator ）

四、总结

三种类型分别在什么时候使用

　　1、一般情况下，我们用的最多的是HashMap。HashMap里面存入的键值对在取出的时候是随机的，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度。在Map 中插入、删除和定位元素，HashMap 是最好的选择。

　　2、TreeMap取出来的是排序后的键值对。但如果您要按自然顺序或自定义顺序遍历键，那么TreeMap会更好。

　 3、LinkedHashMap 是HashMap的一个子类，如果需要输出的顺序和输入的相同,那么用LinkedHashMap可以实现,它还可以按读取顺序来排列，像连接池中可以应用。

转载于:https://my.oschina.net/jiahaov/blog/1553390

你可能感兴趣的文章