Hash tables

Lesson

A hash table stores entries in an array, indexed by hash(key) % capacity. When two keys map to the same slot (collision), resolve it by chaining (linked list per bucket) or open addressing (probe to the next slot).

Choose a hash function appropriate to your key type. For integer keys, Knuth's multiplicative ((uint32_t)k * 2654435761u) % cap is fast and good enough for most uses.

Common mistakes

• Using key % cap directly without a hash — bad keys cluster catastrophically.
• Not resizing when load factor exceeds ~0.7 — performance collapses to O(n).