一、数组很快,可惜下标只认小整数二、哈希函数:给每条数据发一个座位号三、座位号撞了,谁都躲不掉四、两种接客方式:拉链 vs 开放寻址五、删除为什么不能直接置空六、顺带一个本事:一句话判断两段字符串一不一样七、什么时候会翻车最后
图书馆里躺着 100 万本书,你要借《三体》。
管理员没带你一排排走。他扫了一眼电脑上的编号:I247.5/8627,起身走到第 12 排第 4 格,抽出来递给你。整个过程八秒。
换成"从第一本开始翻",翻到明天早上也未必翻得到。
哈希表干的就是这件事。它不负责把东西存得整齐,它负责让你问一次就能直接走到那一格。
数组是计算机里最快的容器。的意思很直白:从开头往后走 5 格,取出来。一步到位,不用比较,不用循环。
a[5]
但数组有个死规矩:下标必须是不太大的整数。
你要是想存"张三的手机号",key 是"张三"这个名字,数组当场就懵了。就算 key 是整数,比如订单号 202611030001,你也不可能开一个长度两万亿的数组——内存会先把你劝退。
于是有人想了个办法:既然数组只认小整数,那我把任何 key 都想办法算成一个小整数,不就行了。
负责算这个数的,叫哈希函数。
哈希函数的输入可以是任何东西——整数、字符串、一整个结构体;输出是一个 0 到 m-1 之间的整数,m 是你开的格子数量。
最常用的一招是取模:
index = key % m
m 取多大有讲究,老规矩是取一个质数。为什么?看一组我本机刚跑出来的数据。场景是 1000 个 key,全是 10 的倍数(1000 个车位编号、1000 个商品编号,现实里太常见了):
![]()
m=1000 的时候,1000 个 key 全挤在 100 个格子里,每格挂 10 个,查一次最坏要比 10 回。换成 1009,一次都不撞——因为 key 和 1009 没有公因数,取模之后均匀撒开。
道理不复杂:key 和 m 一旦有公因数 g,能落到的格子就只剩m/g个,剩下的全空着。你花了 1000 格的内存,实际只用了 100 格。
那字符串怎么办?
字符串不能直接取模。常见做法是把它当成一个127 进制的数来累加:
h = 0for ch in s: h = h * 127 + ord(ch)
"abc" 在它眼里就是 a×127² + b×127 + c。听着玄乎,其实就是把字符换成数字,再按位拼接——和 "123" 表示 1×100+2×10+3 是同一个套路。这个乘法会越算越大,实际实现里通常让它在无符号 64 位整数里自然溢出(相当于对 2⁶⁴ 取模),或者每步都对一个质数取模,比如 998244353。
1000 个格子里塞 1000 个 key,直觉上"一人一格刚好",实际几乎不可能。这就是抽屉原理的日常版:球比抽屉多一个,就一定有两个球睡一张床。哪怕球和抽屉一样多,撞车也照样发生。
我让 100 个格子随机吞 key,结果是这样:
![]()
负载因子才 0.5,就已经有 7 个格子撞了。这不是运气差,这是数学。
所以真正的哈希表从来不是"一个数组",而是数组 + 一套处理撞车的规矩。规矩主要两种。
拉链法:每个格子里不放数据,放一个链表的头。撞了就往这条链上挂,查的时候先算格子,再顺着链找。
开放寻址法:撞了不挂链,往后挪一格,还撞就再挪,直到找到空位。像停车——你的车位被占了,就往后找下一个空位停。
![]()
开放寻址的代价是堆积:连续被占的格子越连越长,后来的 key 撞进这片区域的概率也越大。还是本机数据,1000 格线性探测:
![]()
0.7 之前还算温和,0.9 的时候最坏要摸 185 个格子。这就是为什么开放寻址的实现基本都把负载因子卡在 0.7 上下,一到线就扩容重排。
这是开放寻址最容易踩的坑,我用 11 个格子复现了一遍。
依次插入 1、12、23,它们对 11 取模都是 1,于是排在第 1、2、3 格。现在把第 1 格的 1 删掉,直接置空:
[None, None, 12, 23, None, ...]
再查 12。算法从第 1 格开始走,一看是空的——这条路断了,后面不会有 12,当场返回"不存在"。可 12 明明还在第 2 格躺着。
正确做法是在第 1 格立个“墓碑”,标记这里死过人,查询时看到墓碑继续往后走,插入时可以复用这个位置。墓碑攒多了同样拖慢速度,所以要定期整表重排一次。
拉链法没这个烦恼——链表摘掉一个节点,后面的照样接得上。
字符串哈希还有个副作用特别好用:它能O(1)判断任意两段子串是否相等。做法是先算出前缀哈希,区间哈希用减法取出来:
key = hash[r] - hash[l-1] * base^(r-l+1)
这个式子的意思不复杂。拿 114514 举例,取第 2 位到第 4 位,等于 1145 减去 1000,得 145——把前面那一截"抬到位数对齐"再减掉,剩下的就是你要的那一段。
我本机验了一下:对 "114514" 取区间 [2,4],算出的哈希是 796978;直接对 "145" 单独算哈希,也是 796978。对得上。
有了这个,判断两段长文本是否相同不用逐字比对,比两个数就行。代价是有极小概率误判(不同内容算出同一个哈希),工程上一般用双哈希把它压到可以忽略。
哈希表平均 O(1),但"平均"两个字很脆弱。
第一种翻车是被人为针对。攻击者只要知道你的哈希函数和表长,就能构造出一大批同余的 key,让它们全挤进同一个格子。链表越挂越长,O(1) 直接退化成 O(n),一个查询接口就能把服务拖死。防守的办法是给哈希函数加随机种子(Redis 就这么干),或者撞多了把链表升级成红黑树(Java 8 的 HashMap)。
第二种翻车是扩容。装到阈值就得把整张表翻倍重排,这一下是 O(n) 的。我盯着 Python 的 dict 看它长个儿:
插入 1 个:64 -> 224 字节
插入 6 个:224 -> 352
插入 11 个:352 -> 632
插入 22 个:632 -> 1168
插入 43 个:1168 -> 2264
插入 86 个:2264 -> 4688
插入 171 个:4688 -> 9304
基本是翻倍长,而且每次翻倍都要把所有元素重新算一遍位置。所以大批量写数据之前,先估个量、把容量一次开够,比让它自己慢慢长要快得多。
哈希表这东西,说穿了就三句话:拿哈希函数把 key 算成一个下标,拿一套规矩处理撞车,撞得太厉害就扩容重排。剩下所有的复杂度,都是在"撞车"这两个字上做文章。
你有没有遇到过 map 慢得像 list 的时刻?评论区说说当时是怎么发现的。
数据来源:本机 Python 3.13 实测;核心概念参考博客园《哈希表详细讲解》。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.