CodeLudo 🔥 Daily Guides

More Buckets Will Not Save a Bad Hash Function

✓ numbers produced by the code on this page · Published 2026-08-20

“Hash tables are O(1)” gets repeated until the conditions fall off the end of the sentence. The full version is: constant time on average, for a hash function that spreads keys evenly, at a load factor somebody is watching. Remove any one of those and lookups slide back toward a linear scan.

The dangerous part is that the table still returns correct answers the whole way down. There is no error, no warning, and no test failure — just a program that gets slower as it gets more data, for a reason that never appears in the code that uses it.

Change the hash, not the table

Start on length of the word and drag the bucket slider. Then switch hash function and drag it again.

Probe a hash table the hash matters more than the table size

A hash table sends each key to a bucket by running it through a hash function. When two keys land in the same bucket they form a chain, and a lookup has to walk that chain — so the cost of a lookup is decided by how evenly the hash spreads the keys.

With these 12 keys and a hash that uses only the LENGTH of the word, 8 buckets give a longest chain of 6 and an average successful lookup of 2.42 probes. Doubling the table to 16 buckets changes that to a longest chain of 6 and 2.42 probes — that is, nothing improves, and 11 of the 16 buckets sit completely empty. Memory cannot fix a hash that ignores its input. Switching to a polynomial hash over the same 16 buckets gives a longest chain of 2 and 1.25 probes.

Click any key to look it up. The highlighted cells are the entries that lookup had to step over, and the probe count is what it cost.

The thing worth staring at: with the length hash, going from 8 buckets to 16 does not shorten the longest chain at all. It just creates empty buckets. Every six-letter word still hashes to the same place, because the hash never looked at anything except the length — and doubling the number of places to put things does not help when your rule for choosing a place ignores the thing you are placing.

Why the two bad hashes are bad differently

Length of the word collapses a rich key into a small integer. English words cluster hard at four to nine characters, so a dozen keys collapse into about five distinct values — and no table size recovers information the hash already threw away.

First letter is a real improvement and still not enough. It has at most 26 possible outputs however large the table is, so any table with more than 26 buckets is mostly wasted, and real key sets are never spread evenly across the alphabet anyway. Names starting with S vastly outnumber names starting with X.

A polynomial hash folds every character into the result, and multiplying by 31 at each step means position matters too, so "stop" and "post" do not collide. This is the shape of hash real string implementations use.

The numbers, computed

Same twelve keys, three hash functions, two table sizes.

python 
KEYS = ["apple", "apricot", "avocado", "banana", "berry", "cherry",
        "date", "fig", "grape", "guava", "lemon", "mango"]


def h_length(key):
    """Throws away everything except how long the key is."""
    return len(key)


def h_first(key):
    """Uses one character. At most 26 distinct values, whatever the table size."""
    return ord(key[0])


def h_poly(key):
    """Every character contributes, and its position matters."""
    h = 0
    for ch in key:
        h = (h * 31 + ord(ch)) % 4294967296
    return h


def build(keys, hash_fn, buckets):
    table = [[] for _ in range(buckets)]
    for key in keys:
        table[hash_fn(key) % buckets].append(key)
    return table


def measure(keys, hash_fn, buckets):
    table = build(keys, hash_fn, buckets)
    probes = sum(i + 1 for chain in table for i, _ in enumerate(chain))
    longest = max(len(chain) for chain in table)
    empty = sum(1 for chain in table if not chain)
    return longest, probes / len(keys), empty


print(f"{'hash':<20} {'buckets':>7} {'longest':>7} {'avg probes':>10} {'empty':>5}")
for name, fn in [("length of the word", h_length), ("first letter", h_first), ("polynomial x31", h_poly)]:
    for buckets in (8, 16):
        longest, avg, empty = measure(KEYS, fn, buckets)
        print(f"{name:<20} {buckets:>7} {longest:>7} {avg:>10.2f} {empty:>5}")
Output 
hash                 buckets longest avg probes empty
length of the word         8       6       2.42     3
length of the word        16       6       2.42    11
first letter               8       3       1.50     1
first letter              16       3       1.42     8
polynomial x31             8       3       1.75     2
polynomial x31            16       2       1.25     7

Read the first two rows together. Doubling the table left the longest chain at 6 and the average lookup at 2.42 probes — identical — while leaving 11 of 16 buckets empty. That is twice the memory for exactly no speed. The last two rows are what spending memory is supposed to buy: the longest chain halves and the average lookup drops to 1.25 probes.

Load factor is the other half

Even a perfect hash slows down as a table fills. The load factor — keys divided by buckets — is what real implementations watch, and crossing a threshold triggers a resize: allocate a bigger table and re-hash every key into it.

That resize is why an individual insert into a hash table is occasionally very expensive while the average stays cheap. It is also why the two failure modes are easy to confuse. A table that is merely full gets faster when you give it more buckets. A table with a bad hash does not, and reaching for more memory is the natural wrong move.

The distinguishing question is the one the widget makes visible: are the empty buckets increasing while the longest chain stays put? If so, the problem is the hash.

What this page simplifies