Compare-And-Swap (CAS): Building a Concurrent HashMap from Scratch

From Locks to CAS: A Better Way to Handle Concurrency

When multiple threads access and update shared data structures, we run into a fundamental problem: race conditions. If two threads try to update the same variable at the same time, one might overwrite the other’s changes, leading to inconsistent or incorrect results.

Traditionally, we solve this problem using locks (synchronized, ReentrantLock, etc.). But locks can cause contention, block threads, and reduce performance in highly concurrent systems.

That’s where Compare-And-Swap (CAS) comes in.

Here is a side by side comparision when you are blocking threads at the OS or Java VM level (quite expensive 💸) vs at hardware level

Image1: Blocking threads at the OS or Java VM level is expensive

Image2: Hardware provided atomic operations are cheaper

Locking at the OS/VM Level (First Diagram)

In the first image, Thread 1 holds a lock on a shared data structure.

• While Thread 1 is inside the critical section, Thread 2 has to wait.

• The OS or JVM blocks Thread 2, meaning it might get descheduled and put to sleep.

• Waking it back up later involves expensive context switches, kernel involvement, and wasted CPU cycles.

**Key point: Locks block threads at the OS/VM level, which is costly. That’s why under contention, lock-based solutions don’t scale well.

Lock-Free with CAS (Second Diagram)

In the second image, instead of acquiring a heavyweight lock, both threads try to update using CAS.

• Thread 1 attempts a CAS update.

• If Thread 2 sneaks in and updates first, Thread 1’s CAS fails.

• But instead of blocking, Thread 1 just retries immediately in a tight loop.

• The "blocked time" is tiny (just CPU cycles) instead of OS-level thread parking.

**Key point: CAS works at the hardware CPU instruction level, so retries are cheap compared to thread suspension.

How does CAS work?

When multiple threads access a critical section, the traditional way to ensure correctness is by using locks. But locks can cause performance issues like contention, blocking, or even deadlocks.

An alternative is CAS (Compare-And-Swap) — a lock-free synchronization technique.

Here’s how CAS works:

1. A thread reads the current value of a variable.

2. It compares this value with the expected value (what it originally read).

3. If the values match then it updates the variable to a new value and returns true.

4. If the values don’t match then another thread must have modified the value, so the operation fails and returns false.

This ensures that updates happen safely without locking, because only the thread that sees the value unchanged can modify it.

---

import java.util.concurrent.atomic.AtomicBoolean;

public class CompareAndSwapLock {

    // Atomic boolean to represent lock state: false = unlocked, true = locked
    private final AtomicBoolean atomicLocked = new AtomicBoolean(false);

    // Acquire lock
    public void lock() {
        // Keep trying until CAS succeeds
        while (!atomicLocked.compareAndSet(false, true)) {
            // busy-wait (spin) until lock is free
        }
    }

    // Release lock
    public void unlock() {
        atomicLocked.set(false);
    }
}

Let’s see how this code will work on 2 threads.

Step 1: Thread-1 calls lock()

• compareAndSet(false, true) is checked.

• Current value is false → CAS succeeds.

• Lock becomes true.

• Thread-1 enters the critical section.

Step 2: Thread-2 calls lock()

• compareAndSet(false, true) is checked.

• Current value is already true (Thread-1 holds the lock).

• CAS fails, so Thread-2 keeps looping inside the while loop until Thread1 set the value back to false.

Now that you already have a good grip on Compare-And-Swap (CAS) and how it's used for building locks (CompareAndSwapLock), the next logical step is to see how such primitives are leveraged to build lock-free data structures like a ConcurrentHashMap.

We won’t go into all the details (Java’s ConcurrentHashMap is extremely optimized with segmenting, bucketized locks, tree bins, etc.), but we can sketch a simplified version that demonstrates the principles.

ConcurrentHashMap in Java heavily relies on CAS (Compare-And-Swap) to avoid blocking threads with heavyweight locks wherever possible. Instead of always using synchronized or ReentrantLock, it tries to update data structures optimistically with CAS and falls back to locking only when strictly necessary.

Here’s where CAS comes into play in ConcurrentHashMap:

---

1. Inserting the first node in a bucket

When you do:

map.put(key, value);

If the bucket (array slot) is empty, ConcurrentHashMap tries:

if (tabAt(table, i) == null) {
    if (casTabAt(table, i, null, new Node<>(key, value))) {
        break; // success
    }
}

Here, it uses CAS to insert the new node. If two threads try to insert into the same bucket, only one wins. The loser retries.

package CompareAndSetHashMap;

import java.util.concurrent.atomic.AtomicReferenceArray;

public class MyConcurrentHashMap<K,V> {
    private final AtomicReferenceArray<Node<K,V>> map;
    private final int capacity;

    public MyConcurrentHashMap( int capacity) {
        this.capacity = capacity;
        this.map = new AtomicReferenceArray<>(capacity);
    }

    private int hash(K key) {
        return key.hashCode() % capacity;
    }

    public V get(K key) {
        int index = hash(key);
        Node<K,V> node = map.get(index);
        if(node != null && node.key.equals(key)){
            return node.value;
        }
        return null;
    }

    public void put(K key, V value) {
        System.out.println("Putting " + key + " -> " + value);
        int index = hash(key);
        Node<K, V> newNode = new Node<>(key, value);
        while(true){
            System.out.println("Running loop...");
            Node<K,V> existingNode = map.get(index);
            if(existingNode == null){
                System.out.println("No key insertion.");
                if(map.compareAndSet(index,null,newNode)){
                    return;
                }
            }
            else if(existingNode.key.equals(key)){
                System.out.println("Key insertion started.");
                if(map.compareAndSet(index,existingNode,newNode)){
                    System.out.println("Successfully inserted.");
                    return;
                }
                System.out.println("Key insertion failed trying again.");
            }
            else{
                // in case of collision override... (not a fair thing to do)
                System.out.println("Key insertion started.");
                if(map.compareAndSet(index,existingNode,newNode)){
                    System.out.println("Successfully inserted.");
                    return;
                }
                System.out.println("Key insertion failed trying again.");
            }
        }
    }

}

• Custom Concurrent Map Idea

  • This class is a simplified version of ConcurrentHashMap.

  • It uses Compare-And-Swap (CAS) through AtomicReferenceArray to achieve thread safety without explicit locks.

• Data Structure Used

  • AtomicReferenceArray<Node<K,V>> map → stores key-value pairs.

  • Each slot in the array is atomic, meaning updates are done safely across multiple threads.

• Constructor

  • Takes capacity → the size of the underlying array.

  • Initializes an AtomicReferenceArray with that capacity.

• Hash Function

  • hash(K key) → returns an index by taking key.hashCode() % capacity.

  • Decides where the key-value pair should go in the array.

• get(K key)

  • Finds the correct index using the hash.

  • Checks if the stored node at that index matches the key.

  • If yes → returns the value; if not → returns null.

• put(K key, V value)

  • Creates a new node with the given key and value.

  • Loops until the value is successfully inserted (CAS retry loop).

  • Three main cases:

    1. Empty slot (null) → tries CAS to insert new node.

    2. Key already exists → replaces the existing node atomically.

    3. Collision with different key → overwrites (not ideal, but kept simple).

• CAS Logic

  • compareAndSet(index, expected, newValue)

    • If the value at index is still expected, swap in newValue.

    • Otherwise, retry in a loop.

  • This avoids race conditions when multiple threads insert/update at the same time.

• Limitations

  • No proper collision handling (like chaining or probing).

  • Only one key per slot → overwrites if hash collision happens.

  • Simplified for learning purpose, not production use.

I hope that covers everything you need to know about CAS. 🙌
If you feel I missed something or got anything wrong, I’d genuinely love to hear from you—always down to learn and improve. 💡💬