Java Questions on Collections

Day-1
1. How does HashMap work internally?
Answer:
High-Level Internal Structure
Internally, HashMap uses:
Array + LinkedList + Red-Black Tree (Java 8+)

Internal Data Structure

transient Node<K,V>[] table;

This is an array of buckets.
Each bucket stores:
single node
linked list
tree nodes

Basic Working Flow
When you do:

map.put(key, value);

HashMap performs:

1. Calculate hashCode()
2. Calculate bucket index
3. Store value in bucket
4. Handle collision if needed

Step-by-Step Example

Map<Integer, String> map = new HashMap<>();
map.put(101, "John");
map.put(102, "David");
map.put(103, "Alex");

Now let us understand internally what happens.
Step 1: Create HashMap

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

Internally:
capacity = 16
loadFactor = 0.75
threshold = 12

Meaning:
resize after 12 elements
Internal Array

Initially: table[16]
Like:
index
0
1
2
...
15

All buckets empty initially.
Step 2: Insert First Entry

map.put(101, "John");

Internal Working
A. Calculate hashCode()
For Integer:

hash = key.hashCode()

For 101: hash = 101
B. Calculate Bucket Index
Formula:

index = (n - 1) & hash

Where: n = capacity = 16
So: 15 & 101
Binary:
15 = 00001111
101 = 01100101

Result: 5
So element stored in: bucket 5

Internal Structure

table[5] → Node(101, "John")

Step 3: Insert Another Entry
map.put(102, "David");
Hash: 102
Index: 15 & 102 = 6
Stored at: bucket 6

Current Structure
table[5] → (101, John)
table[6] → (102, David)

What is a Node Internally?
Simplified internal class:

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

Collision Handling
Now suppose:

map.put(117, "Mike");

Why Collision Happens?
Index formula: 15 & 117 = 5
Same bucket as 101.

Now What Happens?
HashMap creates linked list.
table[5]
↓
(101, John)
↓
(117, Mike)

This is collision handling.
How Retrieval Works
Suppose:

map.get(117);

Step-by-Step Retrieval

Step 1: Calculate hash
hash = 117
Step 2: Find bucket
15 & 117 = 5

Go to bucket 5.
Step 3: Traverse nodes
Bucket contains:

(101, John)
(117, Mike)

HashMap checks: equals()
until matching key found.
Returns: Mike
Why equals() is Important?
Hash collision possible.
So HashMap uses:
`1. hashCode()

1. equals()`

Both are mandatory.
Internal Put Logic (Simplified)

public V put(K key, V value) {
    int hash = hash(key);
    int index = (table.length - 1) & hash;
    Node<K,V> node = table[index];
    if(node == null) {
        table[index] = new Node<>(hash, key, value);
    } else {
        // collision handling
        // traverse linked list
        // compare using equals()
        // update or append
    }
}

Java 8 Optimization

Before Java 8:
collisions stored as linked list only
Problem: worst-case O(n)

Java 8 Improvement
If bucket size becomes: > 8
Linked list converts to: Red-Black Tree
called: Treeification
Now complexity becomes: O(log n)
instead of: O(n)
Visual Example
Before Treeify
Bucket 5:
A → B → C → D → E → F → G → H → I
Search slow.

After Treeify
          D
        /   \
       B     G
      / \   / \
     A  C  F  I

Faster searching.
Important Interview Point
Why Capacity Always Power of 2?
Because index calculation:

(n - 1) & hash

is faster than modulo:

hash % n

Load Factor Default: 0.75

Meaning: resize when 75% full

Rehashing
When threshold exceeded:

1. New bigger array created
2. Entries redistributed Example: 16 → 32

*Why Immutable Keys Recommended?
*
Suppose:

class Employee {

    String name;
}

If name changes:

• hashCode changes
• retrieval fails

Very dangerous.
That is why:

• String
• Integer
• immutable objects

recommended as keys.

**Real Interview Example
**Bad Mutable Key

class Employee {
    String name;
    Employee(String name) {
        this.name = name;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
    @Override
    public boolean equals(Object obj) {
        Employee e = (Employee) obj;
        return this.name.equals(e.name);
    }
}

Problem

Employee e = new Employee("John");
map.put(e, "Developer");
e.name = "David";
map.get(e); // FAILS

Because:

• bucket changed
• object unreachable

Time Complexity
Operation Average Worst
put O(1) O(n)
get O(1) O(n)
remove O(1) O(n)

Java 8 treeification improves worst case:

O(log n)

Internal Hash Function
Java improves hash distribution:

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

This avoids poor bucket distribution.
*Null Handling *
HashMap allows:

• one null key
• multiple null values

Null key always stored in: bucket 0
Important Differences
Feature HashMap Hashtable
Thread-safe No Yes
Null allowed Yes No
Performance Faster Slower