1. Hashing
Goal
Perform search, insert and delete in constant average time.
Structure used:
- a (relatively small) table,
- entirely contained in memory,
- implemented by an array,
- so that any cell can be accessed in constant time.
2. Hash Functions
Definition – Hash function
A hash function maps the universe of keys into the cells of a hash table :
- an element of key is stored in — we say hashes to slot ;
- is the hash value of .
Good practice: choose the table size to be a prime number.
Worked example – ,
| 25 | 129 | 35 | 2501 | 47 | 36 | |
|---|---|---|---|---|---|---|
| 10 | 9 | 5 | 11 | 2 | 6 |
(.)
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Key | 47 | 35 | 36 | 129 | 25 | 2501 |
Insert, delete and search are then .
Hash code + compression
To handle any key type (not just integers), is the composition of two functions:
- hash code : key → integer,
- compression function : integer → ,
Hash codes
| Method | Used for | How |
|---|---|---|
| Integer cast | types of ≤ 32 bits (char, short, float) | reinterpret the bits as an int |
| Component sum | types > 32 bits (long, double) | sum the 32-bit components |
| Polynomial accumulation | strings | characters are coefficients of a polynomial |
Polynomial accumulation, evaluated with Horner’s rule (ignoring overflow) at a fixed :
With or : at most 6 collisions on a 50 000-word English vocabulary.
Compression functions
| Method | Formula | Notes |
|---|---|---|
| Division | works well | |
| Multiply–Add–Divide | constants; , otherwise every key maps to |
int hash(const string &key, int tableSize) {
unsigned int value = 0;
for (int i = key.size() - 1; i >= 0; --i) // Horner, x = 33
value = 33 * value + key[i];
return value % tableSize; // compression
}Worked example – hash("ab", 7) (ASCII a=97, b=98)
| i | char | value |
|---|---|---|
| 1 | b | |
| 0 | a |
(the polynomial with ) and → slot 6.
3. Collisions
Definition – Collision
Two distinct keys hash to the same cell.
Worked example: in the table above, inserting gives , but cell 5 already holds 35 → collision.
Two tasks:
- Design a good hash function: fast to compute, minimizing collisions.
- Design a method to resolve collisions when they occur:
- Separate chaining
- Open addressing: linear probing, quadratic probing, double hashing
4. Separate Chaining
Definition – Separate chaining
Use a table of linked lists: each cell keeps a list of all keys hashing to that value.
Worked example – , keys 0, 81, 1, 64, 4, 25, 36, 16, 49, 9
flowchart LR T0["0"] --> a0[0] T1["1"] --> a81[81] --> a1[1] T2["2"] T3["3"] T4["4"] --> a64[64] --> a4[4] T5["5"] --> a25[25] T6["6"] --> a36[36] --> a16[16] T7["7"] T8["8"] T9["9"] --> a49[49] --> a9[9]
Operations
- Insert : compute . If is null, make it point to a list containing only ; otherwise add a node with at the beginning of the list.
- Delete : compute , search in the list , remove its node if found.
If we store keys, choose = next prime . With a good hash function each list has a small constant number of keys.
Definition – Load (fill) factor
| Operation | Best | Average | Worst |
|---|---|---|---|
| Insert (at list head) | |||
| Search / delete |
- Average search: 1 to compute + to scan the list.
- When (), all operations are on average.
⚠️ A much larger lowers further but wastes memory. And insertion assumes we don’t check for duplicates first.
5. Open Addressing
Definition – Open addressing
All keys stay in the table itself: if collides, store it in another cell of the same array. Probe until an empty cell is found:
is the collision resolution strategy.
Linear Probing –
Cells are probed sequentially: .
for i = 0 to m-1
L = (hash(K) + i) mod m
if T[L] is empty: put K there and stop
report "table full"Worked example – insert 89, 18, 49, 58, 69 with
| Key | Probes | Placed at |
|---|---|---|
| 89 | 9 | 9 |
| 18 | 8 | 8 |
| 49 | 9 ✗, 0 | 0 |
| 58 | 8 ✗, 9 ✗, 0 ✗, 1 | 1 |
| 69 | 9 ✗, 0 ✗, 1 ✗, 2 | 2 |
| Index | 0 | 1 | 2 | 3–7 | 8 | 9 |
|---|---|---|---|---|---|---|
| Key | 49 | 58 | 69 | 18 | 89 |
Definition – Primary clustering
A cluster is a block of contiguously occupied cells. On average a new key lands in the middle of a cluster, so insertion time is proportional to half the cluster size. Disadvantages of linear probing:
- once falls into a cluster, that cluster grows by one;
- if two clusters are separated by a single free cell, one insertion merges them → performance can drop sharply after a single insertion.
Quadratic Probing –
Worked example – same keys,
| Key | Probes | Placed at |
|---|---|---|
| 89 | 9 | 9 |
| 18 | 8 | 8 |
| 49 | 9 ✗, | 0 |
| 58 | 8 ✗, 9 ✗, | 2 |
| 69 | 9 ✗, 0 ✗, | 3 |
| Index | 0 | 1 | 2 | 3 | 4–7 | 8 | 9 |
|---|---|---|---|---|---|---|---|
| Key | 49 | 58 | 69 | 18 | 89 |
Definition – Secondary clustering
Quadratic probing avoids primary clustering: keys with different home positions have different probe sequences (e.g. : home 30 → 30, 31, 34, 39…; home 29 → 29, 30, 33, 38…).
But keys with the same home position probe exactly the same sequence → secondary clustering.
⚠️ Quadratic probing may fail to find a free cell even when one exists. It is guaranteed to succeed only if is prime and the table is at most half full.
Double Hashing –
To avoid clustering, the probe sequence must depend on the key, not only on its home position → use a second hash function:
with a prime smaller than (and prime).
Worked example – , , same keys
| Key | hash | Probes | Placed at | |
|---|---|---|---|---|
| 89 | 9 | – | 9 | 9 |
| 18 | 8 | – | 8 | 8 |
| 49 | 9 | 9 ✗, | 6 | |
| 58 | 8 | 8 ✗, | 3 | |
| 69 | 9 | 9 ✗, | 0 |
| Index | 0 | 1–2 | 3 | 4–5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|
| Key | 69 | 58 | 49 | 18 | 89 |
⚠️ must never be 0 (else the key probes the same cell forever) — guarantees this. The slide example uses , which is not prime: some step sizes (e.g. 5) then cycle through only 2 cells.
Deletion in open addressing
⚠️ Not on the slides, but important: you cannot simply empty a cell — that breaks the probe chain of keys inserted after it (search would stop early at the hole). Mark the cell as deleted instead (searches skip it, insertions may reuse it).
6. Comparison of Collision Strategies
| Strategy | Probe step | Clustering | Notes |
|---|---|---|---|
| Separate chaining | – (lists) | none | can exceed 1; extra memory for pointers |
| Linear probing | primary | simplest; degrades as the table fills | |
| Quadratic probing | secondary | needs prime, | |
| Double hashing | essentially none | two hash functions; prime, prime |