Hashing
Introduced| English | Meaning |
|---|---|
| hash function/hæʃ ˈfʌŋkʃn/ | A function that maps input data to a hash value for tasks such as lookup, comparison or integrity checking; different inputs may have the same value. |
| key/kiː/ | A value used to identify or look up an associated item, such as a key in a dictionary or database. |
| address/əˈdres/ | An identifier specifying a location in memory or on a network. |
| deterministic/dɪˌtɜːmɪˈnɪstɪk/ | Producing the same outcome whenever the same inputs and initial conditions are used. |
| collision/kəˈlɪʒn/ | A conflict such as different keys mapping to the same hash location, or simultaneous transmissions interfering on a shared network medium. |
| linear probing/ˈlɪnɪə ˈprəʊbɪŋ/ | A hash-table collision method that checks successive table positions until an available slot or the sought entry is found. |
| chaining/ˈtʃeɪnɪŋ/ | A hash-table collision method that keeps multiple entries associated with the same table position in a separate collection. |
| load factor/ləʊd ˈfæktə/ | For the hash table in this topic, the number of stored records divided by the number of available slots. |
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.
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$.
A hash function:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
27 MOD 10 = 7 (the remainder when 27 is divided by 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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
45 + 17 = 62, and 62 MOD 10 = 2. The same key under a modulo hash would go to slot 7 instead.
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.
A collision occurs when:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Collisions are resolved by chaining or probing; keeping the load factor low keeps lookups near 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.
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
A 10-slot table uses key MOD 10 with linear probing. After inserting 23, 33 and 43 in that order, which slot holds 43?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
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.
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%.
To keep hash lookups fast, the load factor (records ÷ slots) should be kept:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
A lower load factor means fewer collisions, so lookups stay close to 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