HashMap and ConcurrentHashMap in Java: An Insightful Look at Efficiency and Safety

Introduction

Java provides various data structures for efficient data storage and retrieval. Among them, HashMap and ConcurrentHashMap are widely used for key-value storage. This blog delves into the internals of HashMap and ConcurrentHashMap, their working principles, and the differences between them.

---

1. HashMap Internal Working

1.1 Data Structure

HashMap in Java is implemented using an array of nodes (buckets), where each node represents a linked list (or a red-black tree in case of high collision scenarios).

1.2 Put Operation

1. Hashing: The key's hashCode() is computed.

2. Index Calculation: The index is determined using bitwise AND instead of modulus for efficiency:

    index = (n - 1) & hash;  // where n is the capacity
   

3. Collision Handling:

   • If the bucket is empty, the key-value pair is stored directly.

   • If a key exists, the value is updated.

   • If multiple entries exist, a linked list is traversed.

   • If the list grows beyond TREEIFY_THRESHOLD (default: 8), it converts into a red-black tree for efficient lookups.

Example of Put Operation with Collision

HashMap<Integer, String> map = new HashMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.put(1, "D"); // Overwrites "A" with "D"
System.out.println(map); // Output: {1=D, 2=B, 3=C}

1.3 Get Operation

1. The key's hashCode() is computed.

2. The index is determined using bitwise AND.

3. The bucket is searched via linked list traversal or tree lookup.

Example of Get Operation

System.out.println(map.get(1)); // Output: D
System.out.println(map.get(4)); // Output: null (key not present)

1.4 Resize Mechanism

When the number of elements exceeds LOAD_FACTOR (0.75) × capacity, the HashMap resizes itself by doubling the size and rehashing the elements.

1.5 Problems with HashMap in Multithreading

• Race Conditions: Multiple threads modifying HashMap can lead to data corruption.

• Infinite Loops: Resizing in a multi-threaded environment may cause linked lists to form circular references, leading to infinite loops.

---

2. ConcurrentHashMap Internal Working

2.1 Need for ConcurrentHashMap

HashMap is not thread-safe, leading to race conditions in a multi-threaded environment. ConcurrentHashMap provides a thread-safe alternative without requiring external synchronization (like Collections.synchronizedMap).

2.2 Segmentation (Pre-Java 8)

Before Java 8, ConcurrentHashMap used Segment-based locking:

• The map was divided into segments (default: 16), each acting as an independent HashMap.

• Multiple threads could operate concurrently on different segments, reducing contention.

2.3 Bucket-Level Locking (Java 8+)

• Java 8 removed segments and introduced bucket-level locks using CAS (Compare-And-Swap) and synchronized blocks for updates.

• A fine-grained locking mechanism ensures better performance than segment-based locking.

Example of ConcurrentHashMap Usage

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<Integer, String> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put(1, "A");
concurrentMap.put(2, "B");
System.out.println(concurrentMap.get(1)); // Output: A

2.4 Differences from HashMap

---

3. When to Use Which?

• Use HashMap when single-threaded performance is required.

• Use ConcurrentHashMap when thread safety is a concern without needing explicit locks.

---

Conclusion

Understanding the internals of HashMap and ConcurrentHashMap helps in making better design choices when working with Java collections. HashMap is efficient in single-threaded scenarios, while ConcurrentHashMap ensures thread safety without compromising performance. Choose wisely based on your application needs!