Map Interface

Introduction

In the previous lesson, you learned about the Set Interface, which stores unique elements.

However, many real-world applications require storing data as key-value pairs.

For example:

A List stores only values.

A Set stores only unique values.

Neither is suitable for storing associations between two pieces of information.

Java solves this problem using the Map Interface.

The Map interface stores data as key-value pairs, enabling extremely fast lookups.

Map is one of the most widely used data structures in:

• Spring Boot
• Hibernate
• REST APIs
• Banking Applications
• Caching Systems
• Authentication Systems
• Microservices
• Distributed Systems

Mastering the Map interface is essential for Java interviews.

In this lesson, you'll learn:

• What is Map?
• Why Map is Needed
• Map Hierarchy
• HashMap
• LinkedHashMap
• TreeMap
• Hashtable
• Internal Working of HashMap
• Hashing
• Buckets
• Load Factor
• Resizing (Rehashing)
• Collision Handling
• Java 8 Treeification
• equals() & hashCode()
• Performance Analysis
• Best Practices
• Common Mistakes
• Hands-on Exercises
• Professional Interview Questions

What is a Map?

A Map stores data in the form of key-value pairs.

Each key is unique.

Each key maps to exactly one value.

Example:

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

employees.put(101, "Rahul");
employees.put(102, "Amit");
employees.put(103, "Jagannath");

Retrieving:

System.out.println(employees.get(102));

Output:

Amit

Why Map?

Suppose we need to find an employee by ID.

Using List:

List<Employee> employees;

Searching requires iterating through the list.

Using Map:

Map<Integer, Employee> employees;

Searching becomes much faster.

Benefits:

• Fast lookup
• Unique keys
• Easy updates
• Efficient retrieval
• Excellent scalability

Map Hierarchy

Unlike List and Set, Map does not extend Collection.

              Map
               │
      ┌────────┼──────────┐
      │        │          │
   HashMap LinkedHashMap TreeMap
      │
 Hashtable

Common Map Methods

put()

get()

remove()

containsKey()

containsValue()

keySet()

values()

entrySet()

size()

clear()

isEmpty()

Example:

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

map.put(1,"Java");

System.out.println(map.containsKey(1));

Output:

true

HashMap

HashMap is the most commonly used implementation of the Map interface.

Characteristics:

• Fast lookups
• Unique keys
• Allows one null key
• Allows multiple null values
• No ordering guarantee

Example:

Map<String,String> capitals =
        new HashMap<>();

capitals.put("India","New Delhi");

capitals.put("Japan","Tokyo");

Internal Working of HashMap

Internally:

HashMap

↓

Array of Buckets

↓

Bucket

↓

Linked List

↓

(Red-Black Tree if heavily collided)

Each bucket stores entries based on the key's hash value.

Hashing Process

When inserting:

map.put("Java",100);

Steps:

1. Compute hashCode()
2. Calculate bucket index
3. Check for existing key using equals()
4. Replace value if key exists
5. Otherwise create a new entry

Flow:

Key

↓

hashCode()

↓

Bucket

↓

equals()

↓

Store

Buckets

Example:

Bucket 0

↓

(Spring,100)

Bucket 1

↓

(Java,200)

Bucket 2

↓

(Hibernate,300)

Multiple entries may exist in the same bucket if collisions occur.

Hash Collisions

A collision occurs when two different keys map to the same bucket.

Example:

Key A

↓

Bucket 5

Key B

↓

Bucket 5

Java resolves collisions using linked lists and, from Java 8 onward, converts long collision chains into balanced trees under specific conditions.

Java 8 Treeification

Before Java 8:

Bucket

↓

Node

↓

Node

↓

Node

↓

Node

After Java 8 (when thresholds are met):

Bucket

↓

Red-Black Tree

This improves worst-case lookup performance from approximately O(n) to O(log n) for heavily collided buckets.

Load Factor

The Load Factor determines when a HashMap should resize.

Default:

0.75

Formula:

Current Entries

──────────────

Capacity

When the load factor threshold is exceeded, the HashMap grows and redistributes its entries.

Rehashing (Resizing)

Suppose capacity:

16

When the threshold is exceeded:

16

↓

32

The existing entries are redistributed across the new bucket array.

Although resizing is expensive, it occurs infrequently, allowing HashMap to maintain excellent average performance.

HashMap Time Complexity

*Worst-case assumes Java 8+ treeified buckets where applicable.

LinkedHashMap

LinkedHashMap extends HashMap by maintaining insertion order.

Example:

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

students.put(1,"Rahul");
students.put(2,"Amit");
students.put(3,"John");

Output:

1=Rahul
2=Amit
3=John

Internally, it combines hashing with a doubly linked list.

TreeMap

TreeMap stores entries sorted by their keys.

Internally, it uses a Red-Black Tree.

Example:

Map<Integer,String> marks =
        new TreeMap<>();

marks.put(80,"A");
marks.put(95,"A+");
marks.put(70,"B");

Output:

70=B
80=A
95=A+

Characteristics:

• Sorted keys
• No null keys
• O(log n) operations

Hashtable

Hashtable is a legacy synchronized implementation.

Example:

Hashtable<Integer,String> table =
        new Hashtable<>();

table.put(1,"Java");

Characteristics:

• Thread-safe
• No null keys
• No null values
• Slower due to synchronization

Modern applications typically use ConcurrentHashMap for concurrent access instead of Hashtable.

HashMap vs LinkedHashMap vs TreeMap vs Hashtable

equals() and hashCode()

For custom key classes:

class Employee {

    int id;

    String name;

}

Always override:

equals()

hashCode()

Without them:

• Duplicate logical keys may be stored incorrectly.
• Retrieval may fail because the map cannot locate the intended bucket.

Iterating Through a Map

Using entrySet():

for(Map.Entry<Integer,String> entry
        : employees.entrySet()){

    System.out.println(
        entry.getKey() + " : " +
        entry.getValue());

}

Using keySet():

for(Integer id : employees.keySet()){

    System.out.println(id);

}

Using values():

for(String name : employees.values()){

    System.out.println(name);

}

Real-World Example: Employee Directory

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

employees.put(101,"Rahul");

employees.put(102,"Amit");

employees.put(103,"Jagannath");

Finding an employee:

System.out.println(
    employees.get(103));

Real-World Example: Shopping Cart

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

cart.put("Laptop",2);

cart.put("Mouse",5);

cart.put("Keyboard",3);

Best Practices

Use HashMap by Default

Choose HashMap unless ordering or sorting is required.

Override equals() and hashCode()

Always override both methods when using custom key objects.

Prefer entrySet() for Iteration

It avoids unnecessary lookups and is generally more efficient than iterating over keySet() followed by get().

Use Immutable Keys

Changing a key's state after insertion can make it impossible to retrieve.

Use ConcurrentHashMap for Concurrent Access

Avoid using Hashtable in new applications unless maintaining legacy code.

Common Mistakes

Using Mutable Keys

Changing key fields after insertion breaks map lookups.

Forgetting equals() and hashCode()

Custom key retrieval may fail or produce duplicate logical entries.

Assuming HashMap Preserves Order

It does not guarantee insertion or sorted order.

Using TreeMap Without Comparable or Comparator

Keys must be naturally comparable or a Comparator must be supplied.

Iterating Using keySet() Unnecessarily

When both key and value are needed, prefer entrySet().

Hands-on Exercise

Create a Java program that:

1. Creates a HashMap of employee IDs and names.
2. Demonstrates insertion, retrieval, update, and deletion.
3. Iterates using:
   • entrySet()
   • keySet()
   • values()
4. Creates a LinkedHashMap and verifies insertion order.
5. Creates a TreeMap and verifies sorted keys.
6. Creates a custom EmployeeKey class with proper equals() and hashCode().
7. Demonstrates the effect of duplicate keys.
8. Compares the behavior of HashMap, LinkedHashMap, TreeMap, and Hashtable.

Summary

The Map interface provides an efficient mechanism for storing and retrieving key-value pairs. HashMap offers excellent average-case performance, LinkedHashMap preserves insertion order, TreeMap maintains sorted keys using a Red-Black Tree, and Hashtable provides legacy synchronized access. Understanding hashing, bucket distribution, load factors, collision handling, and proper implementation of equals() and hashCode() is essential for writing high-performance enterprise Java applications.

Key Takeaways

• Map stores key-value pairs.
• Keys are unique; values may be duplicated.
• Map is not part of the Collection interface hierarchy.
• HashMap provides fast average-case lookup using hashing.
• LinkedHashMap preserves insertion order.
• TreeMap maintains sorted keys.
• Hashtable is synchronized but largely replaced by ConcurrentHashMap.
• Proper equals() and hashCode() implementations are essential for custom keys.
• entrySet() is generally the preferred way to iterate through a map.

Professional Interview Questions