# Part 4 — HashMap Deep Dive (Most Important)

If there is one Collections topic you must master for senior Java interviews, it is HashMap.

At companies like Oracle, Amazon, Microsoft, Goldman Sachs, JPMC, Walmart, SAP, and Visa, interviewers frequently spend 20–40 minutes on HashMap internals.

This part covers the fundamentals. In the next lesson, we'll dive into equals(), hashCode(), and advanced scenarios.

1. What is HashMap?¶

HashMap is a hash table implementation of the Map interface.

It stores key-value pairs.

Example:

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

map.put(101, "Alice");
map.put(102, "Bob");
map.put(103, "Charlie");

Output:

101 -> Alice
102 -> Bob
103 -> Charlie

Characteristics:

• Stores key-value pairs
• Duplicate keys are not allowed
• Duplicate values are allowed
• Allows one null key
• Allows multiple null values
• Not synchronized
• Average O(1) lookup

2. Internal Data Structure¶

The most important interview point:

HashMap is backed by an array of buckets.

Simplified JDK implementation:

transient Node<K,V>[] table;

Each bucket contains a linked list or a red-black tree.

Bucket Array

Index

0   1   2   3   4   5   6

|   |   |   |   |   |   |

↓

Bucket

↓

Node -> Node -> Node

Think of it as:

Array

↓

Each cell points to

↓

Linked List (Java 7)

or

Red-Black Tree (Java 8+ when needed)

3. Node Structure¶

Simplified JDK code:

static class Node<K,V> {

    final int hash;

    final K key;

    V value;

    Node<K,V> next;
}

Each node stores:

• hash
• key
• value
• next node

4. How put() Works¶

Suppose:

map.put("Apple", 100);

Steps:

Step 1¶

Calculate hash

hash = key.hashCode();

Example:

"Apple"

↓

63476543

Step 2¶

Spread the hash (Java 8)

hash = h ^ (h >>> 16);

Why?

To distribute keys more uniformly across buckets, especially when the table size is small.

Step 3¶

Calculate bucket index

index = (table.length - 1) & hash;

If capacity = 16:

hash

↓

101011011

↓

index = 11

Using bitwise AND is faster than modulo because capacities are powers of two.

Step 4¶

Go to bucket 11

Bucket 11

↓

empty

Insert node.

Bucket 11

↓

Apple

Done.

5. Collision¶

What if another key maps to the same bucket?

Bucket 5

↓

Apple

↓

Orange

This is called a collision.

Collisions are normal and expected.

HashMap is designed to handle them efficiently.

6. Collision Handling¶

Java 7¶

Bucket

↓

Node

↓

Node

↓

Node

Only linked lists.

Worst case:

O(n)

Java 8+¶

If too many nodes accumulate in one bucket:

Linked List

↓

Red-Black Tree

Worst case improves to:

O(log n)

7. Treeification¶

Treeification occurs only if both conditions are met:

1. Bucket size ≥ 8
2. Table capacity ≥ 64

Node

↓

Node

↓

Node

↓

Node

↓

Node

↓

Node

↓

Node

↓

Node

↓

Convert

↓

Red-Black Tree

Why require capacity ≥ 64?

If the table is still small, resizing is usually a better solution than building a tree.

8. Untreeification¶

If deletions reduce the bucket size below 6, the tree is converted back into a linked list.

Tree

↓

Delete nodes

↓

6

↓

Linked List

Using separate thresholds (8 and 6) avoids frequent conversions when the bucket size fluctuates.

9. Resize¶

Initial capacity:

16

Default load factor:

0.75

Threshold:

16 × 0.75

=

12

When the 13th entry is inserted:

Capacity

16

↓

32

The map resizes and redistributes entries.

10. Load Factor¶

Default:

0.75

Meaning:

Capacity = 16

Threshold = 12

Resize occurs after 12 entries.

Higher load factor:

• Less memory
• More collisions

Lower load factor:

• More memory
• Fewer collisions

11. Capacity¶

Example:

new HashMap<>(32);

Capacity becomes:

32

Threshold:

32 × 0.75

=

24

Interview point: HashMap internally rounds capacities up to the next power of two if necessary.

Example:

new HashMap<>(20);

Internal capacity becomes:

32

12. Why Powers of Two?¶

Interview favorite.

Capacity:

16

Binary:

10000

Index calculation:

(hash & (capacity - 1))

Works correctly only when capacity is a power of two, giving a fast and uniform mapping.

13. get() Operation¶

Example:

map.get("Apple");

Steps:

1. Compute hash.
2. Compute bucket index.
3. Go to bucket.
4. Compare hash.
5. Compare keys using equals().
6. Return value if found.

Average complexity:

O(1)

Worst case:

O(log n)

(Java 8 tree bucket)

or

O(n)

(Linked list bucket)

14. containsKey()¶

Internally similar to get().

map.containsKey("Apple");

Steps:

• Compute bucket
• Traverse bucket
• Compare keys

Average:

O(1)

15. remove()¶

Example:

map.remove("Apple");

Steps:

• Compute bucket
• Find node
• Remove it
• Re-link the chain if necessary

Average:

O(1)

16. Null Key Handling¶

HashMap allows one null key.

Example:

map.put(null, "Admin");

Internally:

null

↓

Bucket 0

No hashCode() call is made for a null key.

If another null key is inserted:

map.put(null, "Manager");

The value is replaced.

Final map:

null

↓

Manager

17. Why Duplicate Keys Are Not Allowed¶

Example:

map.put(1, "A");

map.put(1, "B");

Second insertion:

• Finds the existing key using equals()
• Replaces the value

Result:

1 -> B

18. Java 7 vs Java 8¶

19. Time Complexity¶

*Worst case is O(n) if the bucket remains a linked list. Treeified buckets reduce this to O(log n).

20. Production Tips¶

Good Practices¶

• Use immutable keys where possible.
• Override both equals() and hashCode() correctly.
• Set an appropriate initial capacity when the expected size is known.
• Avoid mutable fields in keys.

Avoid¶

class Employee {
    int id;

    public int hashCode() {
        return 1;
    }
}

This forces every key into the same bucket, degrading performance dramatically.

Common Interview Questions¶

Q1. Why is HashMap lookup O(1)?¶

Because it computes the bucket index directly from the hash and usually searches only a very small number of entries.

Q2. Why is capacity always a power of two?¶

To enable efficient index calculation using bitwise AND and to promote an even bucket distribution.

Q3. Why does HashMap allow only one null key?¶

All null keys map to the same special bucket (bucket 0). Since keys are unique, inserting another null key replaces the previous value.

Q4. What causes collisions?¶

Different keys can produce the same bucket index, either because they have identical hash codes or because different hash codes map to the same bucket after indexing.

Q5. When does a linked list become a tree?¶

When:

• Bucket size ≥ 8
• Table capacity ≥ 64

Q6. Why is the untreeification threshold 6 instead of 7?¶

To introduce hysteresis, preventing repeated conversions between linked lists and trees when bucket sizes fluctuate around the threshold.

Senior-Level Interview Notes¶

A strong candidate should be able to explain:

• Why hashCode() is called before equals()
• Why equal objects must have equal hash codes
• Why unequal objects can have equal hash codes
• How resizing works
• Why resizing is expensive
• Why capacities are powers of two
• How collisions affect performance
• Why treeification was introduced in Java 8

These topics almost always lead into the next discussion.

Key Takeaways¶

• HashMap uses an array of buckets.
• Each bucket contains a linked list or a red-black tree.
• Average lookup, insertion, and removal are O(1).
• Treeification occurs at 8 nodes with a minimum table capacity of 64.
• Default load factor is 0.75.
• Capacities are powers of two.
• Correct implementations of equals() and hashCode() are essential for correctness and performance.

What's Next¶

The next session is Part 4.1 — equals() and hashCode() Deep Dive, where we'll examine:

• The contract between equals() and hashCode()
• Why overriding one requires overriding the other
• How HashMap uses them internally
• Common bugs and interview pitfalls
• Mutable keys
• Real-world production scenarios

This is one of the highest-yield topics in senior Java interviews because it directly determines whether HashMap behaves correctly.