-----

A HashMap is one of the most powerful and frequently used data structures in programming. It allows us to store data in key–value pairs and retrieve values in constant time on average.

HashMaps are heavily used in

Data lookups

Frequency counting

Caching

Indexing

System design components (LRU Cache, Databases, etc.)

Understanding HashMap fundamentals is mandatory for DSA interviews.

What is a HashMap?

A HashMap stores data in the form of (key → value) pairs.

Each key is unique

Each key maps to exactly one value

Lookup, insertion, and deletion are very fast

Example

"name" → "Piyush"

"role" → "Software Engineer"

"age" → 27

Here

"name" is the key

"Piyush" is the value

Why HashMap is Needed?

Consider this problem

Find whether a number exists in an array of 1 million elements.

Without HashMap

You scan the array

Time Complexity: O(n)

With HashMap

Store all numbers as keys

Direct lookup

Time Complexity: O(1) (average)

This is why HashMaps are so powerful.

How Does a HashMap Work Internally?

A HashMap works using three core concepts

1. Hash Function

A hash function converts a key into an integer (hash code).
hash("apple") → 234567

This hash determines where the value will be stored.

2. Buckets (Array Indexing)

Internally, a HashMap uses an array of buckets.

index = hash(key) % arraySize

Each index points to a bucket where data is stored.

3. Collision Handling

Two different keys can produce the same hash index.

This is called a collision.

HashMaps handle collisions using

Chaining (Linked List / Tree)
Open Addressing (less common in interviews)

Collision Handling Using Chaining

When multiple keys map to the same index

Index 2 → (key1, value1) → (key2, value2)
All elements are stored as a linked list (or tree in modern implementations).

Visual Representation

Array (Buckets)

0 → null

1 → ("cat", 5)
2 → ("dog", 3) → ("god", 7)

3 → null

4 → ("apple", 10)

"dog" and "god" collided

Stored together using chaining

Basic Operations in HashMap

1. Insert (Put)

Store a key-value pair.

2. Search (Get)

Retrieve value using key.

3. Delete (Remove)

Remove a key-value pair.

Code Example – HashMap Usage

JavaScript Example

const map = new Map();

Insert

map.set("apple", 10);
map.set("banana", 20);

Get

console.log(map.get("apple")); // 10

Delete

map.delete("banana");

Check existence

console.log(map.has("apple")); // true

Java Example - 

import java.util.HashMap;
public class Main {
  public static void main(String[] args) {
    HashMap<String, Integer> map = new HashMap<>();
    map.put("apple", 10);
    map.put("banana", 20);
    System.out.println(map.get("apple")); // 10
    map.remove("banana");

  }

}

C++ Example

#include <iostream>
#include <unordered_map>
using namespace std;
int main() {
    unordered_map<string, int> mp;
    mp["apple"] = 10;
    mp["banana"] = 20;
    cout << mp["apple"] << endl;
    mp.erase("banana");
    return 0;
}

Python Example

mp = {}
mp["apple"] = 10
mp["banana"] = 20
print(mp["apple"])  # 10

del mp["banana"]

Time Complexity of HashMap Operations

Operation Average Case Worst Case

Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)
Why worst case is O(n)?

If all keys collide and go into one bucket, HashMap behaves like a linked list.

Modern implementations optimize this using balanced trees.

Space Complexity

HashMap stores keys, values, and buckets

Space Complexity: O(n)

Common Interview Use Cases

HashMaps are commonly used in

Frequency counting problems

Two Sum problem

Detecting duplicates

Grouping anagrams

Subarray sum problems

Caching (LRU Cache)

Most Asked Interview Questions

Difference between HashMap and Array?

How does HashMap handle collisions?

Why HashMap average time is O(1)?

When does HashMap performance degrade?

Difference between HashMap and TreeMap?

When NOT to Use HashMap?

Avoid HashMap when

Order matters

Memory is very constrained

You need sorted keys

Use

TreeMap / Ordered Map instead

Summary

HashMap stores data as key–value pairs

Uses hash function + buckets

Very fast for lookup operations

One of the most important DSA topics

Appears in almost every coding interview

Mastering HashMap basics unlocks many advanced DSA problems. DSA With Piyush | DWP