CAS (Compare-And-Swap) Functions in ConcurrentHashMap

ConcurrentHashMap in Java is a thread-safe, high-performance alternative to HashMap that uses Compare-And-Swap (CAS) operations to achieve lock-free updates for certain methods.

---

1. What is CAS (Compare-And-Swap)?

Compare-And-Swap (CAS) is an atomic operation that:

1. Compares the current value of a variable to an expected value.
2. Swaps (updates) the value only if it matches the expected value.
3. Returns true if the update was successful, false otherwise.

Why CAS?

• Avoids locks → Faster than synchronized
• Minimizes contention → Reduces blocking in multi-threaded environments

---

2. CAS-Based Methods in ConcurrentHashMap

1. putIfAbsent(K key, V value)

• Adds a key-value pair only if the key is not already present.
• Internally uses CAS to avoid race conditions.

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
        
        map.put("A", 1);
        map.putIfAbsent("A", 10); // Won't update because "A" exists
        map.putIfAbsent("B", 20); // Inserts "B" because it's absent
        
        System.out.println(map); // Output: {A=1, B=20}
    }
}

---

2. replace(K key, V oldValue, V newValue)

• CAS-based update: Replaces oldValue with newValue only if the key exists and has oldValue.

map.replace("A", 1, 100); // Success, "A" changes to 100
map.replace("A", 1, 200); // Fails, because "A" is now 100

---

3. compute(K key, BiFunction<K, V, V> remappingFunction)

• Atomically computes a new value based on the old value.
• CAS ensures thread safety while computing updates.

map.compute("A", (k, v) -> v == null ? 50 : v * 2); // Doubles "A"
System.out.println(map); // Output: {A=200, B=20}

---

4. computeIfAbsent(K key, Function<K, V> mappingFunction)

• If the key is absent, it atomically computes and inserts the new value.

map.computeIfAbsent("C", k -> 30); // Adds "C" with value 30
System.out.println(map); // Output: {A=200, B=20, C=30}

---

5. computeIfPresent(K key, BiFunction<K, V, V> remappingFunction)

• If the key exists, it modifies the value atomically.

map.computeIfPresent("A", (k, v) -> v + 10); // A → 210
System.out.println(map); // Output: {A=210, B=20, C=30}

---

6. merge(K key, V value, BiFunction<V, V, V> remappingFunction)

• CAS-based merge: If the key exists, combines old and new values.
• If the key is absent, simply inserts the new value.

map.merge("A", 5, Integer::sum); // Adds 5 to "A"
map.merge("D", 40, Integer::sum); // Inserts "D" with 40
System.out.println(map); // Output: {A=215, B=20, C=30, D=40}

---

3. Why is CAS Used in ConcurrentHashMap?

• Faster than locking (synchronized)
• Scalable in multi-threaded environments
• Prevents race conditions
• Reduces contention

ConcurrentHashMap uses CAS at the bucket level instead of locking the whole map.

---

4. CAS vs. Locks in Java Concurrent Collections

Feature	CAS (Compare-And-Swap)	Locks (synchronized, ReentrantLock)
Performance	🚀 Fast	🐢 Slow
Thread Blocking	❌ No Blocking (Optimistic)	✅ Blocks Threads
Scalability	✅ Scales Well	❌ Limited Scalability
Best Use Case	Low-contention, frequent updates	High-contention, complex updates

---

Conclusion

• CAS-based functions in ConcurrentHashMap improve performance without locks.
• putIfAbsent(), replace(), compute(), and merge() all use CAS internally.
• ConcurrentHashMap splits the map into segments to allow parallel updates.