HashMap: The Algorithm Behind Fast Lookups

When solving algorithmic problems, we often need to answer a simple question:

“Have I seen this value before?”

A normal array requires searching element by element, which takes O(n) time. A HashMap can usually answer the same question in O(1) average time.

That makes HashMaps one of the most important data structures in algorithmic programming.

How Does a HashMap Work?

A HashMap stores data as:

key → value

For example:

"John" → 25
"Sarah" → 31
"Mike" → 42

When we insert a key, a hash function converts the key into a number:

"Sarah"
   ↓
hash function
   ↓
hash value
   ↓
table index

The HashMap uses this index to determine where the data should be stored.

When we want "Sarah" again, it performs the same calculation and can jump directly to the relevant location instead of searching everything.

Hash Collisions

Different keys can sometimes produce the same index.

For example:

hash("John")  → 4
hash("Sarah") → 4

This is called a collision.

HashMaps handle collisions using techniques such as:

• Separate chaining
• Open addressing

The goal is to keep lookup efficient even when collisions occur.

Why Is It O(1)?

For a well-designed HashMap:

OperationAverageSearchO(1)InsertO(1)DeleteO(1)

The worst case can reach O(n) when many collisions occur, but good hashing and resizing keep the average performance close to O(1).

Get 0xshel_’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The trade-off is memory: HashMaps use O(n) space to achieve fast access.

The Most Useful Algorithmic Pattern

HashMaps are especially useful when we need to remember information while iterating through data.

Consider the Two Sum problem:

[2, 7, 11, 15]
target = 9

Instead of checking every pair in O(n²), we can store numbers we’ve already seen.

def two_sum(numbers, target):
    seen = {}

    for i, number in enumerate(numbers):
        complement = target - number
        if complement in seen:
            return seen[complement], i
        seen[number] = i

For each number, we calculate:

complement = target - number

Then we ask the HashMap:

“Have I already seen this complement?”

Because lookup is O(1) on average, the entire algorithm becomes O(n).

When Should You Think About HashMaps?

Recognize these patterns:

“Have I seen this before?”
→ HashSet / HashMap

“How many times does each value appear?”
→ HashMap

“Find duplicates.”
→ HashSet

“Find two values that satisfy a condition.”
→ HashMap

“Associate each object with information.”
→ HashMap

The Core Idea

The most important concept is not the Python dictionary itself.

It is this:

Instead of searching for the information,
compute where the information should be.

A HashMap trades memory for speed, replacing repeated searches with fast average O(1) lookups.

Once you recognize this pattern, many O(n²) problems can be transformed into O(n) solutions.