Chapter 19 of 32

HashMap

On this page

Suppose John is a student with ID 101, Jason has ID 102, and Alex has ID 103.

We could store this information like this:

101 → John
102 → Jason
103 → Alex

Here, each student ID is a key, and each student's name is a value.

A HashMap is a data structure that stores information in key-value pairs and uses hashing to provide fast access to values.

In Java, HashMap is one of the most commonly used data structures for solving DSA problems.

What is a HashMap?

A HashMap stores data in this form:

Key → Value

For example:

101 → John
102 → Jason
103 → Alex

Each key should be unique.

However, multiple keys can have the same value:

101 → John
102 → John
103 → Alex

That's perfectly valid because the keys are different.

Creating a HashMap

We can create a HashMap using:

import java.util.HashMap;

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

Here:

Integer → Type of key
String  → Type of value

So the map can store:

Integer → String

For example:

students.put(101, "John");
students.put(102, "Jason");
students.put(103, "Alex");

Now the map contains:

101 → John
102 → Jason
103 → Alex

Adding Elements with `put()`

The put() method adds a key-value pair.

students.put(101, "John");
students.put(102, "Jason");
students.put(103, "Alex");

The general syntax is:

map.put(key, value);

For example:

students.put(104, "Michael");

Now:

101 → John
102 → Jason
103 → Alex
104 → Michael

Retrieving a Value

We can use get() to retrieve a value using its key.

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

Output:

Jason

The HashMap uses the key 102 to find the corresponding value.

102
 ↓
Hashing
 ↓
Jason

This is much faster than manually searching through a large collection in many typical cases.

What Happens If the Key Doesn't Exist?

Suppose we ask for:

students.get(999);

If the key doesn't exist, get() returns:

null

For example:

System.out.println(students.get(999));

Output:

null

Checking Whether a Key Exists

We can use:

containsKey()

For example:

if (students.containsKey(102)) {
    System.out.println("Student found");
}

Output:

Student found

This is very useful in DSA problems where we need to quickly determine whether something has already been seen.

Checking Whether a Value Exists

We can also check whether a particular value exists using:

containsValue()

For example:

System.out.println(students.containsValue("John"));

Output:

true

Updating a Value

If we use put() with a key that already exists, the old value is replaced.

Suppose we have:

101 → John

Now:

students.put(101, "Michael");

The map becomes:

101 → Michael

The key 101 still exists, but its value has changed.

This is an important difference from collections such as ArrayList, where adding another element simply creates another element.

Removing an Element

We can remove a key-value pair using remove().

students.remove(102);

If the map contained:

101 → John
102 → Jason
103 → Alex

it becomes:

101 → John
103 → Alex

We can also retrieve the removed value:

String name = students.remove(102);

System.out.println(name);

Output:

Jason

Finding the Size

We can use:

students.size()

For example:

System.out.println(students.size());

If there are three key-value pairs, the output is:

Checking Whether the HashMap Is Empty

Use:

students.isEmpty()

For example:

if (students.isEmpty()) {
    System.out.println("Map is empty");
}

Iterating Through a HashMap

We often need to process every key-value pair.

One of the best ways is using entrySet():

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

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

Output might look like:

101 → John
102 → Jason
103 → Alex

The order is not something you should rely on with a normal HashMap.

Getting Only the Keys

We can use:

students.keySet()

For example:

for (Integer id : students.keySet()) {
    System.out.println(id);
}

This processes only the keys.

Getting Only the Values

We can use:

students.values()

For example:

for (String name : students.values()) {
    System.out.println(name);
}

This processes only the values.

HashMap and Hashing

You might wonder why it's called a HashMap.

Internally, Java uses hashing to determine where entries should be stored.

The general idea is:

Key
 ↓
hashCode()
 ↓
Hash calculation
 ↓
Bucket
 ↓
Key-value entry

For example:

101
 ↓
Hash Function
 ↓
Bucket
 ↓
101 → John

When you later call:

students.get(101);

the HashMap uses the key to locate the appropriate bucket and find the value.

Hash Collisions

Different keys can sometimes produce the same hash location.

This is called a collision.

For example:

Key 101 → Bucket 3
Key 111 → Bucket 3

Both keys want the same bucket.

Java's HashMap handles these collisions internally.

You don't normally have to manually manage them when using the standard HashMap class.

Understanding collisions is still important when studying hashing because they explain why hash tables aren't magically guaranteed to perform every operation in constant time.

Time Complexity

For a well-distributed HashMap, common operations are generally:

Operation	Average	Worst Case
`put()`	`O(1)`	`O(n)`*
`get()`	`O(1)`	`O(n)`*
`remove()`	`O(1)`	`O(n)`*
`containsKey()`	`O(1)`	`O(n)`*

*The exact worst-case behavior depends on the implementation and collision structure. Modern Java uses tree-based structures in sufficiently large collision buckets, which can improve some collision-heavy cases.

The important DSA concept is that HashMap operations are usually O(1) on average.

HashMap for Frequency Counting

One of the most important uses of a HashMap in DSA is frequency counting.

Suppose we have:

10, 20, 10, 30, 20, 10

We want to count how many times each number appears.

We can use:

import java.util.HashMap;

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

        int[] numbers = {
            10, 20, 10, 30, 20, 10
        };

        HashMap<Integer, Integer> frequency = new HashMap<>();

        for (int number : numbers) {

            frequency.put(
                number,
                frequency.getOrDefault(number, 0) + 1
            );
        }

        System.out.println(frequency);
    }
}

The result represents:

10 → 3
20 → 2
30 → 1

This pattern is extremely common in DSA.

Understanding `getOrDefault()`

This line:

frequency.getOrDefault(number, 0)

means:

"Give me the current count for this number. If the number doesn't exist, give me 0."

Suppose we're processing 10 for the first time.

frequency.getOrDefault(10, 0)

returns:

Then we add 1:

0 + 1 = 1

The map becomes:

10 → 1

When we encounter 10 again:

1 + 1 = 2

And so on.

Finding Duplicate Values

HashMap can also help identify duplicates.

For example:

int[] numbers = {10, 20, 30, 20, 40, 10};

HashMap<Integer, Integer> frequency = new HashMap<>();

for (int number : numbers) {

    frequency.put(
        number,
        frequency.getOrDefault(number, 0) + 1
    );
}

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

    if (entry.getValue() > 1) {
        System.out.println(
            "Duplicate: " + entry.getKey()
        );
    }
}

Output:

Duplicate: 10
Duplicate: 20

HashMap for Two Sum

HashMap is especially useful in classic DSA problems such as Two Sum.

Suppose we have:

[2, 7, 11, 15]

and we need to find two numbers whose sum is 9.

We can use a HashMap to remember numbers we've already seen.

import java.util.HashMap;

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

        int[] numbers = {2, 7, 11, 15};
        int target = 9;

        HashMap<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < numbers.length; i++) {

            int needed = target - numbers[i];

            if (seen.containsKey(needed)) {

                System.out.println(
                    "Pair: " +
                    needed + ", " +
                    numbers[i]
                );

                break;
            }

            seen.put(numbers[i], i);
        }
    }
}

Output:

Pair: 2, 7

The HashMap allows us to quickly check whether the number we need has already appeared.

This is a very important DSA pattern:

Calculate what you need
        ↓
Check HashMap
        ↓
Found?
  ↙       ↘
Yes       No
 ↓         ↓
Answer   Store current value

HashMap with Strings

HashMap isn't limited to integers.

We can use strings as keys:

HashMap<String, Integer> ages = new HashMap<>();

ages.put("John", 25);
ages.put("Jason", 28);
ages.put("Alex", 24);

Now:

System.out.println(ages.get("Jason"));

Output:

We can use almost any suitable object type as a key, provided it follows the requirements for hashing and equality.

Important: Keys Are Unique

A HashMap cannot have duplicate keys.

For example:

students.put(101, "John");
students.put(101, "Jason");

After the second put():

101 → Jason

The value associated with key 101 was replaced.

But different keys can have the same value:

students.put(101, "John");
students.put(102, "John");

This is valid:

101 → John
102 → John

HashMap Does Not Guarantee Order

A normal HashMap does not guarantee that elements will be returned in the order they were inserted.

For example, if we insert:

students.put(101, "John");
students.put(102, "Jason");
students.put(103, "Alex");

you should not write your program assuming iteration will always produce:

101
102
103

If you specifically need insertion order, Java provides LinkedHashMap.

If you need keys sorted according to their natural ordering, TreeMap is another option.

HashMap vs HashSet

Both use hashing, but they store different things.

A HashMap stores:

Key → Value

Example:

101 → John
102 → Jason

A HashSet stores only unique values:

10
20
30

So:

HashMap → Key-value pairs
HashSet → Unique values

When Should You Use HashMap?

HashMap is especially useful when you need to:

Quickly find a value using a key
Count frequencies
Detect duplicates
Store relationships between two pieces of data
Remember previously seen elements
Solve lookup-based DSA problems
Build dictionaries or lookup tables

Whenever you find yourself thinking:

"I need to quickly check whether I have already seen this."

or:

"I need to associate this value with another value."

a HashMap is often worth considering.

A Complete Example

Let's create a simple student lookup system:

import java.util.HashMap;

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

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

        students.put(101, "John");
        students.put(102, "Jason");
        students.put(103, "Alex");
        students.put(104, "Michael");

        int studentId = 103;

        if (students.containsKey(studentId)) {

            String name = students.get(studentId);

            System.out.println(
                "Student: " + name
            );

        } else {
            System.out.println("Student not found");
        }
    }
}

Output:

Student: Alex

The program uses the student ID as the key and the student's name as the value.

The Main Idea

A HashMap stores information as key-value pairs:

Key → Value

For example:

101 → John
102 → Jason
103 → Alex

The key is passed through hashing to efficiently locate the corresponding entry.

The most important operations are:

put()          → Add or update
get()          → Retrieve
remove()       → Delete
containsKey()  → Check key
size()         → Number of entries

And in DSA, one of the most important patterns is:

HashMap
   ↓
Store information
   ↓
Quick lookup
   ↓
Solve the problem efficiently

HashMap is a key-value data structure that uses hashing to provide fast average-time insertion, lookup, and deletion.

Once you're comfortable with put(), get(), containsKey(), and frequency counting, you'll find HashMap appearing again and again in DSA problems.

PreviousHashing NextHashSet

HashMap

What is a HashMap?

Creating a HashMap

Adding Elements with put()

Retrieving a Value

What Happens If the Key Doesn't Exist?

Checking Whether a Key Exists

Checking Whether a Value Exists

Updating a Value

Removing an Element

Finding the Size

Checking Whether the HashMap Is Empty

Iterating Through a HashMap

Getting Only the Keys

Getting Only the Values

HashMap and Hashing

Hash Collisions

Time Complexity

HashMap for Frequency Counting

Understanding getOrDefault()

Finding Duplicate Values

HashMap for Two Sum

HashMap with Strings

Important: Keys Are Unique

HashMap Does Not Guarantee Order

HashMap vs HashSet

When Should You Use HashMap?

A Complete Example

The Main Idea

Adding Elements with `put()`

Understanding `getOrDefault()`