How hash maps work.

This blog is a result of a short rabbit hole i went through as a part of me learning about hash indexing. I have also written a blog on hash indexing, you can check it out here.

Firstly, what problem does a hash map solve?

Imagine you have an array:

names= ["Bruh","Bro","Dude","Bob"]

If I ask you to find "Bob", you might scan the array until you find it.

Scanning through an array take O(n) time.

But image if you could calculate exactly where the value should live, instead of searching for it?

That's the central idea behind a hash map.

The hash function doesn't usually return an array index directly. It produces a hash value (using a hash function), which the hash map then converts into an index.

What is a hash function?

Simply put a hash function takes an input and transforms it into a number.

For example, imagine we create a simple hash function:

def hash_key(key):
    return sum(ord(char) for char in key)

ord() gives us the numeric value of a character.

For "cat":

• c → 99
• a → 97
• t → 116

Therefore:

h("cat")=99+97+116=312

This function converts strings into numbers. That's hashing.

You will notice "act" also produces 312, because addition doesn't care about character order.Real hash functions are better designed to distribute keys more effectively.

We need numbers because arrays use integer indices. Suppose our hash map uses an underlying array with 10 slots, indexed from 0 to 9. Our hash values might be much larger than 9, so we need to turn them into valid array indices.

A simple approach is the modulo operator:

index=h(key)mod capacity

For "cat": 312mod10=2
For "dog": 314mod10=4

Now we have valid array indices.

Our hypothetical hash table

This is the basic mechanism behind a hash map: hash the key, calculate an index, and use the underlying array to access the entry.

A hash function does not have to be cryptographically secure to work well in a hash map. General-purpose hash functions and cryptographic hash functions solve different problems.

For example, SHA-256 is designed for cryptographic uses. A programming language's built-in hashing mechanism is generally designed around efficient data-structure operations and its own requirements.

What happens when two keys get the same index?

I think this is probably everyone’s first question.

Suppose we insert "cat" and "tac".

Our terrible hash function gives both strings the same hash because their characters add up to the same number. Both end up at index 2. This is called a collision.

And collisions aren't just a problem with bad hash functions. Even good hash functions produce collisions when mapping a huge number of possible keys into a finite number of array slots. Collisions don't mean the hash map is broken. Collision resolution is part of the data structure's design.

There are two major strategies for handling them.

Strategy A: Separate chaining

Each array slot holds a collection of entries, often a linked list or another small structure (like an array).

For example:

Index 0:  empty
Index 1:  empty
Index 2:  cat -> tac -> act
Index 3:  empty
Index 4:  dog

When multiple keys hash to the same index, they share that bucket.

To look up "tac":

1. Hash "tac" to get index 2.
2. Go to bucket 2.
3. Search the entries in that bucket.
4. Compare the actual keys to find "tac".

Strategy B: Open addressing

Instead of storing a collection inside each bucket, every entry lives directly in the array. If the desired slot is occupied, the hash map searches for another available slot according to a probing strategy.

For example, with linear probing:

Index 0:  empty
Index 1:  empty
Index 2:  cat
Index 3:  tac    <- goes to the next available slot
Index 4:  dog
...

To find "tac", the map starts at index 2, sees "cat", checks the next slot, and finds "tac" at index 3. There are more sophisticated probing strategies, but that's the core idea.

Resizing

Imagine the underlying array has 10 slots, and you keep inserting hundreds of entries.

Eventually, the table gets crowded. Collisions become more frequent, and operations slow down.

Many hash maps solve this by resizing the underlying array and redistributing the entries.

For example:

Before:
Capacity = 10
Entries  = 8

Resize:

After:
Capacity = 20
Entries  = 8

The entries generally need to be placed again because their indices depend on the table's capacity:

index=h(key)mod capacity

If the capacity changes, the index can change too.

Resizing is expensive when it happens.

Time analysis

Operation	Average case	Worst case
Insert	O(1)	O(n)
Lookup	O(1)	O(n)
Delete	O(1)	O(n)

Why is the average case constant time?

• Calculating an index is constant time.
• Calculating a hash takes time based on the key's size.
• Accessing an array slot is constant time.

Strictly speaking, hashing a string of length k can take O(k) time if the hash must be calculated from scratch. So the usual O(1) claim assumes bounded-size keys or treats hash computation as constant time.

The worst case happens when many keys collide or cluster together, forcing the map to examine many entries.

But in chaining, there are multiple values in an bucket, so if there are m values inside a bucket why does it not take O(m) time to scan through a bucket ?

This is because of an important variable called the load factor;

α=n/m

Where:

• n = number of entries.
• m = number of buckets.
• α = average number of entries per bucket.

For our example:

α=1000/100​=10

If the load factor stays bounded as the table grows, and hashing distributes keys reasonably well, the expected time spent searching a bucket remains constant. Therefore O(α) == O(1) in such conditions.

Mini hash map

Lastly this is a mini hash map class i made in python (using the same old crappy hash function)

class Hash_Map:
    def __init__(self, capacity = 10):
        self.capacity = capacity
        self.hash = [[] for _ in range(capacity)]

    def hash_function(self, key):
        sum = 0
        for char in key:
            sum += ord(char) 
        return sum

    def get_index(self, key):
        return self.hash_function(key) % self.capacity

    def set(self, key, val):
        index = self.get_index(key)
        bucket = self.hash[index]

        for i, (oldKey, _oldVal) in enumerate(bucket):
            if oldKey == key:
                bucket[i] = (key, val)
                return

        bucket.append((key, val))

    def get(self, key):
        index = self.get_index(key)
        for old_key, val in self.hash[index]:
            if old_key == key:
                return val

        raise KeyError(key)