第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同？
杨晓峰
该思维导图由 AI 生成，仅供参考
Map 是广义 Java 集合框架中的另外一部分，HashMap 作为框架中使用频率最高的类型之一，它本身以及相关类型自然也是面试考察的热点。
今天我要问你的问题是，对比 Hashtable、HashMap、TreeMap 有什么不同？谈谈你对 HashMap 的掌握。
典型回答
Hashtable、HashMap、TreeMap 都是最常见的一些 Map 实现，是以键值对的形式存储和操作数据的容器类型。
HashMap 是应用更加广泛的哈希表实现，行为上大致上与 HashTable 一致，主要区别在于 HashMap 不是同步的，支持 null 键和值等。通常情况下，HashMap 进行 put 或者 get 操作，可以达到常数时间的性能，所以它是绝大部分利用键值对存取场景的首选，比如，实现一个用户 ID 和用户信息对应的运行时存储结构。
TreeMap 则是基于红黑树的一种提供顺序访问的 Map，和 HashMap 不同，它的 get、put、remove 之类操作都是 O（log(n)）的时间复杂度，具体顺序可以由指定的 Comparator 来决定，或者根据键的自然顺序来判断。
考点分析
上面的回答，只是对一些基本特征的简单总结，针对 Map 相关可以扩展的问题很多，从各种数据结构、典型应用场景，到程序设计实现的技术考量，尤其是在 Java 8 里，HashMap 本身发生了非常大的变化，这些都是经常考察的方面。
很多朋友向我反馈，面试官似乎钟爱考察 HashMap 的设计和实现细节，所以今天我会增加相应的源码解读，主要专注于下面几个方面：
理解 Map 相关类似整体结构，尤其是有序数据结构的一些要点。
从源码去分析 HashMap 的设计和实现要点，理解容量、负载因子等，为什么需要这些参数，如何影响 Map 的性能，实践中如何取舍等。
理解树化改造的相关原理和改进原因。
我认为这是一种典型的使用错误，因为 HashMap 明确声明不是线程安全的数据结构，如果忽略这一点，简单用在多线程场景里，难免会出现问题。
知识扩展
1.Map 整体结构
首先，我们先对 Map 相关类型有个整体了解，Map 虽然通常被包括在 Java 集合框架里，但是其本身并不是狭义上的集合类型（Collection），具体你可以参考下面这个简单类图。
Hashtable 比较特别，作为类似 Vector、Stack 的早期集合相关类型，它是扩展了 Dictionary 类的，类结构上与 HashMap 之类明显不同。
HashMap 等其他 Map 实现则是都扩展了 AbstractMap，里面包含了通用方法抽象。不同 Map 的用途，从类图结构就能体现出来，设计目的已经体现在不同接口上。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
Java中的Map实现包括HashMap、Hashtable和TreeMap。Hashtable是早期提供的同步实现，不支持null键和值，性能开销较大，已不推荐使用。HashMap是广泛应用的哈希表实现，非同步且支持null键和值，在大多数情况下具有常数时间的性能。TreeMap基于红黑树，提供顺序访问的Map，操作的时间复杂度为O(log(n))，并且可以根据指定的Comparator或键的自然顺序进行排序。 在面试中，HashMap的设计和实现细节经常受到关注，包括容量、负载因子等参数对性能的影响，以及树化改造的原理和改进原因。并发相关问题也是热点，需要注意HashMap不是线程安全的数据结构。 读者需要了解Map的整体结构、HashMap的设计和实现要点，以及并发相关问题。此外，Java 8中HashMap的变化也值得关注。本文提供了丰富的知识点和思考角度，适合想要深入了解Map及其实现细节的读者。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《Java 核心技术面试精讲》，新⼈⾸单¥59
《Java 核心技术面试精讲》，新⼈⾸单¥59
立即购买
登录 后留言
全部留言(104)
- 最新
- 精选
三口先生置顶最常用的方法就是线性再散列。即插入元素时，没有发生冲突放在原有的规则下的空槽下，发生冲突时，简单遍历hash表，找到表中下一个空槽，进行元素插入。查找元素时，找到相应的位置的元素，如果不匹配则进行遍历hash表。 然后就是我们非线性再散列，就是冲突时，再hash，核心思想是，如果产生冲突，产生一个新的hash值进行寻址，如果还是冲突，则继续。 上述的方法，主要的缺点在于不能从表中删除元素。 还有就是我们hashmap的思想外部拉链。2018-05-24128
天凉好个秋置顶解决哈希冲突的常用方法有： 开放定址法 基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。 再哈希法 这种方法是同时构造多个不同的哈希函数： Hi=RH1（key） i=1，2，…，k 当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。 链地址法 这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。 建立公共溢出区 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。2018-05-241243
Jerry银银为什么HashMap要树化？ 文章说『本质是个安全问题』，但是导致安全问题的本质其实是性能问题。哈希碰撞频繁，导致链表过长，查询时间陡升，黑客则会利用这个『漏洞』来攻击服务器，让服务器CPU被大量占用，从而引起了安全问题。 而树化(使用红黑树）能将时间复杂度降到O(logn)，从而避免查询时间过长。所以说，本质还是个性能问题。 ---------- 个人理解哈作者回复: 竟然无法反驳，哈哈
2018-11-27671
鲤鱼读到最后链表树化刚准备开始飙车，结果突然跳车。树化讲细点更好作者回复: 感谢反馈，最近几章篇幅都超标了……只能照顾大多数需求，抱歉
2018-05-29226
xinfangke老师 如果hashmap中不存在hash冲突 是不是就相当于一个数组结构呢 就不存在链表了呢作者回复: 我理解是
2018-05-2913
kevin看不太懂，讲的还不是不太浅显，既然是面试题，最好不要太浅，但也不要太深，你这个度掌握的不是很好作者回复: 嗯，谢谢指出
2018-09-27212
代码狂徒针对负载因子，您所指的存太满会影响性能是指什么？毕竟已经开辟了相应内存空间的，没什么不用呢？作者回复: 冲突可能会增加,影响查询之类性能，当然看具体的需求
2018-05-247
沈琦斌老师，感觉最后讲为什么要树化的时候结尾有点突然。既然您说了树化本质上是个安全问题，那么树化以后怎么就解决安全问题了呢，这个我没有理解，谢谢。作者回复: 这个树实现提供可靠的logn访问性能，哈希表好的时候比它强，问题是出在最差情况，退化成链表了
2018-06-274
鲲鹏飞九万里这个内容延展的好多，这要补多少天的功课，才能搞定😂作者回复: 加油
2018-06-024- 代码狂徒为什么不是一开始就树化，而是要等到一定程度再树化，链表一开始就是消耗查找性能啊？另外其实不太明白为什么是0.75的负载因子，如果是.08或者0.9会有什么影响吗？毕竟已经开辟了相关内存空间
作者回复: 回复了，数据少的时候，平均访问长度很小，没必要麻烦；0.75是通用场景建议，取个平衡，具体看你调整它目标是什么了
2018-05-243
收起评论
