Hashing
| English | Chinese | Pinyin |
|---|---|---|
| hash function | 散列函数 | sàn liè hán shù |
| key | 键 | jiàn |
| address | 地址 | dì zhǐ |
| collision | 冲突 | chōng tū |
| linear probing | 线性探测 | xiàn xìng tàn cè |
| chaining | 链接法 | liàn jiē fǎ |
| load factor | 装填因子 | zhuāng tián yīn zi |
Finding data instantly
- A hash function 散列函数 turns a record's key 键 into an address 地址 where the record is stored.
- It lets a program jump straight to a record — near-instant lookup.
- The tricky part is handling collisions 冲突.
The hash function
- A good hash is fast, deterministic (same key → same address), and spreads keys evenly.
- Simple examples for $N$ slots: modulo (
address ← key MOD N), folding (split the key, add the parts, MOD N), or a string hash (sum character codes, MOD N).
Random file: a record's position is computed from its key by a hash function
A hash function:
A hash function maps a key to an address, enabling near-instant direct lookup.
Using the modulo hash address ← key MOD N with key = 27 and N = 10, what address is produced?
27 MOD 10 = 7 (the remainder when 27 is divided by 10).
Collisions and resolution
- A collision is when two keys hash to the same address. Ways to resolve it:
- Linear probing 线性探测 — try the next slot (wrapping around); simple but clusters.
- Chaining 链接法 — each slot points to a linked list of records that hashed there.
- Rehashing — use a second hash function.
- Keep the load factor 装填因子 (records ÷ slots) below about 70% for near-O(1) lookups.
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.
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).
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).
Searching and inserting
- Search: hash the key, read that slot; if the keys match you're done, else follow the resolution strategy until a match or an empty slot.
- Insert: hash the key, write to that slot — or the next free one if it's taken.
You've got it
- a hash function maps a key to an address (fast, deterministic, even spread)
- a collision = two keys → same address; resolve by probing, chaining, or rehashing
- keep the load factor below ~70% for fast lookups
- search/insert: hash the key, then follow the resolution strategy