How does a Hash Map work?

A Hash Map uses a "Hash Function" to convert a key into an index in an underlying array (buckets), allowing for O(1) average time search and insertion.

Chaining vs Open Addressing?

Chaining uses linked lists at each bucket to handle multiple keys. Open Addressing finds another empty slot in the array (e.g., Linear Probing) if a collision occurs.

What is the "Worst Case" complexity?

In the worst case (where all keys collide at the same bucket), operations become O(n). A good hash function and proper resizing keep this at O(1) average.

Hash Map (Hash Table)

A hash map (hash table) is a data structure that maps keys to values for fast lookup, insertion and deletion.

0 / 8 · LOAD 0.00

READY

Insert keys and watch where the hash sends them. A collision is two keys landing in one bucket — the two strategies below differ only in what happens next.

Key

Value

Collisions

Buckets

Intuition

Imagine a giant library where every book has a unique ID number. Instead of scanning every shelf to find a book, you use a magic formula (Hash Function) on the ID to get the exact aisle and shelf number immediately. If two books end up on the same shelf (Collision), you just stack them or place one next to the other.

Concept

Hash Function: Converts a given key (string, number, object) into an integer index valid for the array size.

Collision Handling: Strategies to handle cases where two keys hash to the same index.

Chaining: Store colliding elements in a linked list or dynamic array at that index.
Open Addressing (Linear Probing): If the slot is full, try the next slot (index+1) until an empty one is found.

How it Works

Insert (Put):

Compute hash h = hash(key).
Map to index i = h % capacity.
If slot i is empty, store the Key-Value pair.
If occupied, resolve collision (chain or probe).

Search (Get):

Compute hash and finding index i.
Check slot i. If key matches, return value.
If not, traverse chain or probe sequence to find it.

Step-by-Step Breakdown

Watch the visualization:

Input: You provide a Key and Value.
Hashing: The system computes the index (highlighted/animated).
Placement: The item is placed in the corresponding bucket.
Collision: Observe how Chaining creates a list vs Linear Probing finding the next spot.

When to Use

Applications:

Caching (e.g., in-memory caches like Redis).
Database indexing.
Counting frequencies of items.
Implementing Sets (Hash Set).

When NOT to Use

Sorted Data: Hash Maps do not maintain order. Use TreeMap/BST if order matters.
Worst-case guarantees: Poor hash functions or attacks can degrade performance to O(N).

How to Identify

"Fast lookup by ID", "Count occurrences", "Find duplicates", "Store relations".

Sample Problems

Two Sum

Find two numbers summing to target. Use Hash Map for O(1) loopups.

Group Anagrams

Map sorted string hash to list of original strings.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description

Bridges & Articulation Points

Hash Set

Complexity

Time (Best)

O(1)

Time (Average)

O(1)

Time (Worst)

O(N) (High Collisions)

Space

O(N)

Hash Map (Hash Table) Code

1class HashMap {
2    constructor(size = 50) {
3        this.buckets = new Array(size).fill(null).map(() => []);
4        this.size = size;
5    }
6
7    hash(key) {
8        let hash = 0;
9        for (let char of key) hash += char.charCodeAt(0);
10        return hash % this.size;
11    }
12
13    put(key, value) {
14        const index = this.hash(key);
15        const bucket = this.buckets[index];
16        const existing = bucket.find(item => item.key === key);
17        if (existing) existing.value = value;
18        else bucket.push({ key, value });
19    }
20
21    get(key) {
22        const index = this.hash(key);
23        const item = this.buckets[index].find(item => item.key === key);
24        return item ? item.value : undefined;
25    }
26    remove(key) {
27        const index = this.hash(key);
28        const bucket = this.buckets[index];
29        const at = bucket.findIndex(item => item.key === key);
30        if (at !== -1) bucket.splice(at, 1);
31    }
32}

Related Lessons