Introduction

In data structures, a Map is a very important abstract data type used to store data in the form of key-value pairs. A map allows us to associate a unique key with a specific value. Later, we can use that key to quickly access, update, or delete the value.

Map is one of the most commonly used data structures in programming because real-world data is often represented as a relationship between two things. For example, a roll number is related to a student name, a username is related to a user profile, and a product ID is related to product details.

Definition of Map

Each key in a map is unique. A key works like an identifier, and the value is the actual data associated with that key. If we know the key, we can directly find its value without searching every element one by one.

Basic Example

{
    "101": "Rumman",
    "102": "Amit",
    "103": "Priya"
}

In the above example, 101, 102, and 103 are keys. Rumman, Amit, and Priya are their corresponding values.

Real-Life Example of Map

If we want to find the student name for roll number 102, we can directly use the key 102 and get the value Amit Kumar.

Prerequisites to Understand Map

Before learning Map in data structure, students should have basic knowledge of the following topics:

Why Do We Need Map?

Suppose we have a large list of employees and we want to find employee details using employee ID. If we store all employees in a simple array, we may need to search one by one until we find the correct employee. This is slow when the number of records is large.

A map solves this problem by storing employee ID as the key and employee details as the value. So, instead of checking all records one by one, we can directly access the required record using its key.

Structure of Map

A map contains multiple entries. Each entry has two important parts:

Characteristics of Map

Basic Operations on Map

A map supports several important operations. These operations allow us to add, search, update, remove, and display key-value pairs.

Map Operations Summary

Map Example Using JavaScript

JavaScript provides a built-in Map object. It stores data as key-value pairs and provides methods such as set(), get(), has(), delete(), and clear().

// Creating a Map
let students = new Map();

// Insert key-value pairs
students.set(101, "Rumman");
students.set(102, "Amit");
students.set(103, "Priya");

// Search value using key
console.log(students.get(101));

// Check if key exists
console.log(students.has(102));

// Update value
students.set(102, "Amit Kumar");

// Delete key-value pair
students.delete(103);

// Display complete map
console.log(students);

Output

Rumman
true
Map(2) { 101 => 'Rumman', 102 => 'Amit Kumar' }

Map Example Using Java HashMap

In Java, the Map interface is commonly implemented using classes such as HashMap, LinkedHashMap, and TreeMap. The following example shows how to use HashMap.

import java.util.HashMap;
import java.util.Map;

public class MapExample {
    public static void main(String[] args) {

        Map<Integer, String> students = new HashMap<>();

        // Insert key-value pairs
        students.put(101, "Rumman");
        students.put(102, "Amit");
        students.put(103, "Priya");

        // Search value using key
        System.out.println(students.get(101));

        // Update value
        students.put(102, "Amit Kumar");

        // Delete value
        students.remove(103);

        // Display all key-value pairs
        for (Map.Entry<Integer, String> entry : students.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

Output

Rumman
101 -> Rumman
102 -> Amit Kumar

Internal Working of Map

A map can be implemented in different ways. The most common implementations are: Hash Table and Tree. The internal implementation affects performance, order, and use cases.

Hashing in Map

Hashing is a technique used to convert a key into an index. This index helps the map decide where the value should be stored in memory.

Suppose the key is 101 and the table size is 10.

This means the value for key 101 may be stored at index 1. This direct calculation makes map searching very fast in average cases.

Collision in Map

A collision occurs when two different keys generate the same index after applying the hash function. Since both keys want to use the same index, the map must handle this situation.

Collision Example

Here, both 101 and 111 generate the same index 1. This situation is called a collision.

Collision Handling Techniques

Types of Map

Maps can be classified based on ordering and internal implementation.

Hash Map vs Tree Map

Time Complexity of Map

Time complexity depends on the internal implementation of the map. A hash-based map usually gives faster average performance, while a tree-based map provides sorted order with logarithmic time.

Space Complexity of Map

The space complexity of a map is generally O(n), where n is the number of key-value pairs. This is because memory is required to store each key and its associated value.

Hash-based maps may require extra memory for buckets, empty slots, or collision handling structures. Tree-based maps may require extra memory for tree nodes and references.

Map vs Array

Arrays and maps both store data, but they solve different problems. Arrays are best when we want to access data using numeric indexes. Maps are best when we want to access data using meaningful keys.

Map vs Set

Map and Set are both useful data structures, but they are used for different purposes. A map stores key-value pairs, while a set stores only unique values.

Map Implementation Methods

Practical Example: Counting Frequency Using Map

One of the most common uses of a map is frequency counting. In this problem, each item becomes a key and its count becomes the value.

let numbers = [10, 20, 10, 30, 20, 10];

let frequency = new Map();

for (let number of numbers) {
    if (frequency.has(number)) {
        frequency.set(number, frequency.get(number) + 1);
    } else {
        frequency.set(number, 1);
    }
}

console.log(frequency);

Output

Map(3) { 10 => 3, 20 => 2, 30 => 1 }

In this example, the number is used as the key and the number of occurrences is stored as the value. This technique is commonly used in competitive programming, data analysis, text processing, and search engines.

Advantages of Map

Disadvantages of Map

Applications of Map

Maps are used in many real-world systems because they provide a clean and efficient way to connect keys with values.

When Should We Use Map?

Common Mistakes Students Make

Interview Questions on Map

Quick Revision

Conclusion

A Map is one of the most useful data structures in computer science. It stores data in the form of key-value pairs, where each key is unique and is used to access its related value. This makes maps extremely useful for fast searching, updating, and deleting data.

Maps are used in many real-world applications such as student management systems, employee records, e-commerce product catalogs, databases, caching systems, search engines, and compilers. Depending on the requirement, maps may be implemented using hash tables for speed or tree structures for sorted order.