= Solution
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. \b[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 \b[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.
Back to article page
