HashMap

#Introduction

HashMap is one of the most important Java interview topics — the implementation you should understand internally, not just at API level. The central idea:

HashMap converts a key into a hash, uses that hash to locate a bucket, and then uses equality to identify the exact key.

We'll build the internals without repeating the basic Map concepts from the Map Interface chapter.

#HashMap at a Glance

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

map.put(101, "Java");
map.put(102, "Spring");

The O(1) figure assumes good hash distribution.

#What Does HashMap Actually Store?

Internally, HashMap maintains an array called the table:

Node<K,V>[] table;

Each occupied bucket contains a chain/tree of nodes. A simplified Node looks like:

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

So each entry contains hash, key, value, next. The next reference allows multiple entries to exist in the same bucket.

HashMap Internal Structure

map.put("A", 100);
map.put("B", 200);
map.put("C", 300);

If two keys land in the same bucket, they are chained: bucket 2 → [A,100] → [B,200]. That's a hash collision.

#The put() Journey

When you execute map.put(key, value); think:

#Step 1 — Calculate the Hash

For a key like "Java", HashMap obtains key.hashCode(). But modern HashMap doesn't simply use that value directly — it performs additional bit mixing.

Hash Spreading

Conceptually, Java 8+ HashMap uses h ^ (h >>> 16). The implementation's hash method is essentially:

static final int hash(Object key) {
    int h;
    return (key == null)
            ? 0
            : (h = key.hashCode()) ^ (h >>> 16);
}

Why? Because the bucket index uses only part of the hash. Mixing high bits into low bits helps improve distribution.

Why Mix the Hash?

If a key's hashCode() has poor variation in its low bits, many keys can land in the same bucket.

Null-Key Special Case

HashMap permits one null key:

map.put(null, "Hello");

HashMap assigns hash = 0 to a null key, so null handling doesn't require calling null.hashCode() — which obviously isn't possible.

#Step 2 — Calculate the Bucket Index

For a table of size n:

index = (n - 1) & hash;

This is one of the most frequently asked HashMap questions. Why not hash % n? Because bitwise AND is efficient when n is a power of two.

Why Capacity Is a Power of 2

Typical capacities: 16, 32, 64, 128, 256, …

Suppose n = 16 → n - 1 = 15 → binary 1111. Therefore hash & 1111 efficiently extracts the relevant lower bits. This is the basis for (hash & (n - 1)).

Why Not Any Arbitrary Capacity?

HashMap therefore uses power-of-two table sizes.

#Step 3 — Find the Bucket

After calculating index = (n - 1) & hash, HashMap accesses table[index]. If table[index] == null, the entry can be inserted directly. If not, collision handling begins.

#Collisions and Treeification

Collision

A collision occurs when different keys map to the same bucket — e.g. Key A → bucket 5 and Key B → bucket 5. Even if A.equals(B) == false, they can still share a bucket.

Collision Handling

Modern HashMap can use a linked list or a Red-Black tree inside a bucket.

If the collision chain becomes large enough, bucket 5 may become a Red-Black Tree. This is called treeification.

Why Treeify?

Suppose one bucket has many entries: A → B → C → D → E → F → G → H. Searching a long linked list can approach O(n); a balanced tree provides approximately O(log n) within that bucket. So treeification improves worst-case collision behaviour.

Treeification Threshold

TREEIFY_THRESHOLD = 8

When a bucket's node count reaches the relevant threshold, HashMap may attempt to treeify the bucket.

Minimum Treeify Capacity

MIN_TREEIFY_CAPACITY = 64

If the table is too small, HashMap prefers resizing rather than treeifying.

Why Resize Instead of Treeify?

A small table (e.g. size 16 with many entries) can naturally create collisions simply because there aren't enough buckets. Rather than immediately creating trees, increasing the number of buckets spreads the entries out. So small table + collisions → resize first is generally more efficient.

Untreeification

A tree bin doesn't necessarily remain a tree forever. If entries are removed and the number falls sufficiently, HashMap can convert the tree back into a linked structure.

UNTREEIFY_THRESHOLD = 6

#Load Factor, Capacity and Threshold

Load Factor

Default load factor: 0.75f. Suppose capacity = 16, load factor = 0.75:

Threshold = 16 × 0.75 = 12

When the number of entries reaches the resize threshold, HashMap expands.

What Does Load Factor Mean?

Load factor controls the trade-off between memory and collision frequency.

The default 0.75 is a practical compromise.

Capacity vs Size vs Threshold

These are often confused.

#Resizing

What Happens During Resize?

Suppose capacity = 16, threshold = 12, and HashMap needs to resize. The table becomes 16 → 32. Generally, HashMap doubles its capacity, and the threshold is recalculated accordingly.

Why Double the Capacity?

Doubling gives HashMap a convenient property. If the old capacity is 16 and the new capacity is 32, an existing entry generally either stays at the same index or moves by +16. This is determined by a particular hash bit, which makes resizing more efficient than recomputing arbitrary bucket positions from scratch.

The Resize Bit Trick

Old capacity 16, new capacity 32 — the new bit being introduced is 16. For each entry, conceptually:

if ((hash & oldCapacity) == 0) {
    // same index
} else {
    // old index + old capacity
}

This is one reason power-of-two capacities are so useful.

Does Rehashing Call hashCode() Again?

This is a subtle interview question. During resize, HashMap generally does not need to call the key's hashCode() again for every entry. The stored hash is already available in each node; it uses the old hash and the capacity bit to determine the new position.

#The get() Journey

map.get("Java");

If the bucket is a tree, HashMap searches the Red-Black Tree; if it's a linked structure, it traverses the nodes.

Why Both hash and equals()?

If two keys have different hash codes, they cannot be the same logical key in a correctly implemented hash-based Map. So HashMap can first check the hash before calling equals(), which avoids unnecessary equality comparisons.

• Hash differs → not the key.
• Hash same → check equals().

#The equals() / hashCode() Contract

This is one of the most important HashMap concepts. If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true. The reverse isn't required: two different objects can have the same hash (hashCode() same, equals() false) — that's a collision.

Wrong hashCode() Implementation

class Employee {

    int id;

    @Override
    public boolean equals(Object o) {
        // ...
    }
}

If hashCode() isn't overridden consistently, two logically equal Employees may have different hashes, and HashMap can place them into different buckets. Result: equals() says same, HashMap lookup says different. This violates the required contract.

Correct Implementation

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (!(o instanceof Employee other)) return false;
    return id == other.id;
}

@Override
public int hashCode() {
    return Integer.hashCode(id);
}

Now: same id → equals() true → same hash.

Mutable Keys — Major Trap

Map<Employee, String> map = new HashMap<>();

Employee e = new Employee(101);
map.put(e, "John");

e.setId(999);

If id participates in hashCode(): old hash → bucket A becomes new hash → bucket B, but the entry is physically still in its original bucket. Now map.get(e) may fail.

#Thread Safety and Iteration

Why HashMap Isn't Thread-Safe

Two threads calling put() at the same time may both modify internal state concurrently. Without appropriate synchronization, operations can interfere with each other, and visibility/ordering guarantees aren't provided. Therefore HashMap is not a concurrent Map. For concurrent access, ConcurrentHashMap is usually the appropriate choice.

HashMap vs ConcurrentHashMap

We'll deep-dive into ConcurrentHashMap later.

Fail-Fast Iterator

HashMap iterators are generally fail-fast.

for (Integer key : map.keySet()) {
    if (key == 10) {
        map.remove(key);
    }
}

ConcurrentModificationException

because the Map was structurally modified outside the iterator.

Correct Iterator Removal

Iterator<Integer> iterator = map.keySet().iterator();

while (iterator.hasNext()) {
    Integer key = iterator.next();
    if (key == 10) {
        iterator.remove();
    }
}

The iterator knows about its own removal operation.

HashMap Doesn't Guarantee Ordering

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

map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

You cannot write code assuming the iteration will be 3, 1, 2 or 1, 2, 3. Neither ordering should be relied upon. For insertion order use LinkedHashMap; for sorted keys use TreeMap.

#Null Handling

HashMap permits one null key and multiple null values.

map.put(null, "A");
map.put(null, "B");

Result: null → B. Only one null key exists because keys are unique.

Why Does HashMap Allow Null but ConcurrentHashMap Doesn't?

HashMap can represent key → null without needing concurrent atomic semantics. ConcurrentHashMap deliberately disallows null because concurrent operations need a clear distinction between key absent and key mapped to null. This simplifies its concurrent API semantics.

#Constructors and Capacity

Constructors

new HashMap<>();
new HashMap<>(32);
new HashMap<>(32, 0.75f);

Parameters: initialCapacity and loadFactor.

Initial Capacity Is Not Allocated Immediately

Creating new HashMap<>(100); doesn't necessarily mean an array of 100 buckets is immediately allocated. HashMap table allocation is lazy and occurs when needed, such as during the first insertion. Requested capacities are also normalized to HashMap's power-of-two sizing rules.

Default Capacity

The commonly documented default initial capacity is 16 with load factor 0.75. Remember that the internal table is lazily allocated, so the backing array isn't necessarily created at constructor invocation.

Initial Capacity and Performance

If you know approximately how many entries will be stored, providing an appropriate initial capacity can reduce repeated resizing:

Map<Integer, Employee> map = new HashMap<>(1000);

But don't blindly over-allocate — more buckets mean more memory.

#HashMap's Core Formulas

This deserves memorization.

Complete put() Mental Model

Complete get() Mental Model

#Performance in Practice

Why HashMap Is Fast

HashMap avoids searching every entry:

That's the fundamental reason HashMap is so widely used.

Poor Hash Distribution

Suppose every key returns:

@Override
public int hashCode() {
    return 1;
}

Then A, B, C, D … all go to bucket X. Everything goes into one bucket and HashMap loses much of its expected performance advantage. With modern treeification, sufficiently large collision bins can become trees, but a pathological hash function is still a poor design.

Same Hash ≠ Same Key

A classic interview question: A.hashCode() = 100 and B.hashCode() = 100 — does HashMap treat A and B as the same key? No. It checks hash + equals(). If A.equals(B) == false, both entries can coexist.

HashMap and Object Identity

HashMap normally uses logical equality (equals()), not reference identity (==). Therefore two new String("Java") objects represent the same logical key if equals() returns true and their hashes agree. For identity-based key semantics, Java provides IdentityHashMap.

Why containsKey() Is Better Than get() != null

map.put("A", null);

Then map.get("A") == null is true — but the key exists. Therefore map.containsKey("A") is the correct test when you specifically want to know whether the key exists.

putIfAbsent() vs put()

Memory Model

HashMap has memory overhead from the table array + Node objects + references + hash values. Compared with a simple array, it's substantially more memory-intensive — but that trade-off buys fast key-based lookup.

HashMap vs ArrayList Lookup

To find the Employee with ID 5000:

• ArrayList → iterate through elements → potentially O(n)
• HashMap → employeeId → hash → bucket → employee → O(1) average

Map<Long, Employee> employees = new HashMap<>();

Employee employee = employees.get(10025L);

This is much more appropriate than repeatedly scanning a List when lookup by ID is the primary operation.

#Java 7 vs Java 8+ HashMap

This is a common senior-level interview topic.

• Older Java (Java 7-era): collision buckets were linked structures. Heavy collisions could lead to poor worst-case lookup behaviour.
• Java 8+: HashMap introduced treeification of sufficiently large collision bins.

This significantly improves pathological collision behaviour (a bucket chain of A → … → H drops from O(n) to O(log n) search).

Does HashMap Always Use Red-Black Trees?

No. Only sufficiently crowded bins can become tree bins. Most normal buckets are either empty, a single node, or a small linked structure. Tree bins are for unusually collision-heavy situations.