Intermediate · 20 minYou are hereRead
Hash functions
A hash function turns a key into an array index, spreading keys evenly so most lookups go straight to the right place. Collisions are certain; spreading is what matters.
Sorting and hashing
Hashing
Lessons on this topic
Intermediate · 20 minYou are hereRead
Hash tables with chaining
Each bucket holds a linked list of the keys that hash there, so with load factor α a lookup checks about α keys.
Intermediate · 20 minYou are hereRead
Linear probing
Keep every key in the array itself; after a collision try the next slot, and the next, until one is free.
Intermediate · 15 minYou are hereRead
Quadratic probing
Probing 1, 4, 9, … slots away breaks up linear probing’s long runs, though keys with the same home still follow the same path.
Intermediate · 15 minYou are hereRead
Double hashing
Taking the probe step from a second hash gives each key its own stride, so keys that collide once go separate ways.
Intermediate · 15 minYou are hereRead
Growing a hash table
When the load factor passes a limit, the table doubles its buckets and re-inserts every key, at an average cost per insertion that stays constant.
Related topics