FilesLast commitLast update
20 days ago
20 days ago
20 days ago
README

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。

插入 10 万个 key 之后:热力图铺满桶数组、卡片定格在 262,144 个桶、扩容时间线停在末 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

四种策略对照:同一份 key 跑出四行实测数字

四行数字里有三件反直觉的事。

第一,开放地址法的冲突次数是链地址法的 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 撞进同一个桶,查找退化成单链表扫描,比较次数等于元素数

查找最后一个 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」」,不是白屏,也不是静默失败。

失败路径:未生成 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 张截图都在公开仓库里:

进目录把 index.html 下载到本地,双击就能自己填一个 key 数量重跑一遍。

十、小结

一页纸能把哈希表讲到多细,试过才知道。

负载因子 0.75 的背后是泊松分布,公式只有一行。

真正值得看的是它跑起来的边界:桶翻倍 14 次,最后一次要 18.7 毫秒;所有 key 撞进同一个桶,查找一次退化成 10 万次比较。

能回答「扩容为什么慢、四种策略差在哪、最坏能坏到什么程度」,不能回答「你线上那张表的哈希函数够不够匀」。

下一步想加的是阈值对照:同一个 key 数量跑 0.5 / 0.75 / 0.9 / 1.0 四个阈值,把内存占用和查找耗时摆在一张表里。

那是另一轮的事了。