网易首页 > 网易号 > 正文 申请入驻

100 万条数据里找一个,它凭什么只翻一次

0
分享至

一、数组很快,可惜下标只认小整数二、哈希函数:给每条数据发一个座位号三、座位号撞了,谁都躲不掉四、两种接客方式:拉链 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 实测;核心概念参考博客园《哈希表详细讲解》。

声明:内容由AI生成

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

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.

相关推荐
热点推荐
庞众望现状:27岁清华博士毕业,母亲去世5年后,女友一直陪他

庞众望现状:27岁清华博士毕业,母亲去世5年后,女友一直陪他

小虎新车推荐员
2026-11-22 00:11:54
副厅长,任民办高校党委书记

副厅长,任民办高校党委书记

麦可思研究
2026-11-21 18:11:45
英锦赛一夜2场冷门!中国2胜1负,傅家俊对手确定,奥沙利文出局

英锦赛一夜2场冷门!中国2胜1负,傅家俊对手确定,奥沙利文出局

小火箭爱体育
2026-11-21 21:47:42
超3亿元!福建提前下达一批补助资金

超3亿元!福建提前下达一批补助资金

北青网-北京青年报
2026-11-21 18:55:03
自曝,“家丑”,1,个月,张家齐传来喜讯,和全红婵哥哥恋爱早有真相

自曝,“家丑”,1,个月,张家齐传来喜讯,和全红婵哥哥恋爱早有真相

誮惜颜a
2026-11-21 21:56:15
“新型啃老”全国开始蔓延,孩子不上班、不要钱,只是把门关上,父母却更难受了

“新型啃老”全国开始蔓延,孩子不上班、不要钱,只是把门关上,父母却更难受了

可读
2026-11-20 22:34:37
兄妹顶峰相见后日乒再现情侣顶峰相见 90后姐姐与00后弟弟温馨依偎

兄妹顶峰相见后日乒再现情侣顶峰相见 90后姐姐与00后弟弟温馨依偎

劲爆体坛
2026-11-22 08:18:04
R星太会串:《GTA6》出现“异性恋骄傲游行”

R星太会串:《GTA6》出现“异性恋骄傲游行”

游民星空
2026-11-22 10:14:17
连遭三轮袭击,克里米亚大桥已很难修复,俄军开始疯狂报复

连遭三轮袭击,克里米亚大桥已很难修复,俄军开始疯狂报复

兵国大事
2026-11-20 16:37:56
阿尔特塔离谱用人!阿森纳全能天才被雪藏!实力碾压 7500 万新援

阿尔特塔离谱用人!阿森纳全能天才被雪藏!实力碾压 7500 万新援

澜归序
2026-11-22 10:32:38
监管升级!5家券商遭密集罚单,涉及中信证券!下周券商会这样走

监管升级!5家券商遭密集罚单,涉及中信证券!下周券商会这样走

虎哥闲聊
2026-11-22 09:22:06
工商银行、建设银行等示警金市风险,网友:已经被套,30年后再看了

工商银行、建设银行等示警金市风险,网友:已经被套,30年后再看了

东方豪侠
2026-11-21 12:16:51
刚刚,Anthropic攻下黎曼猜想,DeepSeek和国产模型在卖API

刚刚,Anthropic攻下黎曼猜想,DeepSeek和国产模型在卖API

智能纪元AGI
2026-11-21 21:13:06
钓鱼钩到一把“左轮喷子”,拿在手里绣得掉渣,重庆男子丢回水中!网友发问:为啥不报警?

钓鱼钩到一把“左轮喷子”,拿在手里绣得掉渣,重庆男子丢回水中!网友发问:为啥不报警?

鱼窝鱼窝
2026-11-20 18:50:04
37岁张檬广州遛娃引热议!双保姆随行太惬意,产后状态太真实

37岁张檬广州遛娃引热议!双保姆随行太惬意,产后状态太真实

揭秘世间万象
2026-11-21 09:33:45
普通人要提前做准备:北京等地出现7大转变,正在蔓延,深思

普通人要提前做准备:北京等地出现7大转变,正在蔓延,深思

笑熬浆糊111
2026-11-21 11:23:32
京AG21637、京Q966T5、京QT2H29,相关小客车指标作废!

京AG21637、京Q966T5、京QT2H29,相关小客车指标作废!

BRTV新闻
2026-11-21 20:37:03
小雷:拉亚是阿森纳唯一无法被替代球员,凯帕达不到他的水平

小雷:拉亚是阿森纳唯一无法被替代球员,凯帕达不到他的水平

懂球帝
2026-11-22 10:32:07
CCTV5直播U17国足VS摩洛哥,浮嶋敏黔驴技穷,名记质疑邝兆雷水平

CCTV5直播U17国足VS摩洛哥,浮嶋敏黔驴技穷,名记质疑邝兆雷水平

体育大学僧
2026-11-21 09:26:00
峨眉山偶遇刘涛!48岁素颜爬山状态引热议

峨眉山偶遇刘涛!48岁素颜爬山状态引热议

手工制作阿歼
2026-11-20 13:03:18
2026-11-22 11:04:49
千纸鹤安安
千纸鹤安安
大自然的搬运工
216文章数 4关注度
往期回顾 全部

科技要闻

Anthropic收涨17.1%,市值一度破2万亿美元

头条要闻

"敢不敢玩刺激的" 女博士当主播6个月至今有心理阴影

头条要闻

"敢不敢玩刺激的" 女博士当主播6个月至今有心理阴影

体育要闻

约基奇vs申京:最强的策应巨人?

娱乐要闻

港姐季军吴文忻去世,生前已办追思会

财经要闻

金价跌破3550美元,分析称短期下行未逆转

汽车要闻

35万级MPV的满配答案 享界V8正式上市售31.98万起

态度原创

游戏
艺术
本地
旅游
公开课

曝GTA6"偷偷"监控你的心理 R星小馋猫什么都看?

艺术要闻

16位欧洲画家的19幅作品欣赏

本地新闻

43年起落记忆倒计时,去厦门高崎领绝版登机牌!

旅游要闻

闵行浦江:菊海听秋林下歇脚 千灯起处铁花如雨

公开课

李玫瑾:为什么性格比能力更重要?

无障碍浏览 进入关怀版