Data StructuresData StructuresCollege

Hash Tables

Hash functions, collisions and load factor.

A hash table stores key-value pairs so that looking up a key takes, on average, constant time. A hash function turns each key into an index in an underlying array. Python dictionaries, JavaScript objects and Maps, and Java HashMaps are all hash tables.

Two different keys can hash to the same index, a collision. Chaining stores a small list at each slot; open addressing probes for the next free slot. Keeping the load factor (entries divided by slots) low, typically under about 0.75, keeps collisions rare, and tables resize automatically when it grows too high.

Key ideas

Average insert, lookup and delete: $O(1)$ ; worst case $O(n)$ if everything collides.
Load factor $\alpha = \frac{n}{m}$ for $n$ entries in $m$ slots.
Good hash functions spread keys uniformly and are fast to compute.
Hash tables do not keep keys in sorted order.

Worked example

Using $h(k) = k \bmod 7$ , insert keys 15, 22 and 9 into a 7-slot table with chaining.

$15 \bmod 7 = 1$ : slot 1.
$22 \bmod 7 = 1$ : collision, chained in slot 1.
$9 \bmod 7 = 2$ : slot 2.
Load factor: $\frac{3}{7} \approx 0.43$ .

Answer: Slot 1: 15 → 22; slot 2: 9

Common mistakes

Expecting keys to come out in insertion or sorted order.
Using mutable objects as keys, so their hash changes.
Ignoring the worst case when many keys collide.

Practice questions

Try each one, then open the answer. Numerical answers on this page are verified by an automated calculation check.

1.Slot for key 38 with $h(k) = k \bmod 10$ .
Show answer
$8$
2.Load factor of 300 entries in 400 slots.
Show answer
$0.75$
3.Slot for key 100 with $h(k) = k \bmod 13$ .
Show answer
$9$

Key ideas

Worked example

Common mistakes

Practice questions

More in Data Structures