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 — hashing should be cheap relative to the lookup. Fixed-size integer keys can be treated as O(1), but first hashing a long string or tuple generally reads the key and costs O(key length).

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

Hashable objects must obey two rules: equal values have equal hashes, and the hash must not change while the object is stored. In Python, overriding value-based __eq__ without an appropriate __hash__ normally sets __hash__ = None, making instances unhashable instead of silently corrupting a dict. Strings, integers, and tuples containing only hashable values are common keys; mutable lists, dictionaries, and sets are unhashable by default. Mutable equality state should not drive a key's hash.

(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 added value-based __eq__ to a custom object and tried to use it as a dict key. Python slammed the door with "unhashable." What felt like an obstacle was a guardrail against a dictionary that lies. Dad's rule burned in: "Design equality and hashing as a pair—and once a key is stored, don't mutate the state its hash depends on."

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