Topic 30 of 79

HashMap

Q: What is the difference between `HashMap`, `LinkedHashMap`, and `TreeMap`?

`HashMap` is unordered — O(1) get/put but no iteration order guarantee. `LinkedHashMap` maintains insertion order by linking buckets — O(1) operations but slightly more memory. `TreeMap` stores keys in sorted (natural or custom Comparator) order — O(log N) for all operations because it is backed by a Red-Black tree.

Overview

A HashMap is a foundational Key-Value data structure that stores pairs of data. Instead of locating data by a numeric index (like an array), you retrieve data using a meaningful key. This makes data lookup both semantically rich and blazing fast.

Internally, HashMap is powered by an array of 'buckets' and a Hash Function. When you call map.put("name", "Alice"), the JVM runs the hashCode() method on the key ("name"), converts it into an array index, and stores the value at that location. When you later call map.get("name"), the exact same hash is computed, the same bucket is found, and the value is retrieved in amortized O(1) time.

A Hash Collision occurs when two different keys produce the same hash code (same bucket index). Java resolves this using Chaining — each bucket holds a linked list (or a Red-Black tree for 8+ collisions in Java 8+) of all key-value pairs that collided there. HashMaps are fundamentally unordered — they make no guarantee about the order of iteration.

Syntax

Core HashMap Operations

java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        
        // 1. Putting Key-Value Pairs
        scores.put("Alice", 95);
        scores.put("Bob", 88);
        scores.put("Charlie", 72);
        
        // 2. Retrieving Values
        System.out.println(scores.get("Alice")); // 95
        System.out.println(scores.get("NoKey")); // null (key doesn't exist)
        
        // 3. Safe Retrieval with Default
        int aliceScore = scores.getOrDefault("NoKey", 0); // Returns 0, not null
        
        // 4. Checking Existence
        System.out.println(scores.containsKey("Bob")); // true
        
        // 5. Iterating (Order NOT guaranteed!)
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + " scored: " + entry.getValue());
        }
        
        // 6. Powerful Java 8+ method
        // If key exists: adds 10. If key absent: inserts 10.
        scores.merge("Alice", 10, Integer::sum); // Alice → 105
    }
}

Common Pitfalls

Depending on iteration order. HashMap makes absolutely NO guarantee about the order you will get your key-value pairs when you iterate. If order matters, use LinkedHashMap (insertion-order) or TreeMap (natural sort order of keys).
Using mutable objects as Keys. The HashMap uses the key's hashCode() to find the bucket. If you use an object as a key and then mutate it after inserting, its hashCode() changes, and the map can no longer find it — it's lost permanently! Always use immutable objects (like String, Integer) as HashMap keys.
Calling get() without null-checking. If the key doesn't exist, get() returns null. If you immediately try to unbox the result (e.g., int score = scores.get("Unknown");), you get a NullPointerException. Always use getOrDefault() or check containsKey() first.

Interview Questions

What is the time complexity of put() and get() in a HashMap?

Both are amortized O(1). In the absolute worst-case scenario (every single key produces the same hash code, causing massive collisions), it degrades to O(N). In practice, with a well-distributed hash function and the default load factor, it is effectively constant time.

What is the default initial capacity and load factor of a HashMap, and what does the load factor mean?

Default initial capacity is 16 buckets, and the default load factor is 0.75. When the number of entries exceeds 75% of the current capacity (12 entries for a capacity-16 map), the HashMap automatically doubles its internal array size and rehashes all existing entries — an expensive O(N) operation.

What is the difference between HashMap, LinkedHashMap, and TreeMap?

HashMap is unordered — O(1) get/put but no iteration order guarantee. LinkedHashMap maintains insertion order by linking buckets — O(1) operations but slightly more memory. TreeMap stores keys in sorted (natural or custom Comparator) order — O(log N) for all operations because it is backed by a Red-Black tree.

Real-World Example

Rate limiting middleware in an API server uses a HashMap to track how many requests each user has made in the last minute. The user's ID is the key, and the request count is the value, enabling O(1) lookup on every incoming request.

example

java

Map<String, Integer> requestCounts = new HashMap<>();

public boolean isRateLimited(String userId) {
    int count = requestCounts.getOrDefault(userId, 0);
    if (count >= 100) { // More than 100 requests per minute
        return true; // Block the request
    }
    requestCounts.put(userId, count + 1);
    return false;
}

Check Your Knowledge

Test your understanding of HashMap with these quick questions.

What does `HashMap.get()` return if the key does not exist?

Which collection should you use if you need HashMap behavior but with entries always iterated in insertion order?

What happens internally when you call `put()` and the HashMap's load factor is exceeded?

Take Java Quiz

Overview

Syntax

Core HashMap Operations

java

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        
        // 1. Putting Key-Value Pairs
        scores.put("Alice", 95);
        scores.put("Bob", 88);
        scores.put("Charlie", 72);
        
        // 2. Retrieving Values
        System.out.println(scores.get("Alice")); // 95
        System.out.println(scores.get("NoKey")); // null (key doesn't exist)
        
        // 3. Safe Retrieval with Default
        int aliceScore = scores.getOrDefault("NoKey", 0); // Returns 0, not null
        
        // 4. Checking Existence
        System.out.println(scores.containsKey("Bob")); // true
        
        // 5. Iterating (Order NOT guaranteed!)
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.println(entry.getKey() + " scored: " + entry.getValue());
        }
        
        // 6. Powerful Java 8+ method
        // If key exists: adds 10. If key absent: inserts 10.
        scores.merge("Alice", 10, Integer::sum); // Alice → 105
    }
}

Common Pitfalls

Depending on iteration order. HashMap makes absolutely NO guarantee about the order you will get your key-value pairs when you iterate. If order matters, use LinkedHashMap (insertion-order) or TreeMap (natural sort order of keys).
Using mutable objects as Keys. The HashMap uses the key's hashCode() to find the bucket. If you use an object as a key and then mutate it after inserting, its hashCode() changes, and the map can no longer find it — it's lost permanently! Always use immutable objects (like String, Integer) as HashMap keys.
Calling get() without null-checking. If the key doesn't exist, get() returns null. If you immediately try to unbox the result (e.g., int score = scores.get("Unknown");), you get a NullPointerException. Always use getOrDefault() or check containsKey() first.

Interview Questions

What is the time complexity of put() and get() in a HashMap?

What is the default initial capacity and load factor of a HashMap, and what does the load factor mean?

What is the difference between HashMap, LinkedHashMap, and TreeMap?

Real-World Example

example

java

Map<String, Integer> requestCounts = new HashMap<>();

public boolean isRateLimited(String userId) {
    int count = requestCounts.getOrDefault(userId, 0);
    if (count >= 100) { // More than 100 requests per minute
        return true; // Block the request
    }
    requestCounts.put(userId, count + 1);
    return false;
}

Check Your Knowledge

Test your understanding of HashMap with these quick questions.