What is a Hash Map?

Updated Apr 28, 2026

Short answer

A Hash Map is a data structure that stores data as key-value pairs and uses a hash function to quickly locate values based on their keys. It provides average O(1) time complexity for insertion, deletion, and lookup operations. Hash maps are widely used when fast access to data is more important than maintaining a specific order.

Deep explanation

A Hash Map (also called a hash table or dictionary in some languages) stores information in the form of key-value pairs.

Example:

TEXT

1Key          Value
2
3101   ->     "Alice"
4102   ->     "Bob"
5103   ->     "Charlie"

Instead of searching through every item, a hash map uses a hash function to calculate where a key should be stored.

How a Hash Map Works

A hash map internally uses:

An array of buckets
A hash function
A collision handling mechanism

1. Hash Function

A hash function converts a key into an integer value called a hash code.

Example:

TEXT

1Key:
2
3"apple"
4
5Hash Function:
6
7"apple" -> 245678

The hash code is then converted into an array index:

TEXT

Index = hash code % number of buckets

245678 % 10 = 8

The key-value pair is stored in bucket 8.

Example:

TEXT

1Buckets:
2
30
41
52
63
74
85
96
107
118 -> ("apple", 100)
129

When searching for "apple":

The hash function runs again.
The same bucket index is calculated.
The value is retrieved directly.

This avoids checking every element.

Key Components of a Hash Map

Keys

Keys are unique identifiers used to access values.

Example:

TEXT

1User ID -> User Information
2
31001 -> Alice
41002 -> Bob

Two entries cannot have the same key.

---

Values

Values are the actual data stored.

Example:

TEXT

"username" -> "john123"

Multiple keys can have similar values.

---

Buckets

Buckets are storage locations inside the hash map.

Example:

TEXT

1Bucket Array:
2
30   []
41   []
52   [key-value pair]
63   []
74   [key-value pair]

The hash function determines which bucket stores each entry.

Collision Handling

A collision occurs when two different keys produce the same bucket index.

Example:

TEXT

"cat"  -> bucket 3

"dog"  -> bucket 3

Both keys want the same location.

Hash maps handle collisions using techniques such as:

Separate Chaining

Multiple entries are stored in the same bucket.

Example:

TEXT

1Bucket 3:
2
3(cat, value1)
4      |
5(dog, value2)

Open Addressing

The map searches for another available bucket.

Example:

TEXT

1Bucket 3 occupied
2
3Try bucket 4
4
5Store entry in bucket 4

Time Complexity of Hash Map Operations

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

The average case is fast because hashing allows direct access.

The worst case occurs when many keys collide and many entries end up in the same bucket.

Load Factor and Resizing

The load factor measures how full the hash map is.

Formula:

TEXT

Load Factor = Number of Entries / Number of Buckets

Example:

TEXT

1Entries = 75
2Buckets = 100
3
4Load Factor = 0.75

When the load factor becomes too high:

A larger bucket array is created.
Existing entries are rehashed.
Entries are redistributed.

This reduces collisions.

Although resizing takes O(n) time, insertions remain O(1) on average because resizing happens occasionally.

Hash Map vs Array

Feature	Array	Hash Map
Access by index	`O(1)`	Not applicable
Search by key	`O(n)`	`O(1)` average
Ordering	Maintains order	Usually unordered
Memory usage	Lower	Higher due to hashing overhead
Best use	Indexed data	Key-based lookup

Hash Map vs TreeMap

Feature	Hash Map	TreeMap
Internal structure	Hash table	Balanced tree
Ordering	No sorted order	Sorted keys
Lookup	Average `O(1)`	`O(log n)`
Range queries	Not efficient	Efficient

Use a Hash Map when speed is the priority.

Use a TreeMap when sorted keys are required.

Common Hash Map Operations

Insert

Python

1users = {}
2
3users["101"] = "Alice"
4users["102"] = "Bob"

Lookup

Python

name = users["101"]

print(name)

Output:

TEXT

Alice

Delete

Python

del users["101"]

Real-world example

A web application may store user information using a hash map.

The user's ID acts as the key:

Python

1users = {
2    101: "Alice",
3    102: "Bob",
4    103: "Charlie"
5}
6
7print(users[102])

Output:

TEXT

Bob

Without a hash map, the application might need to search through every user:

TEXT

User 1 -> check
User 2 -> check
User 3 -> found

With a hash map:

TEXT

1User ID 102
2
3Hash Function
4
5102 -> Bucket 5
6
7Retrieve Bob

The lookup is much faster, which is why hash maps are commonly used for:

User databases.
Caching systems.
Dictionaries.
Counting frequencies.
Storing configuration settings.

Common mistakes

* Thinking a hash map stores keys in sorted order.
* Assuming hash maps always guarantee `O(1)` performance.
* Forgetting that collisions can occur.
* Confusing a hash map with an array.
* Assuming duplicate keys can exist in a hash map.
* Ignoring the extra memory used by hash tables.
* Using a hash map when ordered traversal is required.
* Forgetting that poor hash functions can reduce performance.
* Assuming the hash value itself is the storage location without considering bucket calculation.

Follow-up questions

How does a hash map achieve average O(1) lookup time?
What happens when two keys have the same hash value?
Why does a hash map need to resize?
What makes a good hash function?
Why can a hash map not guarantee O(1) operations in every case?
When should you use a hash map instead of a list or array?

Short answer

Deep explanation

How a Hash Map Works

1. Hash Function

Key Components of a Hash Map

Keys

Values

Buckets

Collision Handling

Separate Chaining

Open Addressing

Time Complexity of Hash Map Operations

Load Factor and Resizing

Hash Map vs Array

Hash Map vs TreeMap

Common Hash Map Operations

Insert

Lookup

Delete

Real-world example

Common mistakes

Follow-up questions

More Heaps and Maps interview questions