DSA Hash Maps

DSA Tutorial

DSA Hash Maps – Complete Beginner Guide

(Concept • Operations • Internal Working • Examples • Implementation • Complexity)

A Hash Map (also called Hash Table / Dictionary) is one of the most powerful data structures in DSA.
It stores data in key–value pairs and provides very fast access.

1️⃣ What is a Hash Map?

A Hash Map stores data as:

Key → Value

  • Key: Unique identifier

  • Value: Data associated with the key

  • Hash Function: Converts key into an index

Example

"India" → "New Delhi"
"USA" → "Washington"

📌 Keys must be unique, values can repeat.

2️⃣ Why Use Hash Maps?

✔ Very fast lookup
✔ Efficient insert & delete
✔ Direct access using keys
✔ Ideal for large datasets

📌 Average time complexity is O(1).

3️⃣ How Hash Map Works Internally

  1. Key is passed to a hash function

  2. Hash function returns an index

  3. Value is stored at that index

  4. If two keys get same index → collision

index = hash(key)

4️⃣ Hash Function

A good hash function:

  • Is fast

  • Distributes keys uniformly

  • Minimizes collisions

Example

hash(42) = 42 % 10 = 2

5️⃣ What is Collision?

A collision happens when:

hash(key1) == hash(key2)

Example:

hash(12) = 2
hash(22) = 2 ← collision

6️⃣ Collision Resolution Techniques

 1. Chaining

  • Each index stores a linked list

  • All collided elements go into that list

Index 2 → (12 → 22 → 32)

✔ Simple
❌ Extra memory

2. Open Addressing

Find another empty slot.

Types:

  • Linear Probing

  • Quadratic Probing

  • Double Hashing

✔ Memory efficient
❌ Clustering issues

7️⃣ Basic Hash Map Operations

Operation Description
Insert Add key–value pair
Search Get value using key
Update Modify value
Delete Remove key

8️⃣ Hash Map Example (C++ – STL)

 

Output (order may vary)

New Delhi
India → New Delhi
USA → Washington
France → Paris

9️⃣ Frequency Count Using Hash Map

( Very Common Interview Question)


 

🔟 Hash Map Implementation Idea (Conceptual)

hash(key) → index
store (key, value) at index
handle collision if needed

📌 Real implementations also handle resizing & rehashing.

1️⃣1️⃣ Load Factor

Load Factor = number_of_elements / table_size

  • High load factor → more collisions

  • Hash maps resize automatically when load factor exceeds limit

1️⃣2️⃣ Time Complexity

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

📌 Worst case occurs due to heavy collisions.

1️⃣3️⃣ Space Complexity

  • O(n) for storing elements

  • Extra space for buckets / chains

1️⃣4️⃣ Hash Map vs Hash Set

Feature Hash Map Hash Set
Stores Key–Value Values only
Duplicates Keys ❌ ❌
Use Case Mapping Uniqueness
Example Phonebook Unique IDs

1️⃣5️⃣ Real-Life Uses

✔ Phone directory
✔ Caching systems
✔ Database indexing
✔ Counting frequency
✔ Two-sum problems

Interview Questions (Hash Map)

Q1. What is a hash map?
👉 Key–value based data structure

Q2. Why hash map is fast?
👉 Direct indexing via hash function

Q3. What causes worst-case O(n)?
👉 Too many collisions

Q4. Difference between map & unordered_map?
👉 Ordered vs unordered

Final Summary

✔ Hash Maps store key–value pairs
✔ Use hashing for fast access
✔ Average O(1) operations
✔ Collisions handled internally
✔ Extremely important for DSA & interviews

You may also like...