| Files | Last commit | Last update |
|---|---|---|
| 20 days ago | ||
| 20 days ago | ||
| 20 days ago |
HashMap 扩容为什么卡顿?10 万个 key 实测负载因子 0.75 的秘密
10 万个随机 key 塞进一张链地址法哈希表,桶数量从 16 一路翻倍到 262,144,中间扩容 14 次。
最后一次扩容花了 18.7 毫秒,是时间线上最早那条记录(8,192 个桶)0.4 毫秒的 47 倍。
我把这张表做成了一个能点的网页:桶数组热力图、扩容耗时时间线、四种冲突策略同台对照,还有一个把所有 key 砸进同一个桶的退化实验。

它只做四件事:插入、扩容、对照、退化。
它测不了多线程并发,也不管哈希函数被恶意构造的攻击场景。
先给三条硬信息。
- 公开位置:Demo Park 仓库的
codearts-hash-table-lab目录,源码、文档、截图都在里面。 - 运行方式:把
index.html下载到本地双击就能用,零依赖、不联网、不上传数据。 - 实测数字:10 万个 key、扩容 14 次、冲突 42,611 次、末态最长链 6 条、最后一次扩容 18.7 毫秒。
一、为什么值得做这个演示
HashMap 扩容、哈希冲突、负载因子,这三个词每天都在被搜。
写业务的人几乎天天用 HashMap,但很少有人见过 0.75 这个阈值触发的那一瞬间。
讲公式的文章很多:α 一到 0.75 就翻倍,链长了查询就慢。
问题在于没人把「翻倍要花多少毫秒」「翻到第 14 次是什么感受」摆出来。
我想补的就是这两处:一次真实插入的全程,和扩容耗时随桶数量的变化。
二、进入码道 Web 与准备环境
码道有三种用法:WebUI(浏览器对话)、TUI(终端命令行)和桌面 IDE(IDE 插件)。这篇用 WebUI 版演示。
浏览器打开码道 Web 版:https://devcloud.cn-north-4.huaweicloud.com/chat?source=dmzntgwsf&sourcead=dmzntgwwbwz,登录后在对话框里直接写需求,不用装任何软件。
我给的需求是六条:key 数量可选、插入过程实时统计、四种冲突策略可切换、四种负载因子阈值可切换、四策略同批对照出表、极端退化实验加曲线。
需求原文的最后一句是「完成后打开预览,让我直接看到运行效果」,全文复制如下:
用纯 HTML + CSS + JavaScript 做一个单文件网页应用「哈希表实验室」,不要任何外部依赖、不要后端、不要 CDN,所有数字都在页面内实时真实计算。
功能要求:
1. 顶部控制区:可填 key 数量 N(默认 10000,可选 100000),有「生成 key」按钮用随机字符串批量生成 key,有「开始插入」按钮把 key 依次插入哈希表。
2. 主视图:把哈希表的桶数组画成一条热力图(每个桶一个格子,颜色深浅表示这个桶里的元素个数),旁边用卡片实时显示:元素数、桶数量、当前负载因子、冲突次数、最长链长度、扩容次数。
3. 可选冲突解决策略:链地址法、线性探测、二次探测、双散列;可选负载因子阈值:0.5 / 0.75 / 0.9 / 1.0;每次扩容要记录这一趟扩容花了多少毫秒,并在时间线上列出。
4. 对照实验:一个「四种策略对照」按钮,对同一份 key 分别用四种策略各跑一遍,输出一张实测数字表:冲突次数、平均探测长度、最坏单次查找比较次数、总耗时(毫秒)、扩容次数。
5. 极端退化实验:一个按钮把 N 个 key 全部用同一个桶下标插入(人为制造哈希冲突),展示查找一次要比较多少次、耗时多少毫秒,并画出比较次数随元素数增长的曲线。
6. 深色主题、左右分栏、数字用卡片展示,界面干净,不要写死任何数字。
完成后打开预览,让我直接看到运行效果
产出是一个纯前端单文件 index.html,深色界面,双击就能跑。
三、0.75 这个数是怎么定下来的
哈希表只有两个成本要对冲:桶多了浪费内存,桶少了链变长。
均匀哈希下,一个桶里恰好有 k 个元素的概率服从泊松分布:P(k) = α^k · e^(−α) / k!。
α 就是负载因子,等于元素数除以桶数。
取 α = 0.75、桶数 131,072,把 k 从 0 算到 7:
| 桶内元素个数 k | 概率 P(k) | 期望有几个这样的桶 |
|---|---|---|
| 0 | 0.4724 | 61,914 |
| 1 | 0.3543 | 46,436 |
| 2 | 0.1329 | 17,413 |
| 3 | 0.0332 | 4,353 |
| 4 | 0.0062 | 816 |
| 5 | 0.0009 | 122 |
| 6 | 0.0001 | 15 |
| 7 | 0.00001 | 2 |
看最后两行就明白 0.75 的位置了。
α = 0.75 时,将近一半的桶是空的,最长的链期望落在 6 到 7 个元素之间。
阈值再往上抬,空桶省下来的内存换不回查询变慢的代价;往下压,内存又白花。
页面里那个「负载因子阈值」下拉框就是用来验证这件事的。
四、实测:10 万个 key 插进去,扩容 14 次
我把 key 数量切到 100,000,策略保持「链地址法」,阈值保持 0.75,点了「开始插入」。
热力图从零星的绿点铺成整片绿色,进度条走完,右上角的状态栏给出结果:
插入完成:100,000 个 key · 冲突 42,611 · 扩容 14 次
六张卡片同时定格:
| 卡片 | 实测值 |
|---|---|
| 元素数 size | 100,000 |
| 桶数量 capacity | 262,144 |
| 当前负载因子 | 0.3815 |
| 冲突次数 | 42,611 |
| 最长链长度 | 7 |
| 扩容次数 | 14 |
桶从 16 翻倍到 262,144,一共翻了 14 次。翻完之后真正装了东西的桶不到三分之一。
热力图右下角那行小字写得很清楚:桶 262,144、非空 83,065、最大 6。

扩容时间线是这篇文章里最值钱的一张表。
每一次翻倍它都单独记了一条,面板可以上下滚,我停在最底下,末 6 次是这样:
| 第几次扩容 | 扩容后桶数 | 这次扩容耗时 | 要重新安置的元素 |
|---|---|---|---|
| #9 | 8,192 | 0.4 ms | 3,072 |
| #10 | 16,384 | 1.1 ms | 6,144 |
| #11 | 32,768 | 2.0 ms | 12,288 |
| #12 | 65,536 | 3.0 ms | 24,576 |
| #13 | 131,072 | 8.8 ms | 49,152 |
| #14 | 262,144 | 18.7 ms | 98,304 |
触发条件很简单:插入前发现元素数加一会超过 0.75 倍桶数,就先翻倍再说。
所以每次翻倍时,表里正好有 0.75 倍旧桶数个元素等着重新找位置。
规则也干净:要搬的元素翻一倍,耗时大约翻一倍,3.0 毫秒到 8.8 毫秒再到 18.7 毫秒。
再看两个端点的对比:#9 只搬 3,072 个元素,0.4 毫秒;#14 要搬 98,304 个,18.7 毫秒。
元素数翻了 32 倍,耗时翻了 47 倍。前面 8 次扩容桶数都在 4,096 以下,耗时小到这一屏里看不出来。
这就是「扩容为什么卡顿」的全部答案:慢的不是数组变大,而是这一次调用里要把 9.8 万个元素重新哈希一遍。
五、四种冲突策略同台对照
第二块面板解决另一个日常争论:链地址法和开放地址法到底怎么选。
点一下「四种策略对照」,同一份 10 万个 key 被四种策略各跑一遍:
| 策略 | 冲突次数 | 平均探测长度 | 最坏单次查找比较 | 总耗时 | 扩容次数 |
|---|---|---|---|---|---|
| 链地址法 | 42,611 | 1.561 | 6 | 37.90 ms | 14 |
| 线性探测 | 263,004 | 3.630 | 18 | 21.60 ms | 14 |
| 二次探测 | 162,921 | 2.629 | 12 | 23.80 ms | 14 |
| 双散列 | 142,650 | 2.426 | 9 | 37.90 ms | 14 |

四行数字里有三件反直觉的事。
第一,开放地址法的冲突次数是链地址法的 3 到 6 倍,但总耗时更短。
因为它不用给每个桶维护一个链表对象,插入时把 key 直接放进数组就行。
链地址法的冲突计数是一次「桶非空」判断,开放地址法的计数是一次「探测」,两个口径本身就不是一个东西。
第二,线性探测是最快的,也是最危险的。
它总耗时 21.6 毫秒,四行里最低,但最坏一次查找要比较 18 次。
因为线性探测会把连续的桶占成一整块,这块区域越大,后面的 key 越容易一路扫过去,这个现象叫聚集。
二次探测和双散列把探测步长打散了,最坏比较次数分别降到 12 和 9,代价是总耗时涨到 23.8 和 37.9 毫秒。
第三,链地址法的最坏单次查找比较只有 6 次。
10 万个 key 分到 26 万个桶里,平均一个桶不到半个元素,最长的链也就 6 个。
这也解释了为什么后面扩容时间线里的耗时会那么大:慢的不是查找,是重建。
六、把所有 key 砸进同一个桶
前两节是正常情况,第三块面板专门做最坏情况。
点「极端退化实验」,页面把 10 万个 key 的下标全部强制成 0,也就是全部塞进同一个桶。
结果只有一个数字重要:
| 指标 | 实测值 |
|---|---|
| 查找一次比较次数 | 100,000 |
| 查找一次耗时 | 3.5 ms |
| 全程插入耗时 | 26.1 ms |
| 所用策略 | 链地址法 |

查找最后一个 key,要比较 10 万次,耗时 3.5 毫秒。
同样的 10 万个 key,正常分布时最坏一次查找比较 6 次,退化后是 10 万次,差了 1.6 万倍。
页面里那条曲线画的就是这个关系:横轴元素数,纵轴比较次数,是一条斜率 1 的直线。
这也是为什么哈希函数不能太简陋,一个好的哈希函数要保证的从来不是「算得快」,是「分得匀」。
七、验证与踩坑
本地跑起来只要一条命令:
python -m http.server 8080
然后打开 http://127.0.0.1:8080/index.html。双击 index.html 直接进浏览器也一样,页面不依赖服务器。
这一轮我按 5 项走了一遍:生成 key、开始插入、四种策略对照、极端退化实验、五张截图逐张核对。
5 项全跑通,数字都在上面几节。
失败路径我留了一处:没生成 key 就点「开始插入」,状态栏给出红字提示。
提示原文是「请先「生成 key」」,不是白屏,也不是静默失败。

三个坑都是自己踩出来的。
第一个坑是同一张表上两个「最长链」口径不同。
统计卡片里的 7 是整轮插入的历史峰值,热力图右下角的 6 是当下真实分布,对照表里链地址法那行的 6 是最坏一次查找的比较次数。
三个数都对,摆在一起会让人以为代码写错了。
我在文章里把它们分开写,就是为了记住这个坑。
第二个坑是「平均探测长度」这个口径。
链地址法这一列算的是每次插入时目标桶里已有的元素个数加一,也就是刚插入那个 key 落在链尾时要走的步数。
它跨了整个插入过程取平均,负载因子从 0.375 涨到 0.75 再落回 0.375,平均下来约 0.56。
实测 1.561 正好等于 1 + 0.56,和口径对得上。
教科书里那个「固定负载因子时,成功查找平均 1 + α/2 次」说的是随机挑一个元素的平均位置。
刚插入的那个 key 在链尾,比平均位置更吃亏,两个数不该直接对比。
第三个坑是理论值和实测值放一起时要先对齐前提。
在这套扩容规则下,按每个桶被占用的概率 1 − e^(−α) 逐次累加,10 万个 key 的期望冲突是 42,494 次。
本轮实测 42,611 次,差 0.28%。
这个吻合度只能说明 key 分布得还算匀,换一批 key、换一个哈希函数,这个数字就会变。
八、使用码道的体会
先说结果:六条要点的需求,第一次交付就拿到了一个能跑的整页应用。
四种策略、四种阈值、热力图、扩容时间线、退化曲线都在里面。
真正需要返工的是显示,不是逻辑。
第一版热力图 canvas 是默认的 300×150,缩在卡片左上角,右边一大片空白。
我提了一轮具体修改点:canvas 铺满卡片、按 devicePixelRatio 放大、resize 重绘。
第二版铺满了,但格子只有 1 像素、网格只占画布上半部分,下面三分之二还是空的。
第三版按画布宽高比算格子数,一个格子覆盖多个桶时取这批桶的最长链,整块网格才铺满。
三轮下来我的结论是:功能一次对,像素要三轮。
「画面完整」这种事,需求里写清楚比事后描述有效得多。
它自己补了一处我没写进需求的东西:把扩容耗时单独记成一条时间线,而不是只给一个总耗时。
这个设计我很认,因为总耗时会被插入本身淹没,单次扩容的耗时才是能拿来做决策的数字。
九、直接下载试玩
源码、本文档和 5 张截图都在公开仓库里:
- Demo Park 仓库:https://atomgit.com/deli007/demo_park
- 本案例目录:https://atomgit.com/deli007/demo_park/tree/main/codearts-hash-table-lab
进目录把 index.html 下载到本地,双击就能自己填一个 key 数量重跑一遍。
十、小结
一页纸能把哈希表讲到多细,试过才知道。
负载因子 0.75 的背后是泊松分布,公式只有一行。
真正值得看的是它跑起来的边界:桶翻倍 14 次,最后一次要 18.7 毫秒;所有 key 撞进同一个桶,查找一次退化成 10 万次比较。
能回答「扩容为什么慢、四种策略差在哪、最坏能坏到什么程度」,不能回答「你线上那张表的哈希函数够不够匀」。
下一步想加的是阈值对照:同一个 key 数量跑 0.5 / 0.75 / 0.9 / 1.0 四个阈值,把内存占用和查找耗时摆在一张表里。
那是另一轮的事了。