Java Collections (internal workings) - How Hashmap works internally

 

📦 Java Collections – Internal Workings & Use Cases

---

1. List Implementations

Class	Backed By	Key Traits	Time Complexity
ArrayList	Dynamic array	Fast random access; resize costs	O(1) get, O(n) add (worst)
LinkedList	Doubly linked list	Fast insert/delete at ends	O(n) get, O(1) addFirst/last
Vector	Synchronized array	Legacy, thread-safe	Slower than ArrayList

✅ Use When:

• Use ArrayList for frequent reads/random access

• Use LinkedList for frequent inserts/deletes

---

2. Set Implementations

Class	Backed By	Key Traits	Time Complexity
HashSet	HashMap	No duplicates, no order	O(1) add/contains
LinkedHashSet	Linked HashMap	Maintains insertion order	O(1) add, ordered
TreeSet	Red-Black Tree (self-balancing BST)	Sorted, no duplicates	O(log n) add/search

✅ Use When:

• HashSet for fast lookups

• LinkedHashSet to preserve order

• TreeSet to maintain sorted elements

---

3. Map Implementations

Class	Backed By	Key Traits	Time Complexity
HashMap	Array + Linked List / Tree (after Java 8)	Unordered, allows nulls	O(1) get/put (avg)
LinkedHashMap	HashMap + Doubly Linked List	Maintains access/insertion order	O(1) get, ordered
TreeMap	Red-Black Tree	Sorted by keys	O(log n)
ConcurrentHashMap	Segmented/striped locking → Java 7, lock-free buckets (Java 8+)	Thread-safe	O(1) concurrent get/put

✅ HashMap (Java 8+) uses:

• Buckets (array of nodes)

• Converts bucket to TreeNode (Red-Black Tree) if bucket > 8 elements → speeds up worst-case from O(n) to O(log n)

✅ Use When:

• HashMap for general usage

• LinkedHashMap for LRU caches

• TreeMap for sorted data

• ConcurrentHashMap in multithreaded scenarios

---

4. Queue & Deque

Interface	Common Implementations	Key Use
Queue	LinkedList, PriorityQueue	FIFO
Deque	ArrayDeque, LinkedList	Double-ended queue
BlockingQueue	ArrayBlockingQueue, LinkedBlockingQueue, DelayQueue	Thread-safe, producer/consumer

✅ PriorityQueue is min-heap (O(log n) insert)
✅ ArrayDeque is more efficient than Stack/LinkedList for LIFO/FIFO operations

---

5. Thread-safe Collections

Class	Description
Vector, Hashtable	Legacy synchronized
Collections.synchronizedList()	Wrapper for any collection
ConcurrentHashMap	High-concurrency map
CopyOnWriteArrayList	Good for read-heavy workloads; copy on every write

✅ Choose CopyOnWriteArrayList for config-heavy apps (low writes, frequent reads)

---

🧠 Interview Answer Template

“I chose LinkedHashMap because we needed fast lookups with insertion order preserved. Internally, it uses a doubly linked list in addition to a HashMap, giving O(1) access while keeping elements ordered. It was ideal for building an LRU cache mechanism in our API gateway.”

---

✅ Summary Table

Need	Collection
Fast access, no order	HashMap, HashSet
Maintain order	LinkedHashMap, LinkedHashSet
Sorted	TreeMap, TreeSet
Thread-safe reads	ConcurrentHashMap, CopyOnWriteArrayList
LIFO / Stack	ArrayDeque
Priority-based queue	PriorityQueue

How HashMap works internally?

 What is HashMap?

A HashMap<K, V> is a key-value data structure that allows fast lookups, inserts, and deletions using hashing. It is not thread-safe, allows one null key, and multiple null values.

---

⚙️ Internal Architecture (Java 8+)

A HashMap is internally backed by:

• An array of Node<K,V> called the bucket array

• Each bucket is a linked list (or a Red-Black tree if it grows too large)

• Hash collisions are handled by chaining

Core Components:

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

---

🔄 Key Operations

1. Put (K key, V value)

Steps:

1. Compute Hash of the key

   • Uses hashCode() and spreads it using hash(hashCode) = h ^ (h >>> 16) to reduce collisions

2. Determine bucket index

   index = (n - 1) & hash;
   

3. Check if key exists in bucket

   • If yes → update value

   • If no → insert a new node

4. If bucket has > 8 elements, convert to Red-Black Tree for better performance

✅ Tree threshold is 8, resize threshold is 0.75 × capacity

---

2. Get (K key)

Steps:

1. Compute the hash

2. Find the index

3. Traverse the bucket (linked list or tree)

4. Return value if key matches

---

3. Resize / Rehashing

When the number of entries exceeds the load factor (default: 0.75), the capacity is doubled, and all existing nodes are rehashed and moved to new buckets.

---

📊 HashMap vs TreeMap vs LinkedHashMap

Feature	HashMap	TreeMap	LinkedHashMap
Order	No	Sorted	Insertion
Backing Structure	Array + LinkedList/Tree	Red-Black Tree	HashMap + Doubly LinkedList
Performance	O(1)	O(log n)	O(1)

---

🌳 Java 8 Optimization: Treeification

If too many entries hash to the same bucket (≥ 8), and capacity ≥ 64:

• The bucket is converted from LinkedList → Tree (Red-Black Tree)

• Improves worst-case get() and put() from O(n) → O(log n)

If size drops below 6, the tree may untreeify back to a linked list.

---

🔐 Hash Collision Example

Two different keys with the same hashCode():

String s1 = "FB";  // hashCode = 2236
String s2 = "Ea";  // hashCode = 2236

These will go into the same bucket and form a chain (or tree if more collide).

---

🔥 Interview-Ready Answer

“HashMap uses a combination of an array and linked list/tree to store key-value pairs. It computes the hashCode, spreads the bits to avoid collisions, and places the entry in the computed bucket. If too many keys collide into the same bucket, it uses treeification to improve performance. Resizing is triggered when the size exceeds the load factor. I chose HashMap in our application to ensure fast constant-time lookups for large datasets.”

---

Great! Let’s go deeper into the core concepts that make HashMap tick: hashing, hashCode(), equals(), and how it handles collisions. These are critical interview topics, especially for Java Architect and Senior Developer roles.

---

🔢 1. Hashing in HashMap

Hashing is the process of converting a key into an integer (the hash code) that determines where the entry is stored in the bucket array.

Java’s Hashing Formula:

hash = hash(key.hashCode()) = h ^ (h >>> 16)

✅ This bit manipulation (XOR with right-shift) is a Java 8 optimization to reduce collision chances by spreading the hash bits.

---

🧪 2. hashCode() and equals() Contracts

hashCode()

• Returns an integer value for an object.

• Should be consistent with equals():

  If a.equals(b) is true, then a.hashCode() == b.hashCode() must be true.

equals()

• Used to determine object equality, especially within a bucket (after a hash match).

• Important when keys collide (same hash, different objects).

---

🔄 Flow in HashMap.get(key):

1. Compute hash from key.

2. Go to bucket at index (n - 1) & hash.

3. Check each node:

   • If node.hash == hash && node.key.equals(key) → return value.

So:

• hashCode() determines bucket

• equals() finds the exact key inside the bucket

---

⚠️ 3. What Are Hash Collisions?

A collision occurs when two different keys produce the same hash index.

String a = "FB"; // hashCode() = 2236
String b = "Ea"; // hashCode() = 2236

Both a and b will go to the same bucket.

HashMap handles collisions using:

1. Chaining via Linked List (pre-Java 8)

2. Tree (Red-Black Tree) after Java 8 if:

   • ≥ 8 entries in a bucket

   • HashMap capacity ≥ 64

---

🔥 Example Scenario

Map<String, String> map = new HashMap<>();
map.put("FB", "value1");
map.put("Ea", "value2");

Internally:

• Both keys have same hashCode()

• They go to the same bucket

• HashMap uses equals() to distinguish between them

If:

map.get("FB"); // returns "value1"
map.get("Ea"); // returns "value2"

Even though they have same hashCode, they're distinct due to equals().

---

💡 Best Practices for Custom Keys

When using custom objects as keys in a HashMap:

✅ Override both hashCode() and equals() properly.

@Override
public int hashCode() {
    return Objects.hash(id, name);
}

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    MyKey other = (MyKey) o;
    return id == other.id && name.equals(other.name);
}

---

🧠 Interview Answer Template

“HashMap relies on hashCode() to determine the bucket and equals() to resolve exact matches inside the bucket. In the event of a collision, where two keys have the same hash, Java 8+ optimizes this by switching from a linked list to a red-black tree once the threshold is reached. This keeps lookup time near O(1) even under high collision scenarios. Ensuring consistent hashCode() and equals() implementations for custom keys is essential for correct behavior.”

Understanding how equals() and hashCode() work in Java is crucial for correctly implementing behavior in collections like HashMap, HashSet, and Hashtable.

---

✅ 1. equals() – Logical Equality

• Defined in: Object class

• Used to compare the contents (logical equality) of two objects.

Default behavior:

Object.equals(Object obj) → true if both references point to the same object.

Custom behavior (Override in your class):

@Override
public boolean equals(Object o) {
    if (this == o) return true;
    if (o == null || getClass() != o.getClass()) return false;
    MyClass that = (MyClass) o;
    return this.id == that.id;
}

---

✅ 2. hashCode() – Hash-based Identity

• Returns an int hash code used in hash-based collections.

• Must be consistent with equals():

  If two objects are equal (a.equals(b) is true), they must return the same hash code.

Default behavior:

Object.hashCode() → memory address-based integer.

Custom behavior:

@Override
public int hashCode() {
    return Objects.hash(id); // consistent with equals()
}

---

🔄 Relationship Between equals() and hashCode()

Condition	Result
If a.equals(b) is true	Then a.hashCode() == b.hashCode()
If a.hashCode() == b.hashCode()	Not necessarily a.equals(b)
If a.equals(b) is false	They can still have the same hash code (collision)

---

📘 Why Both Matter in Hash-Based Collections

Example: HashMap

Map<Employee, String> map = new HashMap<>();
map.put(new Employee(1, "John"), "Dev");
map.get(new Employee(1, "John")); // Might return null if equals/hashCode not implemented

If equals() and hashCode() are not overridden, this get() may fail because:

• HashMap uses hashCode() to find the bucket

• Then uses equals() to match the key

---

🧠 Interview Tip

“Always override both equals() and hashCode() together. Failing to do so can break collections like HashMap or HashSet, causing lookup and insertion anomalies.”

---

✅ Example

public class Employee {
    int id;
    String name;

    // Constructor

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

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

✅ What is a TreeMap?

TreeMap<K, V> is a part of the Java Collections Framework that implements the NavigableMap interface and stores key-value pairs in sorted order.

---

🌲 How Does TreeMap Maintain Order?

➤ Internally, TreeMap uses a Red-Black Tree, which is a type of self-balancing binary search tree (BST).

• Keys are sorted according to their natural ordering (Comparable)
  OR

• By a custom Comparator passed during construction.

🧠 Red-Black Tree Properties:

• Each node is red or black.

• The root is black.

• No two red nodes are adjacent.

• Every path from root to leaf has the same number of black nodes.

• Guarantees O(log n) time complexity for get(), put(), remove().

---

📘 Example 1: Natural Ordering

TreeMap<Integer, String> map = new TreeMap<>();
map.put(5, "A");
map.put(2, "B");
map.put(8, "C");
map.put(1, "D");

System.out.println(map); // Output: {1=D, 2=B, 5=A, 8=C}

• Sorted in ascending key order (1, 2, 5, 8) because Integer implements Comparable.

---

📘 Example 2: Custom Comparator

TreeMap<String, String> map = new TreeMap<>(Comparator.reverseOrder());
map.put("apple", "A");
map.put("banana", "B");
map.put("cherry", "C");

System.out.println(map); // Output: {cherry=C, banana=B, apple=A}

• Sorted in descending order using a custom Comparator.

---

🧪 Interview-Ready Answer

“TreeMap maintains order using a Red-Black Tree, a self-balancing BST. It keeps keys sorted either by natural ordering (via Comparable) or using a custom Comparator. Every insertion and deletion ensures the tree remains balanced, so operations like put(), get() and remove() take O(log n) time.”