How HashMap works Internally?

🔧 1. Storage Structure

HashMap uses an array of buckets (Node[] table) where each bucket is a linked list or tree of Map.Entry objects.

🔢 2. How a key-value pair is stored

When you put a value into a HashMap:

map.put("John", 25);

Internally, it performs:

a. Hashing the key

int hash = hash("John");

The key’s hash code is calculated (using hashCode()), and some bit manipulation is done to spread bits more evenly.

b. Index calculation

index = hash % capacity;

This index determines which bucket to use in the internal array.

c. Store the entry

  • If the bucket is empty → store the entry.
  • If not → check for key collision:
    • If key exists → update value.
    • If key is different → use chaining (linked list or tree) to store multiple entries.

⚠️ 3. Collision Handling

  • Chaining is used — multiple entries in the same bucket using a linked list.
  • From Java 8 onward, if the number of entries in a bucket > 8 and total buckets > 64, it becomes a Balanced Tree (Red-Black Tree) for faster lookups.

🔄 4. get(key) Process

map.get("John");
  • Compute hash and bucket index.
  • Go to the correct bucket.
  • Traverse the linked list or tree to find the key.
  • Return the value if key matches.

📏 5. Resizing

When size exceeds threshold = capacity × load factor (default 0.75), the array is doubled, and all entries are rehashed to new buckets.

🧠 Summary Diagram (Text)

HashMap
  |
  --> [Bucket Array]
         |
         +-- index 0 --> null
         +-- index 1 --> Node("Alice", 30) --> Node("Eve", 40)
         +-- index 2 --> TreeNode("John", 25)

🔍 Performance

  • put() and get() → O(1) average case.
  • In worst case (many collisions) → O(n), but tree optimization improves it to O(log n).

HashMap With a key having multiple values

✅ Example using HashMap<String, List<String>>:

import java.util.*;

public class MultiValueMapExample {
    public static void main(String[] args) {
        Map<String, List<String>> map = new HashMap<>();

        // Add values to key "fruit"
        map.computeIfAbsent("fruit", k -> new ArrayList<>()).add("apple");
        map.get("fruit").add("banana");

        // Add values to key "vegetable"
        map.computeIfAbsent("vegetable", k -> new ArrayList<>()).add("carrot");

        // Print the map
        System.out.println(map);
    }
}

🧾 Output:

{vegetable=[carrot], fruit=[apple, banana]}

🔍 Explanation:

  • computeIfAbsent() checks if the key exists; if not, it initializes an empty list.
  • Then you can add multiple values to the same key.

🛠️ Optional: Use Set Instead of List if You Want Unique Values

Map<String, Set<String>> map = new HashMap<>();
map.computeIfAbsent("fruit", k -> new HashSet<>()).add("apple");

Fetch a value from a HashMap Even if the key doesn't exist

✅ Example:

Map<String, String> map = new HashMap<>();
map.put("name", "Aftab");

String value = map.get("age");  // "age" key doesn't exist

System.out.println(value);  // Output: null

🚨 Things to Remember:

  • map.get(key) returns null if the key is not found.
  • If your map might contain null values, you should use containsKey() to be safe.

✅ Safer Check:

if (map.containsKey("age")) {
    System.out.println("Value: " + map.get("age"));
} else {
    System.out.println("Key not found");
}

✅ Or Use Default Value with getOrDefault():

String value = map.getOrDefault("age", "Unknown");
System.out.println(value);  // Output: Unknown
Back to blog

Leave a comment

Please note, comments need to be approved before they are published.