What is HashMap in java 8?

Definition:

• HashMap is a non-synchronized implementation of the Map interface.
• It stores key–value pairs and allows one null key and multiple null values.

Key Points:

1. Not thread-safe — multiple threads accessing it simultaneously can cause data inconsistency.
2. Performance is high in single-threaded environments.
3. Allows null key and values.
4. Backed by buckets (array + linked list / tree) for storing entries.
5. From Java 8 onward, uses red-black trees for buckets with high collisions (for faster lookup).
6. Fail-fast iterator — throws ConcurrentModificationException if modified while iterating.
7. Ideal for non-concurrent use cases.

🧩 What is HashMap Internally?

🧱 Internal Data Structure

In Java 8 and above:

HashMap = Array + LinkedList + Red-Black Tree

Each entry in the array is called a bucket.
Each bucket can hold:

• null (if empty)
• one Node (key, value, hash, next) (if one element)
• Linked list of Nodes
• Tree of Nodes (Red-Black tree) (if many hash collisions)

---

⚙️ 1. Internal Classes

Each entry is stored as a Node object:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next; // points to next node in the same bucket
}

---

🧠 2. How a Key-Value Pair is Stored (Processing Flow of put())

Let’s break down what happens when you call:

map.put("John", 25);

🔹 Step 1 — Compute hash

hash = key.hashCode()
Then HashMap applies hash spreading to reduce collisions:

hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

This mixing ensures better distribution across buckets.

---

🔹 Step 2 — Find the bucket index

index = (n - 1) & hash;   // n = array size (capacity)

This formula maps the hash value to a bucket index (using bit masking).

---

🔹 Step 3 — Check if bucket is empty

• If bucket[index] is null, create new Node and insert.
• If bucket[index] already has a node, we have a collision.

---

🔹 Step 4 — Handle collision

1. Compare existing node’s key:
   • If same key (equals) → update value.
   • Else → traverse the linked list or tree.
2. If bucket length exceeds TREEIFY_THRESHOLD (8) → convert LinkedList → Red-Black Tree for faster lookup.

---

🔹 Step 5 — Check load factor and resize

• HashMap has a default capacity of 16 and load factor of 0.75.
• When number of entries > capacity * loadFactor → resize() happens.

threshold = capacity * loadFactor;

🔁 Resizing Process

1. Create new array of double capacity.
2. Recalculate bucket position for all keys.
3. Rehash and redistribute entries.

---

🔍 3. How a Value is Retrieved (get(key))

Example:

map.get("John");

Processing flow:

1. Compute hash from the key.
2. Find the bucket index.
3. Traverse the linked list or tree in that bucket.
4. Compare each node’s key using equals().
5. Return value if match found; else null.

---

⚙️ 4. HashMap Capacity and Load Factor

Property	Default	Meaning
Initial Capacity	16	Size of internal array
Load Factor	0.75	Controls when to resize
Threshold	12 (16×0.75)	Resize when this many entries are reached

Example:
If you have 12 entries in a map of capacity 16 → next insert triggers resize to 32.

---

🌳 5. Why Red-Black Tree?

• Before Java 8, collisions were handled by LinkedList → O(n) lookup.
• After Java 8, when a bucket has many items (≥8), it converts to Red-Black Tree → O(log n) lookup.
• This prevents performance degradation due to hash collisions.

HashMap VS ConcurrentHashMap?

Feature / Aspect	HashMap	ConcurrentHashMap
Package	java.util	java.util.concurrent
Thread Safety	❌ Not thread-safe	✅ Thread-safe
Locking Mechanism	No locking	Bucket-level / CAS-based locking
Concurrency Level	Single-threaded	Multiple threads can read/write concurrently
Allows Null Key/Value	✅ Yes (1 null key, multiple null values)	❌ No null key or value
Iterator Type	Fail-fast	Fail-safe (weakly consistent)
Performance	Faster in single-threaded	Better in multi-threaded
Structure (Java 8+)	Array + LinkedList/Tree	Array + Node + CAS operations
When to Use	When only one thread accesses the map	When multiple threads access/modify the map
Exception During Concurrent Modification	ConcurrentModificationException	No exception
Introduced In	JDK 1.2	JDK 1.5

HashMap VS ConcurrentHashMap vs SynchronizedMap

Feature	HashMap	SynchronizedMap	ConcurrentHashMap
Thread Safe	❌ No	✅ Yes	✅ Yes
Locking	None	Whole Map	Partial (Bucket-level)
Performance	Fast	Slow	Fast (High concurrency)
Null Key/Value	Allowed	Allowed	❌ Not Allowed
Iterator Type	Fail-fast	Fail-fast	Weakly consistent
Introduced In	Java 1.2	Java 1.2	Java 1.5

🏁 Summary

• Use HashMap → when single-threaded, for speed.
• Use SynchronizedMap → when simple thread safety is needed but not high performance.
• Use ConcurrentHashMap → when high concurrency is required (most real-world multithreaded cases).