Why Hash Map Exists and What Problem It Solves in DSA Java - Why This Pattern

Mental Model

A hash map helps us find things quickly by using a special code to jump right to the spot instead of searching one by one.

Analogy: Imagine a huge library where books are arranged randomly. Without a system, you must check every book to find one. A hash map is like having a magical index that tells you exactly where the book is on the shelf instantly.

Array: [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
Keys:   k1  k2  k3  k4  k5  k6  k7  k8  k9  k10
Values: v1  v2  v3  v4  v5  v6  v7  v8  v9  v10
Hash Map: key k3 -> index 2 -> value v3
Hash Map: key k7 -> index 6 -> value v7

Dry Run Walkthrough

Input: Store and find phone numbers by name: Add (Alice, 123), (Bob, 456), (Carol, 789), then find Bob's number.

Goal: Show how a hash map quickly finds Bob's number without checking all entries.

Step 1: Add Alice with number 123 using hash function to find index

Array: [Alice:123] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: We store Alice's number at the index given by hashing her name for quick access.

Step 2: Add Bob with number 456 using hash function to find index

Array: [Alice:123] [ ] [Bob:456] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Why: Bob's name hashes to a different index, so we store his number there.

Step 3: Add Carol with number 789 using hash function to find index

Array: [Alice:123] [ ] [Bob:456] [ ] [Carol:789] [ ] [ ] [ ] [ ] [ ]

Why: Carol's name hashes to another index, so her number is stored there.

Step 4: Find Bob's number by hashing 'Bob' to get index

Array: [Alice:123] [ ] [Bob:456 ↑] [ ] [Carol:789] [ ] [ ] [ ] [ ] [ ]

Why: Hashing 'Bob' gives the index directly, so we jump straight to Bob's number without searching.

Result:

Array: [Alice:123] [ ] [Bob:456] [ ] [Carol:789] [ ] [ ] [ ] [ ] [ ]
Answer: Bob's number is 456

Annotated Code

DSA Java

import java.util.*;

public class HashMapDemo {
    static class SimpleHashMap {
        private static class Entry {
            String key;
            int value;
            Entry next;
            Entry(String key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private Entry[] buckets;
        private int capacity = 10;

        public SimpleHashMap() {
            buckets = new Entry[capacity];
        }

        private int hash(String key) {
            return Math.abs(key.hashCode()) % capacity;
        }

        public void put(String key, int value) {
            int index = hash(key); // get bucket index
            Entry head = buckets[index];
            Entry curr = head;
            while (curr != null) {
                if (curr.key.equals(key)) {
                    curr.value = value; // update existing key
                    return;
                }
                curr = curr.next; // move to next entry
            }
            Entry newEntry = new Entry(key, value);
            newEntry.next = head; // insert at head
            buckets[index] = newEntry;
        }

        public Integer get(String key) {
            int index = hash(key); // get bucket index
            Entry curr = buckets[index];
            while (curr != null) {
                if (curr.key.equals(key)) {
                    return curr.value; // found key
                }
                curr = curr.next; // move to next entry
            }
            return null; // key not found
        }
    }

    public static void main(String[] args) {
        SimpleHashMap map = new SimpleHashMap();
        map.put("Alice", 123);
        map.put("Bob", 456);
        map.put("Carol", 789);

        Integer bobsNumber = map.get("Bob");
        if (bobsNumber != null) {
            System.out.println("Bob's number is " + bobsNumber);
        } else {
            System.out.println("Bob's number not found");
        }
    }
}

int index = hash(key); // get bucket index

compute index from key using hash function

while (curr != null) { if (curr.key.equals(key)) { curr.value = value; return; } curr = curr.next; }

search bucket for existing key to update value

newEntry.next = head; buckets[index] = newEntry;

insert new entry at head of bucket linked list

while (curr != null) { if (curr.key.equals(key)) { return curr.value; } curr = curr.next; }

search bucket for key to return value

Output

Bob's number is 456

Complexity Analysis

Time: O(1) average because hashing jumps directly to the bucket; worst case O(n) if many keys collide in one bucket

Space: O(n) because we store all key-value pairs in the buckets

vs Alternative: Compared to searching a list which is O(n), hash map lookup is much faster on average due to direct indexing

Edge Cases

Empty map when searching a key

Returns null indicating key not found

DSA Java

return null; // key not found

Adding duplicate key

Updates the existing key's value instead of adding a new entry

DSA Java

if (curr.key.equals(key)) { curr.value = value; return; }

Hash collisions (different keys with same index)

Stores entries in a linked list at the bucket to handle collisions

DSA Java

newEntry.next = head; buckets[index] = newEntry;

When to Use This Pattern

When you need to store and find data by keys quickly, especially when searching a list is too slow, reach for the hash map pattern because it provides near-instant lookup using hashing.

Common Mistakes

Mistake: Not handling collisions, causing data loss when two keys hash to the same index
Fix: Use a linked list or another structure at each bucket to store multiple entries

Mistake: Not updating existing keys, leading to duplicate keys with different values
Fix: Check for existing key in bucket and update its value instead of adding a new entry

Summary

A hash map stores key-value pairs for very fast lookup using a hash function.

Use it when you want to find data quickly by key without searching everything.

The key insight is hashing turns a key into an index to jump directly to the data.

Practice

1. Why do we use a HashMap in Java instead of a simple array when we want to store key-value pairs?

easy

A. Because arrays use more memory than HashMap.

B. Because HashMap allows fast lookup of values by keys.

C. Because HashMap automatically sorts the keys.

D. Because arrays can only store numbers, not keys and values.

Solution

1. Step 1: Understand the limitation of arrays for key-value storage

   Arrays store values by index, not by custom keys, so they can't quickly find a value by a key.

2. Step 2: Recognize the advantage of HashMap

   HashMap stores data as key-value pairs and uses hashing to find values quickly by keys.

3. Final Answer:

   Because HashMap allows fast lookup of values by keys. -> Option B

4. Quick Check:

   Fast key-based lookup = Because HashMap allows fast lookup of values by keys. [OK]

Hint: HashMap = fast key-value lookup, arrays = index-based [OK]

Common Mistakes:

• Thinking arrays can store key-value pairs directly
• Believing HashMap sorts keys automatically
• Confusing memory usage between arrays and HashMaps

2. Which of the following is the correct way to declare a HashMap in Java that maps String keys to Integer values?

easy

A. HashMap map = new HashMap<>();

B. HashMap map = new HashMap();

C. HashMap map = new HashMap<>();

D. HashMap map = new HashMap<String>();

Solution

1. Step 1: Identify correct generic syntax for HashMap declaration

   The correct syntax uses angle brackets with key and value types on both sides or diamond operator on the right side.

2. Step 2: Check each option for syntax correctness and type order

   HashMap map = new HashMap<>(); correctly declares a HashMap with String keys and Integer values using diamond operator. Others have wrong order or missing types.

3. Final Answer:

   HashMap map = new HashMap<>(); -> Option A

4. Quick Check:

   Correct generic syntax = HashMap map = new HashMap<>(); [OK]

Hint: Use diamond operator <> with correct key-value types [OK]

Common Mistakes:

• Swapping key and value types
• Omitting generic types on right side
• Using raw types without generics

3. What will be the output of the following Java code?

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

medium

A. 10

B. null

C. 20

D. 30

Solution

1. Step 1: Understand how put works in HashMap with duplicate keys

   When a key already exists, put replaces the old value with the new one.

2. Step 2: Trace the code for key "apple"

   First, "apple" is set to 10, then replaced by 30. So map.get("apple") returns 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   Last value for key "apple" = 30 [OK]

Hint: Last put value for a key overwrites previous [OK]

Common Mistakes:

• Assuming first value stays for duplicate keys
• Expecting null for existing keys
• Confusing values of different keys

4. The following code tries to check if a key exists in a HashMap and print its value. What is wrong?

HashMap map = new HashMap<>();
map.put("x", 5);
if (map.containsKey("y")) {
  System.out.println(map.get("y"));
} else {
  System.out.println("Key not found");
}

medium

A. The code throws NullPointerException when key is missing.

B. Using containsKey is wrong; should use get only.

C. No error; code works correctly.

D. The code should check for null instead of using containsKey.

Solution

1. Step 1: Understand containsKey usage

   containsKey safely checks if a key exists without throwing errors.

2. Step 2: Check code behavior for missing key "y"

   Since "y" is missing, containsKey returns false and prints "Key not found" without error.

3. Final Answer:

   No error; code works correctly. -> Option C

4. Quick Check:

   Using containsKey prevents errors = No error; code works correctly. [OK]

Hint: Use containsKey before get to avoid null issues [OK]

Common Mistakes:

• Expecting NullPointerException on missing key
• Using get without checking key existence
• Thinking containsKey is unnecessary

5. You want to count how many times each word appears in a list of words using a HashMap. Which approach correctly solves this problem?

hard

A. Use a HashMap<String, Integer>, for each word check if it exists; if yes, increment count; else, add with count 1.

B. Use a HashMap<Integer, String> and store counts as keys and words as values.

C. Use an array to store counts and loop through words without a map.

D. Use a HashMap<String, String> and store words as both keys and values.

Solution

1. Step 1: Identify the correct key-value types for counting words

   Keys should be words (String), values should be counts (Integer).

2. Step 2: Understand the counting logic using HashMap

   For each word, check if it exists in map; if yes, increment count; else add with count 1.

3. Final Answer:

   Use a HashMap, increment counts per word. -> Option A

4. Quick Check:

   Word count needs String keys and Integer values [OK]

Hint: Map words to counts; increment existing or add new [OK]

Common Mistakes:

• Swapping key and value types
• Using arrays without keys for counting
• Storing words as values instead of counts