| English | 释义 | 拼音 |
|---|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | 散列函数 | sàn liè hán shù |
| key/kiː/ | 键 | jiàn |
| address/əˈdres/ | 地址 | dì zhǐ |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | 确定性 | què dìng xìng |
| collision/kəˈlɪʒn/ | 冲突 | chōng tū |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | 线性探测 | xiàn xìng tàn cè |
| chaining/ˈtʃeɪnɪŋ/ | 链接法 | liàn jiē fǎ |
| load factor/ləʊd ˈfæktə/ | 装填因子 | zhuāng tián yīn zǐ |
不用查找就在五千万行里找到一行
- 超市收银台扫一下条码,你的手还没离开商品,价格就出来了。商品文件有五千万行。
- 没有任何东西去查它们。条码号经过一次简短的计算得出一个位置,计算机读了那个位置:一次读取、零次比较,文件有五十行还是五千万行,用时相同。
- 那次计算就是散列函数(hash function),而整个思想都建立在它上面:不要把数据存在装得下的地方,而要存在它自己的键指定的地方。
- 这一课讲散列算法、两个键想要同一个槽位时会发生什么,以及怎样查找和插入。
散列函数
- 散列函数,也叫散列算法,取一条记录的键(key),产生存储该记录的地址(address)。
- 好的散列函数快、确定性(deterministic,同一个键总是给出同一个地址),并把键在可用槽位上均匀分散。
- 对 $N$ 个槽位,大纲要求的三种:取模,
address ← key MOD N;折叠,把键切成几段相加再对 $N$ 取模;字符串散列,把字符码相加再对 $N$ 取模。
一个哈希函数:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个哈希函数把一个键映射到一个地址,实现近乎即时的直接查找。
什么让一个散列函数是好的?选出所有适用的。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
快、确定性、均匀分散。没有现实的散列函数能完全避免冲突,这就是每个设计都包含解决策略的原因。
例题:应用每种算法
- 一个文件有 10 个槽位,编号 0 到 9。键 4517 放在哪里?
- 取模:$4517 \bmod 10 = 7$,所以是槽位 7。
- 折叠成两位一组:$45 + 17 = 62$,再 $62 \bmod 10 = 2$,所以是槽位 2。
- 那用字符串散列处理键 "CAB" 呢?$67 + 65 + 66 = 198$,再 $198 \bmod 10 = 8$,所以是槽位 8。
- 要写出算术过程。得分点是计算,不是单独一个槽位号。
用取模哈希 address ← key MOD N,键 = 27 且 N = 10,产生什么地址?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
27 MOD 10 = 7(27 除以 10 时的余数)。
一个表有 10 个槽位。对键 4517 用两位一组的折叠(45 加 17,再对 10 取模),它进入哪个槽位?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
45 + 17 = 62,且 62 MOD 10 = 2。同一个键若使用取模散列,则会被映射到槽位 7。
冲突
- 当两个不同的键散列到同一个地址时,就发生冲突(collision)。对任何散列函数和任何现实的文件,冲突都必然发生,所以处理它的策略是设计的一部分,不是事后补救。
- 线性探测(linear probing)把记录放进下一个空槽位,到表尾就绕回开头。简单,但记录会聚集:满的一片会继续变长,落进那里的每个键都要花更久。
- 链接法(chaining)让每个槽位成为一条链表的表头,链上是所有散列到那里的记录。没有聚集,但指针要额外内存,还要沿链走一小段。
- 再散列用第二个散列函数找另一个槽位,分散得更好,代价是更多计算。
一个冲突发生,当:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
两个键映射到同一个槽是一个冲突;它必须用探测、链接或再哈希解决。
把每个冲突处理的想法与它做的事配对。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
冲突用链接或探测解决;保持负载因子低使查找接近 O(1)。
查找与插入
- 插入:对键散列。槽位空着就把记录写在那里。不空就按解决策略走——线性探测找下一个空槽,链接法放到该槽链表的前端。
- 查找:对键散列并读取那个槽位。存储的键匹配就找到了。不匹配就沿同一策略继续,直到键匹配,或者一个空槽位证明该记录不在文件里。
- 两种操作用同一个策略。一遇到不匹配就停止的查找,会漏掉每一条曾因冲突被挪走的记录。
例题:追踪一次冲突
- 一个 10 槽位的表用
key MOD 10加线性探测。依次插入 23、33、43,然后查找 43。 - 23 散列到 3;槽位 3 空着,所以放那里。33 散列到 3;槽位 3 被 23 占了,所以线性探测把它放进槽位 4。43 散列到 3;槽位 3 和 4 都被占,所以放进槽位 5。
- 查找 43:散列到 3,读槽位 3,键是 23,不匹配,继续探测;槽位 4 是 33,不匹配;槽位 5 是 43,找到,读了三次。
- 那条越来越长的连续段,正是线性探测造成的聚集。
把每个键直接哈希到一个桶
一个哈希函数把一个键变成一个桶号,所以你直接跳到记录,而不是搜索。当两个键落在同一个桶里时那是一个冲突——它们在那个桶里串成链。
在散列表中查找时,只要读到的第一个槽位保存着不同的键,记录就不在文件里。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
该记录可能因冲突被挪走了。查找要沿同一解决策略继续,直到匹配或遇到空槽位。
装填因子
- 装填因子(load factor)是记录数除以槽位数。它是预测表性能的那一个数字。
- 低于约 70% 时,平均查找接近一次读取。高于它,探测序列急剧变长,性能退化到接近线性查找。
- 解决办法是把表做大,并把每条记录重新散列进去,这就是散列表要按它将要保存的数据来定大小、而不是按它今天保存的数据来定大小的原因。
一个 10 槽位的表用 key MOD 10 加线性探测。依次插入 23、33、43 之后,哪个槽位保存 43?
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
三个键的散列值都是 3。23 占据槽位 3,33 通过探测放入 4,43 放入 5。三个键连续排列正是线性探测造成的聚集现象。
容易丢掉的分
- 冲突是两个键、一个地址。它不是错误,也不是记录丢失;它是策略要处理的正常情况。
- 查找必须遵循与插入相同的解决策略,并且只在匹配或遇到空槽位时停止。
- 线性探测会聚集;链接法花内存。要给出权衡,不能只说机制。
- 装填因子是记录数除以槽位数,阈值是约 70%,不是 100%。
要保持哈希查找快,负载因子(记录 ÷ 槽)应该保持:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个更低的负载因子意味着更少的冲突,所以查找保持接近 O(1)。
你掌握了
- 散列函数把键变成地址:快、确定性、均匀分散;取模、折叠和字符串散列是要会的三种
- 冲突是两个键散列到一个地址,用线性探测(下一个空槽,会聚集)、链接法(每槽一条链表,更费内存)或再散列解决
- 插入和查找遵循同一策略;查找在匹配或空槽位处结束
- 让装填因子——记录数除以槽位数——保持在约 70% 以下,查找才接近一次读取