Hashing · 哈希
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| 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 zi |
Finding one row in fifty million without looking
- A supermarket till scans a barcode and the price appears before your hand leaves the item. The product file holds fifty million lines.
- Nothing searched them. The barcode number went through a short calculation that produced a position, and the computer read that position: one read, no comparisons, the same time whether the file holds fifty rows or fifty million.
- The calculation is a hash function 散列函数, and the whole idea rests on it: do not store data where it will fit, store it where its own key says it belongs.
- This lesson is hashing algorithms, what happens when two keys want the same slot, and how to search and insert.
不用查找就在五千万行里找到一行
- 超市收银台扫一下条码,你的手还没离开商品,价格就出来了。商品文件有五千万行。
- 没有任何东西去查它们。条码号经过一次简短的计算得出一个位置,计算机读了那个位置:一次读取、零次比较,文件有五十行还是五千万行,用时相同。
- 那次计算就是散列函数(hash function),而整个思想都建立在它上面:不要把数据存在装得下的地方,而要存在它自己的键指定的地方。
- 这一课讲散列算法、两个键想要同一个槽位时会发生什么,以及怎样查找和插入。
The hash function
- A hash function, or hashing algorithm, takes a record's key 键 and produces the address 地址 at which the record is stored.
- A good one is fast, deterministic 确定性 (the same key always gives the same address), and spreads keys evenly across the available slots.
- For $N$ slots, the three the syllabus expects: modulo,
address ← key MOD N; folding, split the key into pieces, add them, then MOD $N$; a string hash, add the character codes, then MOD $N$.
散列函数
- 散列函数,也叫散列算法,取一条记录的键(key),产生存储该记录的地址(address)。
- 好的散列函数快、确定性(deterministic,同一个键总是给出同一个地址),并把键在可用槽位上均匀分散。
- 对 $N$ 个槽位,大纲要求的三种:取模,
address ← key MOD N;折叠,把键切成几段相加再对 $N$ 取模;字符串散列,把字符码相加再对 $N$ 取模。
A hash function: · 一个哈希函数:
A hash function maps a key to an address, enabling near-instant direct lookup. · 一个哈希函数把一个键映射到一个地址,实现近乎即时的直接查找。
What makes a hash function a good one? Select all · 所有 that apply. · 什么让一个散列函数是好的?选出所有适用的。
Fast, deterministic and evenly spread. No realistic hash avoids collisions entirely, which is why every design includes a resolution strategy. · 快、确定性、均匀分散。没有现实的散列函数能完全避免冲突,这就是每个设计都包含解决策略的原因。
Worked example: apply each algorithm
- A file has 10 slots, numbered 0 to 9. Where does key 4517 go?
- Modulo: $4517 \bmod 10 = 7$, so slot 7.
- Folding in pairs: $45 + 17 = 62$, then $62 \bmod 10 = 2$, so slot 2.
- And the key "CAB" by a string hash? $67 + 65 + 66 = 198$, then $198 \bmod 10 = 8$, so slot 8.
- Show the arithmetic. The mark is for the calculation, not the slot number alone.
例题:应用每种算法
- 一个文件有 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。
- 要写出算术过程。得分点是计算,不是单独一个槽位号。
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced? · 用取模哈希 address ← key MOD N,键 = 27 且 N = 10,产生什么地址?
27 MOD 10 = 7 (the remainder when 27 is divided by 10). · 27 MOD 10 = 7(27 除以 10 时的余数)。
A table has 10 slots. Using folding in pairs on key 4517 (add 45 and 17, then MOD 10), which slot does it go to? · 一个表有 10 个槽位。对键 4517 用两位一组的折叠(45 加 17,再对 10 取模),它进入哪个槽位?
45 + 17 = 62, and 62 MOD 10 = 2. The same key under a modulo hash would go to slot 7 instead. · 45 + 17 = 62,62 MOD 10 = 2。同一个键在取模散列下会进槽位 7。
Collisions
- A collision 冲突 happens when two different keys hash to the same address. With any hash and any realistic file, collisions are certain, so a strategy for them is part of the design, not an afterthought.
- Linear probing 线性探测 puts the record in the next free slot, wrapping round to the start at the end of the table. Simple, but records cluster: a full patch grows and every key landing in it takes longer.
- Chaining 链接法 makes each slot the head of a linked list of all the records that hashed there. No clustering, but extra memory for the pointers and a short walk along the list.
- Rehashing applies a second hash function to find another slot, spreading keys better at the cost of more computation.
冲突
- 当两个不同的键散列到同一个地址时,就发生冲突(collision)。对任何散列函数和任何现实的文件,冲突都必然发生,所以处理它的策略是设计的一部分,不是事后补救。
- 线性探测(linear probing)把记录放进下一个空槽位,到表尾就绕回开头。简单,但记录会聚集:满的一片会继续变长,落进那里的每个键都要花更久。
- 链接法(chaining)让每个槽位成为一条链表的表头,链上是所有散列到那里的记录。没有聚集,但指针要额外内存,还要沿链走一小段。
- 再散列用第二个散列函数找另一个槽位,分散得更好,代价是更多计算。
A collision occurs when: · 一个冲突发生,当:
Two keys mapping to the same slot is a collision; it must be resolved by probing, chaining or rehashing. · 两个键映射到同一个槽是一个冲突;它必须用探测、链接或再哈希解决。
Match each collision-handling idea to what it does. · 把每个冲突处理的想法与它做的事配对。
Collisions are resolved by chaining or probing; keeping the load factor low keeps lookups near O(1). · 冲突用链接或探测解决;保持负载因子低使查找接近 O(1)。
Searching and inserting
- To insert: hash the key. If the slot is free, write the record there. If not, follow the resolution strategy, the next free slot for linear probing, or the front of that slot's list for chaining.
- To search: hash the key and read that slot. If the stored key matches, the record is found. If it does not, follow the same strategy, until either the keys match or an empty slot proves the record is not in the file.
- Both operations use the same strategy. A search that stops at the first mismatch would miss every record that was ever displaced by a collision.
查找与插入
- 插入:对键散列。槽位空着就把记录写在那里。不空就按解决策略走——线性探测找下一个空槽,链接法放到该槽链表的前端。
- 查找:对键散列并读取那个槽位。存储的键匹配就找到了。不匹配就沿同一策略继续,直到键匹配,或者一个空槽位证明该记录不在文件里。
- 两种操作用同一个策略。一遇到不匹配就停止的查找,会漏掉每一条曾因冲突被挪走的记录。
Worked example: trace a collision
- A table of 10 slots uses
key MOD 10with linear probing. Insert 23, 33, 43 in that order, then search for 43. - 23 hashes to 3; slot 3 is free, so it goes there. 33 hashes to 3; slot 3 is taken by 23, so linear probing puts it in slot 4. 43 hashes to 3; slots 3 and 4 are taken, so it goes in slot 5.
- Searching for 43: hash to 3, read slot 3, key is 23, not a match, so probe on; slot 4 holds 33, not a match; slot 5 holds 43, found, after three reads.
- That growing run of three is the clustering that linear probing causes.
例题:追踪一次冲突
- 一个 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,找到,读了三次。
- 那条越来越长的连续段,正是线性探测造成的聚集。
Hash each key straight to a bucket · 把每个键直接哈希到一个桶
A hash function turns a key into a bucket number, so you jump straight to the record instead of searching. When two keys land in the same bucket that is a collision — they chain together in that bucket. · 一个哈希函数把一个键变成一个桶号,所以你直接跳到记录,而不是搜索。当两个键落在同一个桶里时那是一个冲突——它们在那个桶里串成链。
When searching a hash table, the record is not in the file as soon as the first slot read holds a different key. · 在散列表中查找时,只要读到的第一个槽位保存着不同的键,记录就不在文件里。
The record may have been displaced by a collision. The search follows the same resolution strategy until a match or an empty slot. · 该记录可能因冲突被挪走了。查找要沿同一解决策略继续,直到匹配或遇到空槽位。
Load factor
- The load factor 装填因子 is the number of records divided by the number of slots. It is the single number that predicts how well the table performs.
- Below about 70% the average lookup is near one read. Above it, probe sequences lengthen sharply and performance degrades towards a linear search.
- The fix is to make the table larger and rehash every record into it, which is why a hash table is sized for the data it will hold, not the data it holds today.
装填因子
- 装填因子(load factor)是记录数除以槽位数。它是预测表性能的那一个数字。
- 低于约 70% 时,平均查找接近一次读取。高于它,探测序列急剧变长,性能退化到接近线性查找。
- 解决办法是把表做大,并把每条记录重新散列进去,这就是散列表要按它将要保存的数据来定大小、而不是按它今天保存的数据来定大小的原因。
A 10-slot table uses key MOD 10 with linear probing. After inserting 23, 33 and 43 in that order, which slot holds 43? · 一个 10 槽位的表用 key MOD 10 加线性探测。依次插入 23、33、43 之后,哪个槽位保存 43?
All three hash to 3. 23 takes slot 3, 33 is probed to 4, and 43 to 5. Three keys in a row is exactly the clustering linear probing causes. · 三个键都散列到 3。23 占槽位 3,33 被探测到 4,43 到 5。连续三个正是线性探测造成的聚集。
Marks that slip away
- A collision is two keys, one address. It is not an error and not a lost record; it is the normal case a strategy handles.
- A search must follow the same resolution strategy as the insert, and stop only on a match or an empty slot.
- Linear probing clusters; chaining costs memory. Give the trade-off, not just the mechanism.
- The load factor is records divided by slots, and the threshold is about 70%, not 100%.
容易丢掉的分
- 冲突是两个键、一个地址。它不是错误,也不是记录丢失;它是策略要处理的正常情况。
- 查找必须遵循与插入相同的解决策略,并且只在匹配或遇到空槽位时停止。
- 线性探测会聚集;链接法花内存。要给出权衡,不能只说机制。
- 装填因子是记录数除以槽位数,阈值是约 70%,不是 100%。
To keep hash lookups fast, the load factor (records ÷ slots) should be kept: · 要保持哈希查找快,负载因子(记录 ÷ 槽)应该保持:
A lower load factor means fewer collisions, so lookups stay close to O(1). · 一个更低的负载因子意味着更少的冲突,所以查找保持接近 O(1)。
You've got it
- a hash function turns a key into an address: fast, deterministic, evenly spread; modulo, folding and string hashes are the three to know
- a collision is two keys hashing to one address, resolved by linear probing (next free slot, clusters), chaining (a linked list per slot, more memory) or rehashing
- insert and search both follow the same strategy; a search ends on a match or an empty slot
- keep the load factor, records divided by slots, below about 70% for near one-read lookups
你掌握了
- 散列函数把键变成地址:快、确定性、均匀分散;取模、折叠和字符串散列是要会的三种
- 冲突是两个键散列到一个地址,用线性探测(下一个空槽,会聚集)、链接法(每槽一条链表,更费内存)或再散列解决
- 插入和查找遵循同一策略;查找在匹配或空槽位处结束
- 让装填因子——记录数除以槽位数——保持在约 70% 以下,查找才接近一次读取