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

Concept Flow - Why Hash Map Exists and What Problem It Solves

Start: Need to store key-value pairs

↓

Use simple list or array?

No↓

Search slow: O(n) time

↓

Need faster search

↓

Use Hash Map: Compute hash(key)

↓

Map hash to index in array

↓

Store value at index

↓

Retrieve value fast by key

↓

Problem solved: Fast lookup, insert, delete

Shows the flow from needing to store key-value pairs to using a hash map for fast lookup by computing a hash and mapping it to an array index.

Execution Sample

DSA Java

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 3);
int val = map.get("apple");
System.out.println(val);

Stores fruit counts in a hash map and retrieves the count for "apple" quickly.

Execution Table

Step	Operation	Hash Computed	Index in Array	Array State (Index: Key=Value)	Output
1	Create empty HashMap	-	-	[]	-
2	Put("apple", 5)	hash("apple")=15	15 % array_size=3	[3: apple=5]	-
3	Put("banana", 3)	hash("banana")=22	22 % array_size=0	[0: banana=3, 3: apple=5]	-
4	Get("apple")	hash("apple")=15	15 % array_size=3	[0: banana=3, 3: apple=5]	5
5	Print value	-	-	-	5
6	End	-	-	[0: banana=3, 3: apple=5]	-

💡 All operations done; hash map stores and retrieves values in O(1) average time.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
map	empty	[3: apple=5]	[0: banana=3, 3: apple=5]	[0: banana=3, 3: apple=5]	[0: banana=3, 3: apple=5]
val	undefined	undefined	undefined	5	5

Key Moments - 3 Insights

Why can't we just use a list or array to store key-value pairs?

Using a list means searching for a key takes time proportional to the list size (O(n)), as shown in step 2 and 3 where hash map uses hashing to find index quickly.

How does hashing help in fast lookup?

Hashing converts a key into an index in the array, so we can directly access the value without searching, as seen in steps 2, 3, and 4 where hash("apple") maps to index 3.

What happens if two keys hash to the same index?

This is called a collision; hash maps handle it internally (not shown here) to store multiple keys at the same index without losing data.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after step 3?

A [0: banana=3, 3: apple=5]

B [3: apple=5]

C []

D [1: apple=5, 2: banana=3]

💡 Hint

Check the 'Array State' column in row for step 3.

At which step is the value 5 retrieved from the map?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Output' column to see when 5 appears.

If the hash function returned the same index for "apple" and "banana", what would change in the execution table?

A Both keys stored at same index, array state shows collision handling

B Keys stored at different indexes as before

C Map would be empty

D Values would overwrite each other

💡 Hint

Collisions mean multiple keys share one index; see key moment 3.

Concept Snapshot

Hash Map stores key-value pairs.
Uses a hash function to convert keys to array indexes.
Allows fast insert, search, and delete (average O(1) time).
Solves slow search problem of lists.
Handles collisions internally to avoid data loss.

Full Transcript

We start with the need to store key-value pairs. Using a simple list means searching for a key takes time proportional to the list size, which is slow. To solve this, hash maps use a hash function to convert keys into array indexes. This lets us store and retrieve values quickly by directly accessing the array position. For example, putting "apple" with value 5 computes a hash and stores it at index 3. Getting "apple" uses the same hash to find the value fast. Collisions can happen if two keys map to the same index, but hash maps handle this internally. This makes hash maps very efficient for fast lookup, insert, and delete operations.

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