Hashing

Imagine you have a huge box of files and you need to find one specific file instantly, without flipping through every page. That is exactly what hashing lets you do in programming. It is one of the most useful tricks for making your code fast, and once you understand it, you will start seeing it everywhere.

What Even Is Hashing?

Okay, simple version: hashing is a way to find data almost instantly, instead of searching for it one item at a time.

Normally, if you wanted to check if 42 exists in a list like this:

[15, 23, 42, 7, 91]

You would have to check each number one by one until you find it. That takes time, and the bigger the list, the longer it takes.

With hashing, instead of searching, you calculate exactly where something should be. You ask a small helper called a hash function to give you the exact spot, and you go straight there.

index = hash(key)

For example:

hash(42) = 2

So you jump directly to index 2. No searching, no scanning. Just straight to the answer.

Tip

Think of hashing like a library that uses a smart numbering system instead of alphabetical shelves. Instead of walking past every shelf, you type in the book’s code and a machine tells you exactly which shelf and slot it sits on. That is what a hash function does for your data.

Hash Tables - Where the Data Actually Lives

A hash table is simply an array (a list of slots) where data is stored using the index that the hash function gives us.

Index: 0   1   2   3   4
Data:  -  23  42   -  15

Here, the number 23 lives at index 1 because the hash function said so. The number 42 lives at index 2. Every piece of data has its own calculated home.

This is the magic that lets hash tables do lookups, insertions, and deletions in roughly constant time, which in plain English means “it stays fast no matter how much data you add.”

The Hash Function - The Brain Behind It All

A hash function is the small piece of logic that takes a key (like a number or a word) and turns it into an index.

h(key) -> a number between 0 and (table_size - 1)

For a hash function to actually be useful, it needs to follow a few simple rules:

• Same input, same output every time. If you hash 42 today, you should get the same index tomorrow.
• Spread things out evenly. You do not want everything piling up at index 0 while the rest of the table sits empty.
• Be fast. The whole point of hashing is speed, so the calculation itself needs to be quick.
• Avoid clashes as much as possible. Two different keys landing on the same spot should be rare, not common.

A Few Common Ways to Build a Hash Function

The division method

This is the simplest and most common approach. You just divide and take the remainder.

h(key) = key % table_size

Example:

table_size = 10
key = 23
h(23) = 23 % 10 = 3

The multiplication method

h(key) = floor(table_size * (key * A % 1))

Here, A is usually a constant like 0.618. This spreads keys out more evenly than simple division in some cases.

The mid-square method

You square the key, then grab the middle digits of the result.

key = 12
12 squared = 144
middle digit = 4

String hashing (used for words and text)

Numbers are easy, but what about words? You convert each character to a number and combine them with a formula like this:

hash = sum of (character_value * p^position) % table_size

This is roughly how Python dictionaries handle text keys behind the scenes, with extra optimizations layered on top.

Collisions - When Two Keys Want the Same Spot

What Is a Collision?

Sometimes two completely different keys end up pointing to the exact same index. This is called a collision.

h(10) = 2
h(20) = 2

Both 10 and 20 want to live at index 2. Only one of them can actually be there, so we need a plan for what happens next.

Caution

Collisions are not a sign that something is broken. They are expected and normal. What matters is how well your hash table handles them when they happen.

There are two main families of solutions for this:

1. Open Addressing - find another empty spot inside the same table
2. Chaining - let multiple keys share the same spot using a small list

Let us go through each one.

Open Addressing - Find Another Seat

With open addressing, every key still lives inside the main table. If a spot is taken, the key politely looks for the next available seat.

Linear Probing

The simplest version: if your spot is taken, just check the next one, and the next, and so on.

(h(key) + i) % table_size

Here i starts at 0 and increases by 1 each time you hit an occupied slot.

Walking through an example

Let us insert 10, 20, and 30 into a table of size 7.

h(10) = 3        -> slot 3 is empty, place it there
h(20) = 3        -> collision! try slot 4 -> empty, place it there
h(30) = 3        -> collision! slot 4 taken too, try slot 5 -> empty, place it there

Final table:

Index: 0 1 2 3  4  5  6
Data:  - - - 10 20 30 -

How it looks in code

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

    def insert(self, key):
        index = key % self.size
        i = 0
        while self.table[index] is not None:
            i += 1
            index = (key % self.size + i) % self.size
        self.table[index] = key

The downside: Primary Clustering

Once a few keys land next to each other, they form a little group:

[10, 20, 30, 40]

Now any new key that collides with this group has to walk past the entire group before finding a free spot. This pile-up effect is called primary clustering, and it slowly makes your hash table feel like a regular slow search again, closer to O(n) than O(1).

Quadratic Probing

To avoid the clustering problem, instead of moving one step at a time, you jump using squares.

(h(key) + i^2) % table_size

Example

collision at index 3
try 3 + 1^2 = 4
try 3 + 2^2 = 7 (wrapped using % table_size)

In code

def insert(self, key):
    h = key % self.size
    for i in range(self.size):
        index = (h + i * i) % self.size
        if self.table[index] is None:
            self.table[index] = key
            return

A new problem: Secondary Clustering

Quadratic probing fixes primary clustering, but creates a smaller version of the same issue. Keys that start at the same index will always follow the exact same jumping pattern, even if there is free space sitting right in between them that they never check.

h(10) = 3
h(20) = 3
Both follow the exact same i^2 jump sequence

This is called secondary clustering. It is less severe than primary clustering, but it is still not perfect.

Double Hashing

This is the cleverest of the three, and the one most people consider the best open addressing technique.

Instead of using a fixed pattern like “+1” or “+i squared,” you use a second hash function to decide how big each jump should be.

index = (h1(key) + i * h2(key)) % table_size

Example setup

h1(key) = key % size
h2(key) = 1 + (key % (size - 1))

In code

for i in range(size):
    index = (h1(key) + i * h2(key)) % size
    if table[index] is None:
        # insert here
        break

Because the jump size itself depends on the key, different keys end up following completely different paths, even if they started at the same spot. This gets rid of both primary and secondary clustering, which is why double hashing is considered the strongest open addressing method.

Chaining - Sharing a Spot Peacefully

Instead of forcing every key to find its own private slot, chaining lets multiple keys live happily at the same index by storing them in a small list.

Index 0 -> 10 -> 20 -> 30
Index 1 -> 5 -> 15

Think of each index as a small parking lot, and the list as cars parked one behind another. If two keys hash to the same index, no problem, they just queue up.

Inserting

index = hash(key)
table[index].append(key)

In code

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def insert(self, key):
        index = key % self.size
        self.table[index].append(key)

Searching

index = hash(key)
look through the small list at that index

How fast is it?

• On average, it is still close to O(1) because each list usually stays short
• In the worst case (if everything ends up in one bucket), it slows down to O(n)

Load Factor - How Full Is Too Full?

What Is Load Factor?

The load factor tells you how crowded your hash table is.

Load Factor = number of elements stored / total table size

Example:

10 elements stored in a table of size 20
Load Factor = 10 / 20 = 0.5

Why It Matters

The fuller your table gets, the more often collisions happen, and the slower your hash table becomes. A nearly empty table is fast. An overcrowded table starts behaving like a regular slow list.

As a rough guideline:

• For open addressing, try to stay under a load factor of 0.7
• For chaining, you can safely go up to 1.0 since multiple keys per slot is expected

Rehashing - Giving Your Table More Room

What Is Rehashing?

When your hash table gets too full (load factor crosses the safe threshold), it is time to upgrade to a bigger table. This process is called rehashing.

Here is what happens step by step:

1. Create a brand new, bigger table - usually double the size of the old one.

2. Go through every existing key - one at a time, from the old table.

3. Recompute its hash for the new table size - since the table size changed, the index changes too.

4. Insert it into the new table - place it at its newly calculated index.

In code

def rehash(self):
    old_table = self.table
    self.size *= 2
    self.table = [[] for _ in range(self.size)]
    for bucket in old_table:
        for key in bucket:
            self.insert(key)

Yes, rehashing touches every single element, so it takes O(n) time when it happens. But here is the good part: it does not happen often. Most of the time, insertions stay at O(1), and rehashing only kicks in occasionally. When you average it out over many insertions, it still works out to O(1) per insertion. This is called amortized constant time.

How Python Dictionaries Actually Work

Python’s built-in dict is basically a hash table that has been heavily optimized in C. A few interesting facts about it:

• It uses hashing combined with open addressing internally
• It uses a clever trick called perturbation (a variant of probing) to reduce clustering
• It automatically resizes itself as it grows, just like the rehashing process above
• It uses some randomization in its hashing for security reasons, so the same data does not always hash the exact same way across different program runs

So every time you write my_dict[key] = value in Python, all of this machinery is quietly working underneath.

Open Addressing vs Chaining - Which One Wins?

Both approaches solve the same problem in different ways, and each comes with trade-offs.

Open Addressing

Good things:

• Cache friendly, since everything lives in one array
• No extra memory needed for pointers
• Simple to understand and implement

Not so good things:

• Suffers from clustering
• Deleting items is tricky (you need placeholder “tombstones”)
• Gets noticeably slower as the table fills up

Chaining

Good things:

• Deleting items is simple and clean
• Load factor can safely go above 1.0
• No clustering issues at all

Not so good things:

• Needs extra memory for the linked lists
• Less cache friendly than open addressing
• Worst case can still be O(n) if buckets get unlucky

How Fast Is Hashing, Really?

Operation	Average Case	Worst Case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

The worst case only shows up when your hash function is poorly chosen, or the table is badly overloaded. With a decent hash function and reasonable load factor, you will almost always get that fast O(1) behavior.

Things Worth Knowing for Interviews

• Hashing does not keep your data in sorted order. If you need sorted data, hashing is the wrong tool.
• The quality of your hash function makes or breaks performance. A bad hash function can turn O(1) into O(n).
• Load factor is the main dial that controls how well your hash table performs.
• Python’s dictionary uses open addressing under the hood.
• Java’s HashMap uses chaining, and even upgrades buckets to a balanced tree structure once they get too crowded (this is called treeification).
• Collisions always need an explicit strategy. They never just resolve themselves.
• Rehashing looks expensive on a single operation, but averages out to cheap (O(1)) across many operations.

When Should You Reach for Hashing?

Use hashing when:

• You need really fast lookups
• You do not care about keeping things in order
• Your keys are unique, or you can handle the few that collide

Avoid hashing when:

• You need range queries (like “give me everything between 10 and 50”)
• You need to walk through your data in sorted order
• Memory is extremely tight, since hash tables often need extra space to stay fast

Tip

A simple way to decide: if your main question is “does X exist?” or “give me the value for this key,” hashing is usually your best friend. If your question involves order, ranges, or “what comes next,” look at trees or sorted structures instead.

Quick Reference

Hash Function

Converts a key into an array index. Should be fast, consistent, and spread keys out evenly to avoid collisions.

Collision

When two different keys land on the same index. Completely normal, but needs a clear strategy to handle.

Open Addressing

Find another free slot inside the same table when a collision happens. Includes linear probing, quadratic probing, and double hashing.

Chaining

Let multiple keys share the same index by storing them in a small list. Simple and avoids clustering entirely.

Load Factor

Elements stored divided by table size. Higher load factor means more collisions and slower performance.

Rehashing

Growing the table and reinserting everything once it gets too full. Expensive once in a while, cheap on average.

Summary

The Core Idea

• Hashing turns a key into an index using a hash function, so you can find data almost instantly
• A hash table is just an array where data lives at its calculated index
• Collisions happen when two keys land on the same index, and that is completely normal
• The two main fixes for collisions are open addressing and chaining

Collision Handling

• Linear probing - check the next slot one at a time, can cause primary clustering
• Quadratic probing - jump using squared steps, can cause secondary clustering
• Double hashing - use a second hash function for jump size, avoids both clustering problems
• Chaining - let keys share a slot using a small list, simple and clustering-free

Interview Tips

• Know the difference between average case O(1) and worst case O(n)
• Be ready to explain load factor and why it matters
• Understand why rehashing is needed and why it is still considered efficient overall
• Remember that hashing sacrifices order for speed
• Python dict uses open addressing, Java HashMap uses chaining