Hash Collisions, Good Hash Functions, and Hashable Keys

What happens when two keys hash to the same slot, and why can't a list ever be a dictionary key?

Finger exercises

Short drills on what this video just taught. Write the code, run the checks, and reveal the answer only if you are stuck.

0 / 5 passed

Exercise 1 of 5

Store colliding keys in one bucket

The given letter_hash(key) is the video's hash: add up the letter positions and take the sum mod 16. A table is a list of 16 buckets, each bucket a list of (key, value) tuples. Define store(table, key, value) that puts the pair at the end of the bucket its key hashes to, so colliding keys simply share that bucket (assume the key is not stored yet).

Given code — runs before yours

def letter_hash(key, size=16):
    """Sum of letter positions (a=1, ..., z=26), mod size."""
    total = 0
    for ch in key:
        total += ord(ch.lower()) - ord('a') + 1
    return total % size

def store(table, key, value):
    # add (key, value) to the bucket this key hashes to
    return ...  # your code here

def store(table, key, value):
    # add (key, value) to the bucket this key hashes to
    return ...  # your code here

Python runs in your browser

⌘/Ctrl + Enter runs

a non-colliding key lands alone in its slot

Ana and Eve collide and share one bucket, in insertion order

every other slot stays empty

←Previous How Lists and Dictionaries Find Items in Constant Time Next Monte Carlo Simulation: Estimating Dice Probabilities →