What Makes a Good Hash Function

"A hash map is only as good as its hash function. A bad one is still 'correct' — it just quietly degrades your O(1) dream back into an O(n) linked list."

Three Properties of a Good Hash

A hash function should be:

Deterministic — the same key always produces the same hash. Without this, you couldn't find what you stored. Non-negotiable.
Uniform — it spreads different keys evenly across the table, so slots fill at roughly equal rates and collisions stay rare. This is what protects the O(1).
Fast — computing it must be cheap (close to O(1)), or the speed you gained from direct addressing is eaten by the hash itself.

A good hash has an avalanche quality: changing the key even slightly ("cat" vs "car") scatters the hash to a completely different value, which is exactly what keeps similar keys from clumping into the same slots.

Why a Bad Hash Is a Silent Killer

Consider the worst legal hash function: return 0 for every key. It's deterministic and fast — and catastrophic. Every key lands in slot 0, so the "hash map" collapses into one giant chain you scan linearly. Lookups are O(n), and nothing looks broken; the code is "correct," just slow. This is why a clumping hash (one that maps many real keys to few slots) quietly destroys performance without any error. The hash function's uniformity is the difference between O(1) and O(n).

A good hash is deterministic, uniform, and fast. 'Correct but clumping' is the dangerous failure: it keeps working while silently degrading O(1) lookups into O(n) scans. Uniformity is what protects the speed.

The Contract You Must Respect

You'll rarely write a hash function from scratch — but the moment you use your own objects as dict keys, you inherit a contract: if two objects are equal, they must have the same hash. In Python that means __eq__ and __hash__ must agree. Break it — two "equal" objects with different hashes — and the map stores them in different slots, so it can never find one by the other. Equal-must-hash-equal is the rule that makes hashing trustworthy.

(Aside: Python salts string hashes with a per-process random seed, so hash("x") differs between runs. That's a deliberate security measure to stop attackers from crafting keys that all collide — a denial-of-service we'll revisit in the last lesson of this track.)

Pippa's Confession

I once made a custom object a dict key, defined __eq__ so two instances compared equal, and forgot to define __hash__ to match. The map cheerfully stored both "equal" objects in different slots and swore neither existed when I looked them up. No error — just a dictionary that lied. Dad's rule, burned in since: "If you touch __eq__, you touch __hash__. They're a pair or they're a bug."

Code

Clumping hash vs uniform, and the eq/hash contract·python

# A TERRIBLE hash vs a reasonable one — same data, very different clumping.
def terrible_hash(key, size):
    return 0                      # everything lands in slot 0 -> O(n) chain

def ok_hash(key, size):
    return hash(key) % size       # Python's hash spreads keys well

keys = ["apple", "banana", "cherry", "date", "fig", "grape"]
for name, fn in [("terrible", terrible_hash), ("ok", ok_hash)]:
    slots = {}
    for k in keys:
        slots.setdefault(fn(k, 8), []).append(k)
    print(name, "-> slot usage:", {s: len(v) for s, v in sorted(slots.items())})
# terrible: every key in one slot (a single length-6 chain).
# ok: keys spread across several slots (short chains -> O(1) lookups).

# The __eq__/__hash__ contract for custom keys:
class Point:
    def __init__(self, x, y): self.x, self.y = x, y
    def __eq__(self, o): return (self.x, self.y) == (o.x, o.y)
    def __hash__(self): return hash((self.x, self.y))   # MUST agree with __eq__

d = {Point(1, 2): "here"}
print(d[Point(1, 2)])    # 'here' — equal points hash the same, so it's found

Exercise

Someone proposes hashing strings by 'sum of character codes mod table_size.' Name two real keys that would collide under it, and explain why this hash clumps badly (hint: anagrams). Then state what breaks if a class defines __eq__ to compare by id-number but __hash__ still uses Python's default object identity.

Hint

'listen' and 'silent' (anagrams) have identical character-code sums → same slot; any anagrams collide, so it's far from uniform. If __eq__ says two objects are equal but __hash__ gives them different hashes, the set/dict puts them in different slots and never matches them.

Three Properties of a Good Hash

Why a Bad Hash Is a Silent Killer

The Contract You Must Respect

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0