Hashing — Informatique universitaire

Vocabulaire

English	Sens
hash function/hæʃ ˈfʌŋkʃn/	hash function
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.
chaining/ˈtʃeɪnɪŋ/	chaining
open addressing	open addressing
load factor/ləʊd ˈfæktə/	load factor
clustering	clustering

English

Spread, collide, resolve

A hash function maps a key to a bucket: $h(k) = k \bmod 13$ sends $4, 17, 30, 43$ all to bucket $4$ — a collision. Chaining hangs a list off each bucket; open addressing walks to the next free slot.

{exercise:uni-cs0503-buckets}

Pratique

Under h(k) = k mod 13, the keys 4, 17, 30, 43 all land —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

With $m$ buckets and $n$ keys, the load factor $\alpha = n/m$ is also the average chain length: our fixed keys $[4, 17, 30, 43, 12, 25, 38]$ give $\alpha = 7/13 \approx 0.54$ — bucket $4$ holds four keys, bucket $12$ holds three, ten buckets sit empty.
Successful search costs about $1 + \alpha/2$ comparisons with chaining; grow $m$ with $n$ and the expected cost stays $O(1)$ — that resize is why dictionaries stay fast.

{exercise:uni-cs0503-load}

Pratique

Seven keys in thirteen buckets give a load factor of —

Difficulté 1/5 · 100 pièces + un petit bonus lors de la première réussite aujourd'hui

English

Linear probing on $4, 17, 30, 43$: slot $4$; then $17$ probes $4 \to 5$; $30$ probes $4, 5 \to 6$; $43$ probes $4, 5, 6 \to 7$. Total: $1 + 2 + 3 + 4 = 10$ probes for four insertions.
Clustering grows those runs, which is why real tables keep $\alpha$ under about $0.75$. Do not modulo a power of two when keys share low bits (pick a prime), and never mutate a key while it sits in the table.