🎓 A1Learner
🔍

DSA Hash Functions and Collisions

A hash function turns a key into a bucket number from a fixed row of buckets. A collision happens when two different keys land in the same bucket.

One key, one bucket

A bucket is one slot in the row. The hash adds the letter codes and divides by the bucket count.

def toy_hash(word, buckets):
    return sum(ord(ch) for ch in word) % buckets

print(toy_hash("cat", 8))
print(toy_hash("dog", 8))

Different keys can collide

Two words with the same letter total share a bucket. The hash cannot tell them apart.

def toy_hash(word, buckets):
    return sum(ord(ch) for ch in word) % buckets

print(toy_hash("act", 8), toy_hash("cat", 8))
print(toy_hash("act", 8) == toy_hash("cat", 8))

A chain holds the collided keys

Chaining stores the keys of one bucket in a small list. A lookup walks that short list.

table = [[] for _ in range(8)]
for word in ["cat", "act", "dog"]:
    bucket = sum(ord(ch) for ch in word) % 8
    table[bucket].append(word)
print(table[0])
print(table[2])

Example

def toy_hash(word, size):
    return sum(ord(ch) for ch in word) % size

words = ["cat", "act", "dog", "god", "bird", "fish", "lion", "wolf"]
size = 5
table = [[] for _ in range(size)]
for word in words:
    table[toy_hash(word, size)].append(word)

collisions = 0
for index, bucket in enumerate(table):
    line = f"bucket {index}: {bucket}"
    if len(bucket) > 1:
        line += " <- collision"
        collisions += 1
    print(line)
print("buckets with collisions:", collisions)

Key points

  • Hash function: a rule that turns a key into a bucket number
  • Collision: two different keys landing in the same bucket
  • Chaining keeps every collided key in a list inside its bucket
  • A good hash spreads keys evenly across the buckets
  • A collision is handled by storing both keys, never by dropping one

In this example, eight words are hashed into five buckets. Anagrams like cat and act share a letter total, so they always collide under this hash. Unrelated words like dog, god and lion collide by chance in bucket four. Two buckets hold more than one word, and chaining keeps every word in place. No word is lost, because a collision changes storage, not correctness.

Note

Python picks dict bucket order internally, and programs must never depend on it

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Two keys land in bucket 4 of a chained table. What does chaining do?