Hashing

Vocabulario

English	Significado
hash function/hæʃ ˈfʌŋkʃn/	A function mapping a key to a hash value used to choose or locate a table position.
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ɪŋ/	Handling hash collisions by storing multiple entries at one bucket.
open addressing	Handling hash collisions by probing other positions within the table.
load factor/ləʊd ˈfæktə/	The number of stored hash-table entries divided by the number of buckets or slots.
clustering	Groups of occupied hash-table positions that can lengthen probe sequences.

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}

Práctica

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

Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy

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}

Práctica

Seven keys in thirteen buckets give a load factor of —

Dificultad 1/5 · 100 monedas + un pequeño bono en el primer intento de hoy

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.