what the hash

20 Aug, 2026

A genius once said, "If you don't know how to solve a problem, throw HashMap at it." I might have made it up myself, but regardless, it's a strategy I often use while solving DSA problems. This made me curious: how does such a versatile data structure actually work?

I knew that it involved hashing keys and storing them (duh!). But how exactly does it do it under the hood? Well, the only way to find out was by implementing a HashMap from scratch, and that's what I did.

In its simplest form, a HashMap has two components: a hash function which gives an integer value for a key, and an array where we actually store the values associated with the key. The first step of storing something in a HashMap is hashing the key to determine the location of the key in the array based on its index.

There are many ways to hash a key before you store it in a map, and they get progressively more complex. For this article, we'll keep it relatively simple.

Suppose we want to insert ("python", 10) into our HashMap. We can start with the simplest possible hash function, which can just add the ASCII value of each letter in the key. Using this function, we would get:

hash("python") = 674

Initially, the length of our array is 16, which is less than 674, so we cannot directly store the key "python" at location 674. To get the location of the key in the array, we do a modulo operation on the hash value with the length of the array.

In our example:

674 % 16 = 2

So we can store ("python", 10) at index 2 of our array.

The problem with this approach is that we can end up with multiple keys having the same hash value and consequently the same index because our hash function is very simple. We can end up with the same hash value even with complex hash functions, but a good hash function makes these collisions relatively uncommon.

Regardless, collisions are inevitable. We need a collision strategy which will determine what to do when two keys want to occupy the same location. We'll discuss that later.

Continuing with hash functions, let's make the function a little bit more complicated so that we can spread out hash values and reduce collisions. A common method to hash string inputs is:

hash (s) = \sum_{i = 0}^{n - 1} s [i] \cdot p^{n - 1 - i}

This is a polynomial rolling hash. We choose a prime number such as 31 for $p$ , which makes character order matter. For example, "ab" and "ba" produce different values under this scheme, although, like any finite hash function, collisions are still possible.

Integers are already represented as binary data in memory. To improve the distribution of integer values, hash functions can mix their bits. One simple example is:

hash (x) = (x \cdot 2654435761) (\mod 2^{32})

Similarly, we can hash floats, booleans, tuples, and other objects. The important requirement is that the hash of a key must remain consistent while that key is being used in the HashMap.

This is one of the reasons mutable objects make problematic keys. Consider this example where we try to insert:

map[["a", "b"]] = 10

Suppose, hypothetically, that our HashMap allowed lists as keys and:

hash(["a", "b"]) = A

We then modify the list:

key = ["a", "b"]
# ...
key.remove("b")

Now the key has changed:

["a", "b"] → ["a"]

and therefore its hash could change:

hash(["a"]) = B

If we now try to retrieve the value using the modified key, our HashMap would look in the location determined by B, even though the value was originally stored at the location determined by A.

The entry hasn't disappeared. We've effectively lost the ability to find it. This is why Python doesn't allow mutable built-in containers such as lists, sets, and dictionaries to be used as dictionary keys.

Now that we understand hashing, we have a problem.

What happens when two different keys produce the same index?

Collision

Let's say we have:

capacity = 16

and two keys:

"python"
"java"

both happen to produce an index of 2.

Our array now looks something like:

index
  0    [ ]
  1    [ ]
  2    ["python", 10]
  3    [ ]
  4    [ ]
  ...

Where do we put "java"?

We obviously can't overwrite "python".

There are several ways to solve this problem. One common approach is separate chaining, where every position in the array contains another data structure, usually a linked list or some kind of dynamic array.

It would look something like:

index 2

["python", 10] → ["java", 20] → ["ruby", 30]

Every key that hashes to index 2 gets added to the chain. This is a valid approach. There is another approach called open addressing which i have implemented. The only reason being, deletion is slightly difficult in case of separate chaining. With open addressing, everything lives directly inside the array. If index 2 is already occupied, we look at the next index.

index 2       index 3

["python",10] ["java",20]

If index 3 is also occupied, we keep going.

2       3       4       5
[P]     [J]     [R]     [ ]

This particular strategy is called linear probing.

The probing sequence is simply:

index
index + 1
index + 2
index + 3
...

with wraparound when we reach the end of the array. With linear probing, we stop searching we come across an EMPTY slot. Finding an EMPTY slot means the key could never have been placed beyond it. However, if there are no empty slots, does that mean we keep searching forever? No. We remember where we started our search and if we encounter the same starting point again, we can be sure that the key we are searching for is not present in the map.

Load Factor and Resizing

Linear probing works well when the table isn't too full. Imagine a table with 16 slots and only 2 entries:

[X] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Most keys will find their position immediately.

Now imagine 14 entries:

[X] [X] [X] [X] [X] [X] [X] [X]
[X] [X] [X] [X] [X] [X] [ ] [ ]

Now collisions are much more likely, and probe sequences become longer. We therefore need a way to measure how full the table is. To determine how full the table is, we use load factor defined as:

load factor = \frac{number of live entries}{capacity}

Load factor determines when we should increase the capacity of our table. For example, if load factor = 0.5, we double the capacity of our table. When we double the capacity, we need to rebuild the entire table. This means we need to get the new indexes based on new capacity as well because changing the capacity changes the index. For example:

For example:

hash(key) = 674

674 % 16 = 2
674 % 32 = 2

Therefore, after resizing, every live key needs to be rehashed and inserted into the new table. This makes resizing an $O (n)$ operation. That sounds expensive, but it doesn't happen on every insertion. Because the table grows exponentially, the cost of resizing is spread across many insertions, giving us O(1) amortized insertion time.

While calculating index, instead of doing:

index = hash_value % capacity

we can do:

index = hash_value & (capacity - 1)

Reason behind this that our capacity is always power of 2. We can exploit this fact and avoid doing expensive modulo operations and instead do a bitwise AND which is relatively cheaper.

Deletion

Insertion and lookup are relatively straightforward. While deleting something, we can simply get the index of key in our table and set it to EMPTY so that it can be reused later. But this breaks probing sequence.

Consider:

hash(A) = 5
hash(B) = 5

We insert both:

index:   0 1 2 3 4 5 6 7

         . . . . . A B .

A gets index 5.

B also hashes to index 5, sees that it's occupied, and gets placed at index 6.

Now delete A.

If we turn index 5 into EMPTY:

         . . . . . . B .

Now while we search for B, we start at index 5 because hash(B) = 5. But index 5 is empty and our lookup concludes, that key is not present in map because we always ensure that earliest EMPTY is always occupied. However, B is present at index 6. To solve this, we introduce tombstones.

Tombstones

We need to distinguish between EMPTY and DELETED. An EMPTY slot means it has never been occupied and DELETED means something occupied this slot before but now it is deleted so we need to continue probing. So after deleting A:

. . . . . D B .

where D represents a tombstone.

Now when we search for B:

5 → DELETED → 6

We continue probing and find it.

Tombstones solve deletion, but they introduce another problem.

Suppose we repeatedly:

insert
delete
insert
delete
insert
delete
...

Over time, the table can accumulate more and more tombstones.

Suppose we have:

capacity = 1024
live entries = 100
tombstones = 924
empty slots = 0

If we only look at the normal load factor:

\frac{100}{1024} \approx 9.8 %

it looks like the table is almost completely empty. But from the perspective of linear probing, we will continue searching because we don't stop our search when we encounter DELETED. An unsuccessful lookup can therefore require a full traversal of the table. Hence, we need to introduce effective occupancy defined as:

effective occupancy = \frac{live entries + tombstones}{capacity}

In this example:

\frac{100 + 924}{1024} = 100 %

Walking through 1024 slots to determine that key is not present in table is terrible.

Hence, we need to rehash table to get rid of tombstones. Once our table reaches a certain threshold of effective occupancy, we need to rehash the table before inserting the new key to get rid of tombstones. To resize:

1. Create a new array of same capacity
2. Iterate over the old array
3. Copy all the live entries in new array

This is similar to resize operation where we double the capacity when load factor crosses a threshold except that the index of live entries remains same. Hence the hash map does to kind of rehashing:

Too many live entries
        ↓
      grow
capacity increases


Too many tombstones
        ↓
    rebuild
capacity stays the same

I initially assumed that lowering the rebuild threshold would always be better because it would keep the table cleaner. This was wrong assumption.

Consider:

load_factor = 0.75
rebuild_threshold = 0.50

Suppose the table reaches:

size = 50
capacity = 100

The effective occupancy is at least 50%, so we rebuild.

After rebuilding:

size = 50
deleted = 0
capacity = 100

But the live occupancy is still 50%. The next insertion checks the thresholds again. The rebuild threshold is still satisfied. And we enter a loop where we keep rebuilding on every insertion which makes insertion O(n) operation. In my benchmark, configurations where:

rebuild_threshold < load_factor

caused thousands of redundant rebuilds and roughly a 100× slowdown.

That gave me an important invariant for this particular rebuilding strategy:

rebuild_threshold \geq load_factor

A rebuild should remove tombstones, not put the table immediately back into a state where another rebuild is required.

Benchmarks results

At this point, the hash map i built was working. However, i wanted to compare it with python's built in dict and also see how it performs under pathological workloads of collisions and tombstones.

For random keys, my HashMap was roughly 20–40× slower than Python's dict, depending on the operation and dataset size. For example, at 100,000 entries:

Insertion

My HashMap: 113,223 µs
Python dict:  3,627 µs

and successful lookup:

My HashMap: 32,027 µs
Python dict: 1,447 µs

Python's dict is a highly optimized production implementation written in C, whereas mine is a Python implementation of the basic algorithm. On the pathological benchmarks:

I created keys that deliberately produce the same hash value.

With linear probing, if 1,000 keys all map to the same initial index, they form a long contiguous cluster:

[A][B][C][D][E][F][G]................

The first key takes one probe. The second takes two. The third takes three. And so on.

If I perform one lookup of the last key, the number of probes is approximately:

O (n)

And that's exactly what the benchmark showed.

For example, deliberately colliding keys produced approximately:

10 keys      → 10 probes
50 keys      → 50 probes
100 keys     → 100 probes
500 keys     → 500 probes
1,000 keys   → 1,000 probes
5,000 keys   → 5,000 probes

For normal keys, HashMap lookup is expected to be: O(1) but with pathological collisions, one lookup can become: O(n)

If I look up every key in the collision cluster, The total number of probes becomes:

1 + 2 + 3 + \dots + n

which is:

\frac{n (n + 1)}{2} = O (n^{2})

So an individual lookup is $O (n)$ in the worst case, while a workload consisting of one lookup for every key in the cluster can require $O (n^{2})$ total work.

One of the reasons we resize the table is to keep the load factor under control. But resizing also has another interesting effect. In our implementation, indexes are calculated as:

hash_value & (capacity - 1)

When the capacity doubles, we expose one additional bit of the hash value. So keys that previously mapped to the same index can get separated after resizing. In one experiment, I inserted 500 deliberately colliding keys into a small table. After several resizes, the table had a capacity of 1,024, and the maximum resulting cluster was only 8 entries. The larger table gave the hash function more possible indexes to distribute those values across.

Tombstone Degradation

The collision benchmarks demonstrated the theoretical worst case. I wanted to know how lookup performance changes as tombstones accumulate. I created workloads with controlled numbers of:

OCCUPIED
DELETED
EMPTY

I measured number of probes for this slots.

As the percentage of non-empty slots approached 100%, unsuccessful lookups increasingly had to traverse the table.

Eventually:

OCCUPIED = 100
DELETED = 924
EMPTY = 0

and an unsuccessful lookup had to traverse essentially the entire table before the cycle detection logic terminated it. This is exactly the pathological state that rebuilding is designed to prevent. To determine the load_factor and rebuild_threshold, i ran a grid search over:

load_factor:
0.50
0.65
0.75
0.85

rebuild_threshold:
0.50
0.65
0.75
0.85

across two different workloads:

A high-churn workload with 40,000 mixed insert/delete operations.
A read-heavy workload with 50,000 operations consisting mostly of lookups.

Configurations where:

rebuild_threshold < load_factor

were disastrous because of the rebuild-thrashing problem described earlier. Once that constraint was respected, the differences became much smaller. For my tested workloads, a load factor around 0.75 provided a useful balance between memory usage and performance. A higher load factor reduced the number of buckets further, while a lower load factor allocated more space to reduce potential clustering. My final configuration was:

self.load_factor = 0.75
self.rebuild_threshold = 0.85

So, How Does a HashMap Actually Work?

After going through all of this, the simple mental model I started with turned out to be both right and very incomplete.

At a high level:

                key
                 │
                 ▼
            hash function
                 │
                 ▼
          integer hash value
                 │
                 ▼
        map hash → array index
                 │
                 ▼
        ┌─────────────────┐
        │     buckets     │
        │                 │
        │ [ ] [ ] [A] [ ] │
        │ [B] [ ] [ ] [ ] │
        │ [ ] [C] [ ] [ ] │
        └─────────────────┘
                 │
                 ▼
        collision handling
        via linear probing

But there are several additional pieces needed to make the simple idea actually work:

Hash function
     ↓
Index calculation
     ↓
Collision resolution
     ↓
Load-factor management
     ↓
Resizing / rehashing
     ↓
Deletion
     ↓
Tombstones
     ↓
Tombstone rebuilding

And that's it.

Checkout the code for this implementation on github