A hash table maps a key to a bucket with a hash function. Average lookup is Θ(1) if buckets stay short. Collisions share a bucket. Load factor is items / buckets.

Goal

Hash city names into buckets, count collisions, and look up a key.

Buckets

def make_table(keys, m):
    buckets = [[] for _ in range(m)]
    for key in keys:
        buckets[hash(key) % m].append(key)
    return buckets

keys = ["nairobi", "mombasa", "kisumu", "nakuru", "eldoret", "nairobi"]
table = make_table(keys, 4)
for i, b in enumerate(table):
    print(i, b)
print("load", len(keys) / 4)

hash is Python’s. % m picks the bucket. Duplicate "nairobi" lands in the same bucket twice unless you store unique keys.

Lookup

def lookup(table, key):
    steps = 0
    bucket = table[hash(key) % len(table)]
    for item in bucket:
        steps += 1
        if item == key:
            return True, steps
    return False, steps

keys = ["nairobi", "mombasa", "kisumu", "nakuru"]
table = [[] for _ in range(4)]
for key in keys:
    table[hash(key) % 4].append(key)
print(lookup(table, "kisumu"))
print(lookup(table, "kericho"))

If every key collides, the bucket is a list and lookup is Θ(n). Keep load factor modest.

From a file

Download words.txt, Add files, then:

from pathlib import Path

words = [w for w in Path("words.txt").read_text(encoding="utf-8").splitlines() if w]
print(len(words), "rows", len(set(words)), "unique")
print(set(words))

Pitfall

Do not write hash(key) into a file and expect it to match next week. Python salts hash() per process. Use the dict ADT in production; this toy table is for counting chain length.