Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Imperative programming / 5 / e

The relevant quantity is the hash-table load factor $\alpha =n/M$, where $n$ is the number of distinct keys and $M$ the bucket count. With a suitable distribution of hashes, separate chaining has expected operation cost $O(1+\alpha )$, treating key operations as constant-cost. Keeping only one hundred buckets while $n$ grows therefore increases average search length.

Balanced binary search trees could reduce a bucket search from linear time in its occupancy to logarithmic time. Unbalanced binary search trees provide no such guarantee: insertion order can produce a chain. Even balanced trees add comparison and node-management overhead, which may dominate for small buckets.

A usual first remedy is grow the table and rehash its entries, keeping the load factor bounded. Geometric growth gives amortized constant resizing overhead per insertion; with suitable hashing, expected lookup, update and insertion costs remain constant. Resizing is $O(n)$ when performed and is not a worst-case constant-time guarantee for that particular operation. Balanced buckets can still be useful for heavy or adversarial collisions, but replacing every bucket tree does not by itself repair a poor hash function. For variable-length strings, hashing and string comparisons add their own character-processing costs.