Hash tables

Hash tables: fast lookup

• A hash table stores items so you can find them very fast — usually in one step.
• It is a list of slots. A hash function turns a key into a slot number.
• Instead of searching every item, you jump straight to the slot the key belongs in.

A hash function

• A hash function takes a key and returns a slot index from 0 to size - 1.
• The same key always gives the same slot, so you can find it again later.
• A simple one: add the character codes, then take % size to stay in range.

def hash_key(key, size):
    total = 0
    for ch in key:
        total += ord(ch)      # ord("A") is 65, ord("B") is 66, ...
    return total % size

print(hash_key("cat", 10))    # a slot from 0 to 9
print(hash_key("cat", 10))    # same key -> same slot
print(hash_key("dog", 10))

Collisions

• Two different keys can hash to the same slot. That is a collision.
• A table has limited slots, so collisions are unavoidable as it fills up.
• We need a rule for what to do when the slot we want is already taken.

Linear probing

• Linear probing: if a slot is full, try the next slot, then the next, wrapping around.
• Keep stepping (slot + 1) % size until you find a free slot.
• Below, A and F both want slot 0, so F is pushed to slot 1.

def hash_key(key, size):
    total = 0
    for ch in key:
        total += ord(ch)
    return total % size

def insert(table, key):
    slot = hash_key(key, len(table))
    while table[slot] is not None:      # slot taken -> try the next one
        slot = (slot + 1) % len(table)
    table[slot] = key
    return slot

table = [None] * 5
print(insert(table, "A"))   # 0
print(insert(table, "F"))   # 1  (A and F both hash to slot 0)
print(table)                # ['A', 'F', None, None, None]

Looking up a key

• To find a key: hash it, then probe forward, comparing each slot to the key.
• Stop and return the index when you find it.
• If you reach an empty slot (or check every slot), the key is not there — return -1.

Why hash tables are fast

• With few collisions, insert and find take about one step — we call this O(1).
• As the table fills, probing gets longer, so it is wise to keep some slots free.
• In the worst case (everything collides) it slows to a linear scan, O(n).

Now you try

• Build the three parts: the hash function, insert with probing, and find.
• Each task checks your function on collisions and wrap-around cases.
• Press Check answer to test it.