Hash Table Concept and Hash Functions in DSA Python

Mental Model

A hash table stores data by turning keys into numbers to find values quickly. It uses a special math rule called a hash function to do this.

Analogy: Imagine a library where each book has a unique code made by a machine. Instead of searching all shelves, you use the code to go directly to the right shelf and spot.

Hash Table:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Hash Function: key -> index
Example: key 'cat' -> hash function -> index 2

Dry Run Walkthrough

Input: Insert keys 'cat', 'dog', 'bird' into a hash table of size 5 using a simple hash function: sum of ASCII codes of letters mod 5.

Goal: Show how keys are converted to indexes and stored in the hash table.

Step 1: Calculate hash for 'cat' and insert at index

[0] -> null
[1] -> null
[2] -> 'cat' -> null
[3] -> null
[4] -> null

Why: We convert 'cat' to a number to find its place quickly.

Step 2: Calculate hash for 'dog' and insert at index

[0] -> null
[1] -> null
[2] -> 'cat' -> null
[3] -> null
[4] -> 'dog' -> null

Why: We use the hash function to find where 'dog' goes.

Step 3: Calculate hash for 'bird' and insert at index

[0] -> null
[1] -> null
[2] -> 'cat' -> null
[3] -> null
[4] -> 'dog' -> null

Why: Hash function places 'bird' at index 2, but since 'cat' is already there, it overwrites 'cat'.

Result:

[0] -> null
[1] -> null
[2] -> 'bird' -> null
[3] -> null
[4] -> 'dog' -> null

Annotated Code

DSA Python

class HashTable:
    def __init__(self, size=5):
        self.size = size
        self.table = [None] * size

    def hash_function(self, key: str) -> int:
        # Sum ASCII codes of characters, then mod by table size
        return sum(ord(c) for c in key) % self.size

    def insert(self, key: str):
        index = self.hash_function(key)  # get index from hash function
        self.table[index] = key  # store key at computed index

    def __str__(self):
        result = []
        for i, val in enumerate(self.table):
            if val is None:
                result.append(f"[{i}] -> null")
            else:
                result.append(f"[{i}] -> '{val}' -> null")
        return "\n".join(result)

# Driver code
ht = HashTable()
ht.insert('cat')
ht.insert('dog')
ht.insert('bird')
print(ht)

index = self.hash_function(key)

convert key to index using hash function

self.table[index] = key

store key at computed index in table

Output

[0] -> null

[1] -> null

[2] -> 'bird' -> null

[3] -> null

[4] -> 'dog' -> null

Complexity Analysis

Time: O(1) average because hash function gives direct index to store or find data

Space: O(n) because we store n keys in an array of fixed size

vs Alternative: Compared to searching a list which is O(n), hash tables give faster access by jumping directly to the index

Edge Cases

Inserting keys that produce the same index (collision)

Current code overwrites existing key; real hash tables handle collisions with chaining or probing

DSA Python

self.table[index] = key

Empty key string

Hash function returns 0, key stored at index 0

DSA Python

return sum(ord(c) for c in key) % self.size

When to Use This Pattern

When you need very fast lookup or insertion by key, think of hash tables because they use math to jump directly to data location.

Common Mistakes

Mistake: Not using modulo operation in hash function causing index out of range
Fix: Always use modulo by table size to keep index within bounds

Mistake: Ignoring collisions leading to data loss
Fix: Implement collision handling like chaining or open addressing

Summary

It stores data by converting keys into indexes using a hash function for quick access.

Use it when you want fast search, insert, or delete by key.

The key insight is that a hash function turns keys into direct positions to avoid slow searching.