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 – ,

251293525014736
10951126

(.)

Index01234567891011121314
Key473536129252501

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

MethodUsed forHow
Integer casttypes of ≤ 32 bits (char, short, float)reinterpret the bits as an int
Component sumtypes > 32 bits (long, double)sum the 32-bit components
Polynomial accumulationstringscharacters 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

MethodFormulaNotes
Divisionworks 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)

icharvalue
1b
0a

(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:

  1. Design a good hash function: fast to compute, minimizing collisions.
  2. 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

OperationBestAverageWorst
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

KeyProbesPlaced at
8999
1888
499 ✗, 00
588 ✗, 9 ✗, 0 ✗, 11
699 ✗, 0 ✗, 1 ✗, 22
Index0123–789
Key4958691889

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,

KeyProbesPlaced at
8999
1888
499 ✗, 0
588 ✗, 9 ✗, 2
699 ✗, 0 ✗, 3
Index01234–789
Key4958691889

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

KeyhashProbesPlaced at
899–99
188–88
4999 ✗, 6
5888 ✗, 3
6999 ✗, 0
Index01–234–56789
Key6958491889

⚠️ 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

StrategyProbe stepClusteringNotes
Separate chaining– (lists)none can exceed 1; extra memory for pointers
Linear probingprimarysimplest; degrades as the table fills
Quadratic probingsecondaryneeds prime,
Double hashingessentially nonetwo hash functions; prime, prime