05｜HashMap：一个优秀的散列表是怎么来的？
黄清昊
该思维导图由 AI 生成，仅供参考
你好，我是微扰君。
过去四讲我们学习了 STL 中全部的序列式容器，数组、链表、队列、栈；今天来谈一谈另一类容器，关联式容器。所谓“关联式”，就是存储数据的时候，不只是存储元素的值本身，同时对要存储的元素关联一个键，形成一组键值对。这样在访问的时候，我们就可以基于键，访问到容器内的元素。
关联式容器本身其实是 STL 中的概念，其他高级语言中也有类似的概念。我们这次就以 JDK 为例，讲解几种关联式容器的原理和实现。
统计单词次数
我们就从一个实际需求讲起。现在有一篇很长的英文文档，如果希望统计每个单词在文档中出现了多少次，应该怎么做呢？
如果熟悉 HashMap 的小伙伴一定会很快说出来，我们开一个 HashMap，以 string 类型为 key，int 类型为 value；遍历文档中的每个单词 word ，找到键值对中 key 为 word 的项，并对相关的 value 进行自增操作。如果该 key= word 的项在 HashMap 中不存在，我们就插入一个 (word,1) 的项表示新增。
这样每组键值对表示的就是某个单词对应的数量，等整个文档遍历完成，我们就可以得到每个单词的数量了。用 Java 语言实现这个逻辑也不难。
但是 HashMap 是怎么做到高效统计单词对应数量的？它设计思路的核心究竟是什么呢？这个问题非常有意思，我们一起来思考一下。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入剖析了HashMap的设计思路和核心原理，通过对比使用数组和HashMap的不同实现方式，引出了HashMap的优化思路。文章介绍了如何利用HashMap统计文档中单词出现的次数，并提出了将单词映射为26进制数的优化方法，大大提高了统计效率。在JDK中，HashMap的实现采用了简洁的散列函数，结合了对hashcode的计算和位运算的处理，以及开链法来处理哈希冲突，保证了散列表的高效性和稳定性。此外，文章还对HashMap的resize操作进行了详细解析，说明了其扩容机制和负载因子的作用。总的来说，本文通过对HashMap的实际应用和JDK的实现进行深入剖析，为读者提供了全面的了解和实践价值。读者可以从中学习到如何手写数据结构统计单词的数量，以及在实际工程中如何使用HashMap或者ConcurrentHashMap来处理散列表的相关问题。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《业务开发算法 50 讲》，新⼈⾸单¥59
《业务开发算法 50 讲》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(10)
- 最新
- 精选
- Paul Shan负载因子定义了扩容时机，在容量和冲突数目取得均衡，一般默认值适合多数情况。个人猜测hashmap用在内存较小的情况下（例如嵌入式系统）应该调整loadfactor，因为这个时候的环境就不是通常环境，需要增加冲突来降低存储。
作者回复: 是的 如果我们内存非常有限的时候，就要将loadfactor提高
2021-12-216 - 吴钩我的理解是：load factor是时间空间权衡的经验参数，当我们明确有时间空间的侧重点时可以改。比如空间不是问题，get的场景多且性能要求高，put的扩容时间损失可以接受，就可以调低load factor，让HashMap多多扩容。
作者回复: 说得没错
2021-12-303 
友假设 n=3 i=0 -> h = 31 * 0 + val[0] i=1 -> h = 31 * (31 * 0 + val[0]) + val[1] i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2] h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2] h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]作者回复: 是这么回事～
2021-12-23- 友复习 : 如果是2^n 那么只有最高位为1，所以 num & 2^n -1 也就是 低位全是1 就获取到了取余的数据 11 % 2 1011 & 0001 = 1
作者回复: 理解正确
2021-12-22 - 友31*i 可以直接转化为(i << 5)- i 看到这句就想起csapp第二章（应该是第二章）
作者回复: 差不多 csapp是好书，值得反复阅读～
2021-12-22 
毛小树为什么hashCode的计算选择31? 1. 一定要奇数。不能用偶数。 2. 素数不素数其实关系不大。 3. 用31是因为31=2^5-1。可以把乘法转换成开销更小的位移操作。提高效率。2022-06-191
拓山为什么是31? https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier/299748#299748 排名第一的回答给出了理论公式：31 * i == (i << 5) - i，但对工程实践意义不大。 要结合排名第二的回答： 【Goodrich and Tamassia computed from over 50,000 English words (formed as the union of the word lists provided in two variants of Unix) that using the constants 31, 33, 37, 39, and 41 will produce fewer than 7 collisions in each case. This may be the reason that so many Java implementations choose such constants.】 正如 Goodrich 和 Tamassia 指出的那样，如果你对超过 50,000 个英文单词（由两个不同版本的 Unix 字典合并而成）进行 hash code 运算，并使用常数 31, 33, 37, 39 和 41 作为乘子，每个常数算出的哈希值冲突数都小于7个，所以在上面几个常数中，常数 31 被 Java 实现所选用也就不足为奇了。 可以看到31是乘子效果最好的最小值，因此选择31是理论+实践的完美数字2023-08-09归属地：浙江
A君哈希表目的是将巨大的稀疏的空间映射到小的连续空间，方法是散列化后再取模，遇到哈希冲突后，可以通过数组+链表的方式解决2023-02-07归属地：上海
SevenHe我有个疑问，当HashMap量足够大时，扩容所需的rehash开销可能会很大。如果为了保证HashMap的即时可用性，是不是要先在另外开个线程里扩容，在没ready之前，原有容器还可以继续对外提供hash服务。2022-03-212
猫头鹰爱拿铁resize方法里都会执行lotail=e和hitail=e这个和lotail=lotail.next和hitail=hitail.next是不是等价2022-02-23
收起评论
