Hashing and Dictionaries

Finding Things Instantly

A dictionary (map) ADT stores key–value pairs for fast lookup, insertion, and deletion by key. The underlying structure is the hash table.

A hash function computes an integer from a key. Reduced modulo the array size, this gives the index of the bucket holding that value:

$$\text{index} = \text{hash(key)} \bmod m$$

When keys spread evenly, operations take $O(1)$ on average. Because two different keys can yield the same index, collisions occur. Every hash table uses a collision-resolution strategy to prevent overwriting values.

Performance and Pitfalls

Performance relies on the load factor (elements divided by buckets). As the table fills, collisions increase. To maintain speed, hash tables resize by allocating a larger array and rehashing all elements.

Common Pitfall: Believing hash lookups are guaranteed $O(1)$. The $O(1)$ is an average under a good hash function and low load factor.