How Does a Hash Table Work (Hashing Functions; Collision Resolution; Load Factor)?

A hash table stores key-value pairs by using a hashing function to calculate an array index for each key. It supports efficient insertion, search, and deletion, with average time complexity of $O(1)$, provided collisions and the load factor are managed effectively.

A hashing function converts a key into an integer index. For a table with $m$ slots, a simple calculation is:

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

For example, if $h(42)=42$ and the table has $10$ slots, the key is stored at index $42 \bmod 10=2$. To retrieve the value, the same function is applied to the key, directing the algorithm to index .

A collision occurs when different keys produce the same index. Since collisions are unavoidable, the implementation must use a collision-resolution method.

The load factor measures how full the table is:

$$\alpha = \frac{n}{m}$$

Here, $n$ is the number of stored entries and $m$ is the number of slots. For example, $7$ entries in $10$ slots give $\alpha=0.7$. As $\alpha$ increases, collisions generally become more frequent. The table may therefore be and its entries into a larger array.

A common misconception is that hashing guarantees $O(1)$ operations. This is only the average case; excessive collisions can produce worst-case time complexity of $O(n)$.

In an IB Computer Science response on B4.1 Fundamentals of ADTs, clearly trace the key through hashing, index calculation, collision resolution, and retrieval. If asked to explain efficiency, connect the load factor and collision frequency to average and worst-case performance.