When Hashing Fails

The Idea

Two keys can land in one bucket. Real tables absorb that by chaining or probing, and the average stays O(1). But a hash function that crowds keys into a few buckets drags lookups toward O(n). Keys must also be immutable: mutate a key after insertion and its hash stops pointing where it lives.

Real-World Example

A festival wristband desk splits collection queues by the first letter of the holder's first name. The decade's most popular baby name floods one line while three desks stand idle. The rule was cheap to apply and hopelessly uneven — which is exactly what a bad hash does.

The Code

def bad_bucket(key, n):
    return len(key) % n          # clusters hard: most names are short

names = ["ana", "bob", "cal", "dee"]
print([bad_bucket(x, 8) for x in names])   # [3, 3, 3, 3] -> one bucket

point = [1, 2]
try:
    seats = {point: "aisle"}     # keys must be hashable
except TypeError:
    print("unhashable:", type(point).__name__)   # unhashable: list

print({tuple(point): "aisle"})   # {(1, 2): 'aisle'} -> tuples work

# make this coordinate usable as a dictionary key
point = ___
seats = {point: "aisle"}
print(seats[point])