HashMap in Java – A Beginner to Advance Guide

In Java, HashMap is one of the most popular data structures provided in the Collection Framework. It is used to store data in the form of key-value pairs, just like a dictionary.

Think of a HashMap as a real-world contact list:

• The name is the key.
• The phone number is the value.
• You use the name (key) to find the number (value).

Key Features of HashMap

Feature	Description
Implements	Map<K, V> interface
Storage Format	Key-Value pairs
Null Keys/Values	Allows one null key and multiple null values
Order	No guaranteed order
Thread-Safety	Not synchronized (not thread-safe by default)
Performance	Constant time for get() and put() (average case)

Syntax of HashMap

import java.util.HashMap;

HashMap<KeyType, ValueType> mapName = new HashMap<>();

Example:

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

Internal Working of HashMap(In Short)

Behind the scenes, HashMap uses an array of buckets, and each bucket holds nodes (also called entries). Each node contains:

• Key
• Value
• Hash of the key
• A pointer to the next node (in case of collision)

Steps:

1. When we put a key-value pair using put(), HashMap calculates the hashcode of the key.
2. This hashcode decides the index of the bucket.
3. If the bucket is empty, the entry is stored there.
4. If not (collision occurs), it uses a linked list or a balanced tree (in Java 8+) to store multiple entries at the same index.

Internal Structure of HashMap(Explained)

Internally, HashMap uses:

1. Array of Buckets

• HashMap maintains an array called table[].
• Each element of this array is called a bucket.
• A bucket is where the actual Node<K, V> objects (also called entries) are stored.

2. Each Node Contains:

• key – The actual key object.
• value – The associated value.
• hash – Hashcode of the key.
• next – Reference to the next node (used in chaining during collision).

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Step-by-Step: put(key, value) Operation

Step 1: Calculate Hash

When you call:

map.put("John", 25);

Java first calculates the hashcode of the key "John" using its hashCode() method.

But instead of using the raw hashCode(), HashMap applies a hash function to spread out the keys more uniformly:

hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

This helps in reducing collisions.

Step 2: Calculate Index

Next, it computes the index in the array using:

index = (n - 1) & hash;

Here, n is the size of the array (initially 16), and & is a bitwise AND to ensure the index is within array bounds.

Step 3: Check for Collision

• If the bucket at that index is empty, it inserts the new node directly.
• If not empty (collision), HashMap checks whether:
  • The key is equal (using .equals()). If yes, it updates the value.
  • If not equal, it checks the next node (i.e., linked list chaining).

Collision Handling

Before Java 8:

Collisions were handled using Linked Lists. New entries were added at the head of the list.

From Java 8 onwards:

If a single bucket contains more than 8 nodes and the array size is at least 64, it transforms the bucket into a Red-Black Tree for faster lookups (O(log n) time instead of O(n)).

Step-by-Step: get(key) Operation

Step 1: Calculate the hash and index

When you call map.get("John"), HashMap needs to find out which bucket to look into.

a. Generate the hash

HashMap doesn’t use the raw hashCode directly. Instead, it improves hash distribution using:

int h = key.hashCode();
int hash = (h) ^ (h >>> 16);  // spreads higher bits to lower for better uniformity

This helps prevent poor performance from bad hash functions.

b. Calculate array index

HashMap internally stores data in an array (called table[]). The index is calculated like this:

int index = (n - 1) & hash;  // n is table.length

This ensures the index is within bounds of the array and helps distribute keys uniformly.

Example:
Let’s say:

• "John".hashCode() = 123456
• After hash improvement: hash = 123400
• Table length = 16

Then:

index = (16 - 1) & 123400 = 15 & 123400 = some value between 0 and 15

Step 2: Go to the bucket at that index

Each bucket is either:

• null (empty),
• Or a reference to the first Node (i.e., a key-value pair or the head of a linked list/tree).

Internal Node structure:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // for collision chaining
}

So, you go directly to table[index].

Step 3: Traverse the bucket (Linked List or Tree)

Case 1: Linked List (before Java 8 or less than 8 elements)

If multiple entries (nodes) are in the same bucket (due to collisions), they’re stored as a linked list. So you do:

Node<K, V> current = table[index];

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

✅ If a match is found → return value
❌ If not → keep going until next == null → return null

Case 2: TreeNode (Red-Black Tree, from Java 8)

If the bucket is converted to a tree (more than 8 entries), then traversal becomes:

return treeNode.getTreeNode(hash, key);

This search is faster (O(log n)), as it follows binary tree rules.

Final Step: Return the value or null

• If a node is found where (hash matches) and (key.equals(searchKey)) → return value
• If no node matches → return null

Rehashing (Resizing)

When the number of entries exceeds the threshold (capacity × load factor, usually 0.75), the HashMap doubles its size and rehashes all the keys.

• Each key’s hash is recalculated.
• Re-inserted into the new array.

This ensures better distribution and avoids performance degradation.

Summary

Step	Action
1	Calculate hash using key’s hashCode()
2	Compute index in the array
3	If bucket is empty → insert node
4	If bucket is occupied → check key equality (collision resolution)
5	If key exists → update value
6	If not → append to list or convert to tree if needed
7	If size > threshold → resize and rehash

Example

HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1); // goes to index i
map.put("B", 2); // different index or same (collision)
map.put("A", 3); // same key → update value to 3

Basic HashMap Methods with Examples

Let’s go through the most used methods.

1. put(key, value) – Add or Update

Purpose:

• Adds a new key-value pair to the HashMap.
• If the key already exists, it updates the value with the new one.

studentMarks.put("Alice", 85);
studentMarks.put("Bob", 90);
studentMarks.put("Alice", 95); // Updates Alice’s score

Notes:

• Keys are unique in a HashMap.
• Values can be duplicated, but keys cannot.

2. get(key) – Retrieve Value

Purpose:

• Returns the value associated with the given key.
• If the key is not found, returns null.

System.out.println(studentMarks.get("Alice")); // 95
System.out.println(studentMarks.get("Charlie")); // null (key not found)

3. containsKey(key) & containsValue(value)

containsKey(key):

Checks if a key is present in the map.

System.out.println(studentMarks.containsKey("Bob")); // true

containsValue(value):

Checks if a value exists in the map.

System.out.println(studentMarks.containsValue(90));  // true

4. remove(key)

Purpose:

• Removes the key-value pair for the specified key.
• If the key doesn’t exist, does nothing.

studentMarks.remove("Bob");

5. size()

Purpose:

Returns the total number of key-value pairs in the map.

System.out.println(studentMarks.size()); // Shows number of key-value pairs

6. isEmpty()

Purpose:

Returns true if the map contains no entries, else returns false.

System.out.println(studentMarks.isEmpty()); // true/false

7. clear()

Purpose:

Deletes all key-value pairs in the map. The map becomes empty.

studentMarks.clear(); // Removes all entries

Iterating through HashMap

Iteration means going through each key-value pair in the map to read, process, or print the data.

1. Using entrySet()

How It Works:

• entrySet() returns a Set of Map.Entry<K, V> objects.
• Each Map.Entry represents one key-value pair.
• You can access the key using entry.getKey() and the value using entry.getValue().

Best Use:

When you need both the key and value.

for (Map.Entry<String, Integer> entry : studentMarks.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Output

Alice: 85
Bob: 90
Charlie: 95

2. Using keySet()

for (String name : studentMarks.keySet()) {
    System.out.println("Name: " + name);
}

How It Works:

• keySet() returns a Set containing all the keys in the map.
• You can use each key to retrieve its value if needed:

for (String name : studentMarks.keySet()) {
    System.out.println(name + ": " + studentMarks.get(name));  // also gives value
}

Best Use:

When you’re only interested in keys, or want to process values by fetching map.get(key).

Output:

Name: Alice
Name: Bob
Name: Charlie

3. Using values()

for (Integer marks : studentMarks.values()) {
    System.out.println("Marks: " + marks);
}

How It Works:

• values() returns a Collection of all the values in the map.
• You don’t get access to the keys directly.

Best Use:

When you only need to process or display the values, not the keys.

Output:

Marks: 85
Marks: 90
Marks: 95

Important Points Of HashMap

1. Duplicate Keys Not Allowed

Only one null key and no duplicate keys are allowed. If you try to put the same key again, the value will be overwritten.

2. Duplicate Values Are Allowed

You can have multiple entries with the same value but different keys.

3. Default Capacity and Load Factor

HashMap<K,V> map = new HashMap<>(initialCapacity, loadFactor);

• Initial Capacity: Default is 16.
• Load Factor: Default is 0.75.
• When size exceeds capacity × load factor, it resizes (doubles) the bucket array.

HashMap vs Other Map Types

Feature	HashMap	LinkedHashMap	TreeMap
Order	No Order	Insertion Order	Sorted by Key
Null Keys	One allowed	One allowed	Not allowed
Performance	Fastest	Slightly slower	Slower (due to sorting)

HashMap is Not Thread-Safe

If you use HashMap in a multi-threaded environment, it may lead to data inconsistency. To make it thread-safe:

• Use Collections.synchronizedMap(map)
• Or use ConcurrentHashMap

Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

When to Use HashMap?

Use HashMap when:

• You need fast access, insert, or delete operations.
• You want to store unique keys and their corresponding values.
• You don’t care about order of elements.

Common Interview Questions on HashMap

1. How does HashMap handle collisions?
2. Can a HashMap have duplicate values?
3. What is the default size and load factor?
4. How is HashMap different from Hashtable?
5. How does HashMap resize itself?
6. Is HashMap synchronized?

Summary

Concept	Explanation
Type	Map Implementation
Stores	Key-Value pairs
Nulls	One null key, multiple null values
Order	No guarantee
Thread-safe	No
Best for	Fast lookup, unique key storage

Final Words

HashMap is a powerful and versatile part of Java’s Collection Framework. Understanding how it works internally and how to use it efficiently will make you a better Java developer.

If you’re learning Java, make sure to practice HashMap programs with different data types, custom objects as keys, and explore its performance in real-world projects.