HashMap Internals

#Introduction

This is one of the highest-value Java Collections chapters for interviews. If an interviewer asks "Explain how HashMap works internally," you should be able to walk through this entire chain:

Then understand: size → threshold exceeded → resize → capacity doubles → entries redistributed.

Let's break this down deeply without repeating concepts already covered in previous chapters.

#What Is HashMap?

HashMap<K,V> is a hash-table-based implementation of Map.

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

It provides average get(), put() and remove() in O(1), assuming good hash distribution. The important word is average — poor hashing or extreme collisions can change the performance characteristics.

#Internal Structure

Each bucket can contain nothing, linked nodes, or — when collision conditions warrant — a tree bin.

Node Structure

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

So each entry essentially stores hash, key, value, next. The actual JDK implementation contains additional details, but this is the important interview model.

#The put() Process

map.put("Java", 100);

Step 1 — hashCode()

For the key "Java", Java first obtains key.hashCode(), which produces an integer. For a custom object:

class Employee {
    int id;

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

HashMap uses that hash information to determine where the entry should go.

hashCode() Does NOT Directly Give the Bucket

A common interview mistake is saying "HashMap uses hashCode as the bucket index." Not exactly. hashCode() returns an integer that can be any int value. HashMap needs to transform that value into a valid table index, and modern HashMap also performs a hash-spreading step.

Hash Spreading

Conceptually, Java 8+ HashMap uses h ^ (h >>> 16) where h = key.hashCode().

Why? Because bucket selection relies heavily on the lower bits when the table size is a power of two. Mixing higher bits into lower bits helps distribute keys more effectively.

Why Mix the Upper Bits?

Suppose two keys have hash codes where the lower bits are identical but the upper bits differ. If only the lower bits influenced bucket selection, those differences would be wasted. h ^ (h >>> 16) mixes information from the high bits into the low bits, improving distribution.

Bucket Index Calculation

One of the most frequently asked HashMap questions. For a table length n:

int index = (n - 1) & hash;

Why Not %?

You might expect hash % n. HashMap instead uses hash & (n - 1) when n is a power of two.

Therefore hash & 01111 extracts the relevant lower bits. Bitwise masking is efficient and works cleanly because HashMap maintains power-of-two capacities.

Why Must Capacity Be a Power of Two?

A classic interview question. If capacity = 16, then capacity − 1 = 15 = 00001111. Masking becomes straightforward — hash & 00001111 efficiently maps hashes to indices 0 → 15. A non-power-of-two capacity would not give the same useful bitmask behaviour.

Complete Hash Calculation

Example

Suppose hash = 101101011010 and capacity = 16. Then n − 1 = 15 = 1111, and the final bucket is determined from the relevant lower bits through hash & 1111. The exact numeric result isn't important — the mechanism is.

Empty Bucket

Suppose index = 5 and table[5] == null. HashMap simply inserts table[5] → Node("Java", 100). Done.

Occupied Bucket

Then we have a hash collision — e.g. Key A → bucket 5 and Key B → bucket 5. Even if A != B, they can still map to the same bucket. This is completely normal.

#Collisions vs Duplicate Keys

Hash Collision

A collision means different keys → same bucket. It does not necessarily mean hashCode(A) == hashCode(B). Two different hash codes can still map to the same bucket, because the final bucket index uses only part of the hash.

Collision Example

Key A with hash 10 and Key B with hash 26: with a small table (16 buckets), 10 & 15 = 10 and 26 & 15 = 10, so both map to the same bucket. HashMap stores both:

How Does HashMap Distinguish Colliding Keys?

It uses hash + equals(): same bucket → compare stored hash → if necessary compare keys with equals(). The equals() method determines whether the key is actually the same logical key.

Collision ≠ Duplicate Key

This distinction is critical.

Example

map.put("A", 10);
map.put("B", 20);

If A and B collide, the bucket holds A → B — both remain. But after map.put("A", 30); the map holds A → 30, B → 20: the existing A mapping is updated.

#The equals() / hashCode() Contract

If a.equals(b) is true, a.hashCode() must equal b.hashCode().

Otherwise HashMap can place logically equal keys into different buckets.

Example of a Broken Contract

class Employee {
    int id;

    @Override
    public boolean equals(Object o) {
        Employee e = (Employee) o;
        return id == e.id;
    }

    @Override
    public int hashCode() {
        return System.identityHashCode(this);
    }
}

Now e1.equals(e2) → true, but e1.hashCode() != e2.hashCode() can occur. HashMap's assumptions are broken.

Correct Contract

If a.equals(b) == true, then a.hashCode() == b.hashCode() must also be true. But the reverse is NOT required — an extremely common interview question.

Same Hash ≠ Equal Objects

Two objects can have the same hashCode() but equals() == false. That's a collision: A.hashCode() → 100, B.hashCode() → 100, A.equals(B) → false — HashMap stores both.

Roles of hashCode() and equals()

#get() and remove() Internals

get()

map.get(key);

remove()

map.remove(key);

#Java 7 vs Java 8 and Treeification

Java 7 vs Java 8 HashMap

A very important interview topic.

This is one of the major improvements.

Why Treeification Was Introduced

A heavily collided bucket A → B → C → D → E → F → G → H → … makes searching approach O(n). Treeification changes the structure to a balanced tree, so lookup becomes approximately O(log n) within that tree.

Red-Black Tree

The tree structure used for treeified HashMap bins is a self-balancing Red-Black Tree. The goal is to prevent the collision structure from degenerating into a long linear chain.

Treeification Threshold

TREEIFY_THRESHOLD = 8

Treeification is considered when a bin becomes sufficiently populated. But HashMap doesn't immediately treeify every bin that reaches eight nodes.

Minimum Treeify Capacity

MIN_TREEIFY_CAPACITY = 64

Why Resize Instead of Treeify?

A small table naturally causes more collisions. With capacity = 16 and one bucket containing many entries, rather than immediately building a tree, HashMap may prefer to resize to 32 or 64, spreading entries across more buckets.

Correct Interview Answer

Untreeification

A tree bin can later be converted back to a linked structure when the number of nodes becomes sufficiently small. A commonly cited implementation threshold is:

UNTREEIFY_THRESHOLD = 6

The exact transition conditions are implementation details, but the concept is: many collisions → tree; entries decrease → potentially linked list.

Why Not Keep the Tree Forever?

A tree has more structural overhead than a simple linked node chain. If the bin becomes small again, the linked representation may be more efficient, so HashMap can reduce unnecessary overhead.

Treeification Is Per Bucket

HashMap doesn't become "entire Map → Red-Black Tree." Instead:

Only collision-heavy bins are treeified.

HashMap Is Still a Hash Table

Even with tree bins, HashMap is an array of buckets; some buckets may contain trees. It doesn't become a TreeMap.

HashMap's treeification is only a mechanism for handling collisions inside individual buckets.

#Load Factor, Capacity, Size and Threshold

Load Factor

Load factor controls when HashMap resizes.

Default load factor: 0.75.

threshold = capacity × loadFactor
          = 16 × 0.75
          = 12

Once the size crosses the threshold, resizing occurs.

Why 0.75?

A compromise between memory usage and collision frequency.

Capacity vs Size vs Threshold

With capacity 16 and size 10, the Map has 16 buckets but only 10 entries.

Load Factor Trade-Off

• Lower load factor (e.g. 0.50): more buckets → fewer collisions → more memory.
• Higher load factor (e.g. 0.90): fewer buckets → potentially more collisions → less table memory.

The default 0.75 is a practical balance.

Does a Higher Load Factor Always Mean Faster?

No. A higher load factor can increase collisions, leading to longer bins, more comparisons and potentially more tree bins. The correct load factor depends on workload and memory/performance trade-offs.

Does a Lower Load Factor Always Mean Faster?

No. You consume more memory and may get diminishing returns. Performance and memory must be balanced.

#Resizing

Resize

When size > threshold, HashMap grows. For the normal growth path: 16 → 32 → 64 → 128. Capacity generally doubles.

Why Double the Capacity?

Doubling allows HashMap to efficiently redistribute entries. Because capacity remains a power of two, the new bucket position can be determined efficiently — an important Java 8+ implementation optimization.

Rehashing

The term "rehashing" is often used loosely. Strictly speaking, when HashMap resizes, it doesn't necessarily recompute each key's original hashCode() from scratch. It redistributes entries based on the existing hash information and the new table capacity.

The Important Resize Trick

With old capacity 16 and new capacity 32, an existing entry's new index is either its old index or old index + old capacity, depending on a particular hash bit.

Why Only One Bit Matters During Doubling

Because new capacity = old capacity × 2, the mask gains one additional bit. Each existing entry can generally remain at the same index or move to old index + old capacity, depending on that bit. For example, an entry in bucket 3 of a 16-bucket table goes to bucket 3 or 19 (3 + 16) after resizing to 32. This avoids recalculating the complete bucket placement from scratch.

Resize Visualization

#Construction and Lazy Initialization

Initial Capacity

new HashMap<>(16); specifies an initial-capacity-related sizing expectation, not necessarily "allocate exactly 16 buckets immediately." Modern HashMap is lazily initialized — the actual table allocation happens when needed, typically on the first insertion.

Lazy Initialization

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

Creating the HashMap does not necessarily allocate the full bucket table immediately. The table is initialized when the Map first needs storage.

Default Capacity and Threshold

The commonly documented default initial capacity is 16 with load factor 0.75, and the table is lazily initialized. Once the table is initialized, the resize threshold becomes approximately 12.

Constructor Options

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

Choosing Initial Capacity

If you know approximately how many entries will be inserted, supplying a suitable initial capacity can reduce resizing:

Map<String, User> users = new HashMap<>(expectedCapacity);

But be careful: constructor capacity is not necessarily equal to the eventual internal table length at construction time. HashMap rounds sizing to its power-of-two strategy.

#put() — Complete Flow

Combine everything for map.put(key, value):

Duplicate Key During put()

map.put("A", 10);
map.put("A", 20);

HashMap finds same hash + keys equal, so A → 20. Size remains 1.

New Key During Collision

If A and B land in the same bucket but A.equals(B) == false, the bucket holds A → B and the size increases.

get() Does Not Modify the Map

A normal map.get(key) does not add an entry. It simply: hash → bucket → search → return.

#Null Handling

get() and Null Values

HashMap permits null values, so map.get("A") returning null could mean A is absent or A exists with a null value. Use map.containsKey("A") to distinguish.

Null Key Internals

HashMap allows one null key: map.put(null, "value"); works. Internally, the null key is handled specially rather than calling null.hashCode(), which would cause a NullPointerException.

Null Value

HashMap also allows map.put("A", null);. So: null key → one allowed, null value → allowed. This differs from ConcurrentHashMap.

#The Mutable Key Problem

One of the most important HashMap interview topics.

class Employee {
    int id;

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

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

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

e.id = 20;

The object remains physically in its old bucket, but its logical hash may now point to a different bucket.

Why Does get() Fail?

Because HashMap calculates the current hash of e (20) and searches bucket 20, but the entry was originally stored in bucket 10. Therefore it isn't found.

Best Practice

Use immutable keys. Good examples: String, Integer, Long, enums, records with immutable components, or carefully designed immutable domain objects.

equals() Must Be Consistent

If key equality changes after insertion, Map behaviour can become unpredictable. Keys should ideally be immutable + stable equals() + stable hashCode() while stored.

Why String Is an Excellent HashMap Key

String is effectively immutable. Its equals() and hashCode() behaviour remains stable after insertion — one reason Strings are commonly used as keys.

#Concurrency and Iteration

Java 7 HashMap Infinite Loop Issue

A historical interview topic: why could Java 7 HashMap experience an infinite loop during concurrent resize? The old implementation could transfer linked-list nodes in a way that allowed concurrent resize operations to create a cyclic linked structure — A → B → C could become A → B → C → A — so traversal could loop forever.

Java 8 Improvement

Java 8 changed the resize mechanics and introduced tree bins. The historical infinite-loop problem associated with concurrent HashMap resizing was addressed by the changed implementation.

HashMap Concurrent Modification

Even though modern HashMap is improved internally, it still should not be concurrently mutated by multiple threads without external synchronization. Use ConcurrentHashMap for concurrent Map requirements.

Fail-Fast Iterator

HashMap iterators are generally fail-fast:

for (String key : map.keySet()) {
    map.put("X", 100);
}

ConcurrentModificationException

What Does Fail-Fast Mean?

The iterator detects certain structural modifications made outside the iterator and may throw ConcurrentModificationException. The purpose is to detect programming errors early. It is not a thread-safety mechanism.

modCount

HashMap internally maintains a modification count. Iterators compare their expectedModCount against the Map's current modCount. If they differ unexpectedly, ConcurrentModificationException may be thrown.

Fail-Fast Is Best-Effort

Fail-fast behaviour is not guaranteed as a synchronization mechanism — the JDK documentation describes it as best-effort. Never write business logic that depends on ConcurrentModificationException being thrown.

Iterator Removal

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

// ... when you want to remove the current entry:
iterator.remove();

Use iterator.remove() rather than directly modifying the Map — the supported iterator-removal mechanism.

Structural vs Non-Structural Modification

A structural modification changes the Map's structure — adding or removing a mapping. Simply replacing the value of an existing mapping isn't necessarily structural, so map.put(existingKey, newValue) may not have the same iterator implications as adding/removing an entry.

HashMap Is Not Synchronized

HashMap is not thread-safe. If multiple threads modify it concurrently, use ConcurrentHashMap or another appropriate synchronization strategy.

Collections.synchronizedMap()

Map<K,V> map = Collections.synchronizedMap(new HashMap<>());

This provides synchronized access around Map operations, but iteration requires proper external synchronization according to the wrapper's contract. For high-concurrency applications, ConcurrentHashMap is usually the better fit.

#Tree Bins and Comparable

Treeification and Comparable

Tree bins need a way to order nodes. When keys are comparable in a suitable way, their ordering can help the tree structure. If keys aren't naturally comparable, HashMap has additional tie-breaking mechanisms.

Do Keys Need Comparable?

No — a common misconception. You can use HashMap<MyClass, String> without MyClass implements Comparable<MyClass>. Treeification can still occur, using internal tie-breaking logic.

Why Doesn't HashMap Require Comparable?

Because HashMap isn't a sorted collection. The tree is an internal collision-management mechanism, not a user-visible sorting feature.

HashMap Tree Bin ≠ Sorted Map

This is extremely important. If you need sorted keys, use TreeMap. Tree bins exist only to manage collisions efficiently.

#Complexity and Hash Quality

Worst-Case Complexity

Does Treeification Make HashMap O(log n)?

No — another interview trap. HashMap is still average O(1). The tree only affects individual heavily collided bins. You should not describe HashMap as O(log n) just because tree bins exist.

Why HashMap Needs Both Hash and Equals

Imagine 100,000 entries. If HashMap used only equals(), it might have to compare the requested key against every entry. Hashing narrows the search: 100,000 entries → one bucket → few candidates, then equals() identifies the exact key.

• hashCode() → narrow the search space
• equals() → confirm the exact key

Performance Depends on a Good hashCode()

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

Every key maps to the same bucket (A → B → C → D → E → …), creating heavy collision behaviour. Modern HashMap can treeify such bins when conditions permit, but a good hash function is still essential.

Constant Hash Code Example

class BadKey {
    int id;

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

    @Override
    public boolean equals(Object obj) {
        return this == obj;
    }
}

Every key goes to the same bucket — terrible for distribution.

HashMap Doesn't Guarantee Order

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

The iteration order is not guaranteed to be A, B, C. Use LinkedHashMap for insertion/access order, and TreeMap for sorted order.

HashMap Memory Model

#The Complete HashMap Mental Model

Memorize this. If you can explain it naturally, you understand HashMap internals at an interview-ready level.