Java ConcurrentHashMap: Thread-Safe Maps

import java.util.*;
import java.util.concurrent.*;

// Problem: HashMap under concurrent access — data corruption
Map<String, Integer> unsafeMap = new HashMap<>();

// Multiple threads writing simultaneously → lost updates, corrupted state
ExecutorService pool = Executors.newFixedThreadPool(4);
for (int t = 0; t < 4; t++) {
    pool.submit(() -> {
        for (int i = 0; i < 10_000; i++) {
            unsafeMap.put("key-" + i, i); // UNSAFE: no synchronization
        }
    });
}
pool.shutdown();
pool.awaitTermination(10, TimeUnit.SECONDS);
// unsafeMap.size() is unpredictable — may be less than 10,000

// "Fix" 1: synchronizedMap — works but serializes ALL access
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// Every get(), put(), size() acquires the SAME intrinsic lock
// Throughput collapses under high concurrency

// "Fix" 2: Hashtable — same problem, different API
Hashtable<String, Integer> hashtable = new Hashtable<>();
// Every method is synchronized on 'this' — one thread at a time

// Solution: ConcurrentHashMap — fine-grained locking, lock-free reads
ConcurrentHashMap<String, Integer> concMap = new ConcurrentHashMap<>();
// Multiple threads can read AND write simultaneously with high throughput
ExecutorService pool2 = Executors.newFixedThreadPool(4);
for (int t = 0; t < 4; t++) {
    pool2.submit(() -> {
        for (int i = 0; i < 10_000; i++) {
            concMap.put("key-" + i, i); // SAFE: internally synchronized per bin
        }
    });
}
pool2.shutdown();
pool2.awaitTermination(10, TimeUnit.SECONDS);
System.out.println(concMap.size()); // exactly 10,000

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// --- Basic put / get / remove ---
map.put("alpha", 1);
map.put("beta", 2);
map.put("gamma", 3);

int val = map.get("alpha");       // 1
boolean has = map.containsKey("beta"); // true
map.remove("gamma");              // removes entry

// --- Atomic conditional operations from ConcurrentMap ---

// putIfAbsent: insert only if key is not already mapped
Integer prev = map.putIfAbsent("alpha", 99);
System.out.println(prev);        // 1 — key existed, value unchanged
System.out.println(map.get("alpha")); // 1

map.putIfAbsent("delta", 4);     // inserted — key was absent
System.out.println(map.get("delta")); // 4

// remove(key, value): remove only if key maps to exact value
boolean removed = map.remove("alpha", 999); // false — value doesn't match
System.out.println(map.get("alpha"));       // 1 — still present

removed = map.remove("alpha", 1);           // true — exact match
System.out.println(map.get("alpha"));       // null

// replace(key, value): replace only if key is present
map.put("beta", 2);
Integer old = map.replace("beta", 20);      // 2 — previous value
System.out.println(map.get("beta"));        // 20

// replace(key, oldValue, newValue): CAS-style conditional replace
boolean swapped = map.replace("beta", 20, 200); // true
System.out.println(map.get("beta"));             // 200

swapped = map.replace("beta", 20, 999);         // false — current is 200, not 20
System.out.println(map.get("beta"));             // 200 — unchanged

// getOrDefault: avoid null checks
int result = map.getOrDefault("missing", -1);    // -1

// Conceptual model of pre-Java 8 ConcurrentHashMap (simplified)
// The table is split into Segments, each with its own lock

// Segment[] segments = new Segment[16];  // default concurrencyLevel = 16
//
// put(key, value):
//   1. hash = spread(key.hashCode())
//   2. segmentIndex = (hash >>> 28) & (segments.length - 1)
//   3. segments[segmentIndex].lock()     // lock only this segment
//   4. insert into segment's internal HashEntry[] table
//   5. segments[segmentIndex].unlock()
//
// get(key):
//   No locking at all — uses volatile reads on HashEntry.value
//   Relies on the Java Memory Model: a volatile read of the value
//   sees all writes that happened before the volatile write
//
// Limitations:
// - Fixed segment count at construction time (concurrencyLevel)
// - Memory overhead from Segment objects
// - Long chains in bins degrade to O(n) lookup

// Java 8+ ConcurrentHashMap internal structure (simplified)
//
// Node<K,V>[] table;  // the main hash table (power-of-two length)
//
// Each slot (bin) holds one of:
//   null         — empty bin
//   Node         — linked list (hash >= 0)
//   TreeBin      — red-black tree wrapper (hash == -2)
//   ForwardingNode — resize in progress (hash == -1)
//
// put(key, value) algorithm:
//   1. hash = spread(key.hashCode())  // ensures top bits mix into lower bits
//   2. index = hash & (table.length - 1)
//   3. If table[index] is null:
//        CAS table[index] = new Node(hash, key, value)  // lock-free!
//   4. If table[index] is ForwardingNode:
//        help with ongoing resize, then retry
//   5. Otherwise:
//        synchronized (headNode) {
//            traverse chain/tree, insert or update
//            if chain length >= TREEIFY_THRESHOLD (8):
//                convert to TreeBin
//        }
//   6. addCount() — increment size, check if resize needed
//
// get(key) algorithm:
//   Entirely lock-free — uses volatile reads of Node.val and Node.next
//   No synchronization, no CAS — just a volatile read chain

// Key constants
// TREEIFY_THRESHOLD = 8   — chain converts to tree at this length
// UNTREEIFY_THRESHOLD = 6 — tree converts back to list during resize
// MIN_TREEIFY_CAPACITY = 64 — table must be at least this size to treeify
// DEFAULT_CAPACITY = 16
// LOAD_FACTOR = 0.75f     — fixed in Java 8+, constructor param is ignored

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.LongAdder;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// --- computeIfAbsent: insert computed value only if key is absent ---
// The mapping function is called at most once, atomically
// Perfect for lazy initialization / caching

map.computeIfAbsent("count", key -> {
    System.out.println("Computing value for: " + key);
    return 0;  // only called if "count" is not in the map
});
System.out.println(map.get("count")); // 0

map.computeIfAbsent("count", key -> 999); // NOT called — key already exists
System.out.println(map.get("count"));      // 0 — unchanged

// --- computeIfPresent: update only if key exists ---
// Returning null removes the entry

map.computeIfPresent("count", (key, val) -> val + 1);
System.out.println(map.get("count")); // 1

map.computeIfPresent("count", (key, val) -> val + 1);
System.out.println(map.get("count")); // 2

// Remove by returning null
map.computeIfPresent("count", (key, val) -> val < 5 ? null : val);
System.out.println(map.get("count")); // null — entry removed because 2 < 5

// --- compute: always runs the function, handles both absent and present ---
// If key is absent, oldValue is null. Returning null removes entry.

map.compute("visits", (key, oldVal) -> oldVal == null ? 1 : oldVal + 1);
System.out.println(map.get("visits")); // 1

map.compute("visits", (key, oldVal) -> oldVal == null ? 1 : oldVal + 1);
System.out.println(map.get("visits")); // 2

// --- merge: combine new value with existing value ---
// If key is absent, inserts the value directly
// If key is present, applies the remapping function

map.merge("visits", 10, Integer::sum);
System.out.println(map.get("visits")); // 12 (2 + 10)

map.merge("newKey", 5, Integer::sum);
System.out.println(map.get("newKey")); // 5 — no existing value, inserted directly

// merge is excellent for atomic counters
ConcurrentHashMap<String, Long> counters = new ConcurrentHashMap<>();
counters.merge("pageViews", 1L, Long::sum); // 1
counters.merge("pageViews", 1L, Long::sum); // 2
counters.merge("pageViews", 1L, Long::sum); // 3
System.out.println(counters.get("pageViews")); // 3

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> scores = new ConcurrentHashMap<>();
scores.put("Alice", 92);
scores.put("Bob", 85);
scores.put("Carol", 97);
scores.put("Dave", 73);
scores.put("Eve", 88);

// --- forEach with parallelism ---
// parallelismThreshold = 1 → always parallel
scores.forEach(1, (name, score) ->
    System.out.println(name + " → " + score)
);

// forEach with transformer — apply a function before the action
scores.forEach(1,
    (name, score) -> name + ": " + (score >= 90 ? "A" : "B"), // transformer
    System.out::println  // action on transformed value
);
// Output: Alice: A, Carol: A, Bob: B, Dave: B, Eve: B (order varies)

// --- search: find the first match (returns null if none) ---
// Stops early when a non-null result is found
String topStudent = scores.search(1, (name, score) ->
    score >= 95 ? name : null  // return non-null to signal "found"
);
System.out.println("Top student: " + topStudent); // Carol

// searchValues — search only values
Integer highScore = scores.searchValues(1, score ->
    score > 90 ? score : null
);
System.out.println("A high score: " + highScore); // 92 or 97

// --- reduce: aggregate all entries ---
// Sum all scores
int totalScore = scores.reduce(1,
    (name, score) -> score,  // transformer: extract the value
    Integer::sum              // reducer: combine two results
);
System.out.println("Total: " + totalScore); // 435

// reduceValues — reduce values directly
int maxScore = scores.reduceValues(1, Integer::max);
System.out.println("Max score: " + maxScore); // 97

// reduceValuesToInt — avoid boxing for primitive reductions
int sumScores = scores.reduceValuesToInt(1, Integer::intValue, 0, Integer::sum);
System.out.println("Sum: " + sumScores); // 435

// reduceKeys — reduce keys
String allNames = scores.reduceKeys(1, (a, b) -> a + ", " + b);
System.out.println("All: " + allNames); // Alice, Bob, Carol, Dave, Eve (order varies)

// --- Parallelism threshold guidance ---
// 1              → always parallel (use ForkJoinPool.commonPool)
// Long.MAX_VALUE → always sequential (no fork/join overhead)
// n              → parallel only when map.size() > n

import java.util.concurrent.*;

// Counting word frequencies across multiple threads
ConcurrentHashMap<String, Long> wordCounts = new ConcurrentHashMap<>();

String[] documents = {
    "the quick brown fox jumps over the lazy dog",
    "the dog barked at the fox",
    "quick quick fox"
};

ExecutorService pool = Executors.newFixedThreadPool(3);
for (String doc : documents) {
    pool.submit(() -> {
        for (String word : doc.split("\\s+")) {
            // merge is atomic — no lost updates
            wordCounts.merge(word, 1L, Long::sum);
        }
    });
}
pool.shutdown();
pool.awaitTermination(5, TimeUnit.SECONDS);

wordCounts.forEach((word, count) ->
    System.out.println(word + " → " + count)
);
// the → 4, fox → 3, quick → 3, dog → 2, ...

import java.util.concurrent.ConcurrentHashMap;

// Lazy-initialized, thread-safe cache
// Only ONE thread computes the value; others wait and reuse the result
ConcurrentHashMap<String, byte[]> cache = new ConcurrentHashMap<>();

byte[] getData(String key) {
    return cache.computeIfAbsent(key, k -> {
        System.out.println("Loading " + k + " from database...");
        // Simulate expensive operation
        return fetchFromDatabase(k);
    });
}

// Thread 1 calls getData("user:42") → computes and caches
// Thread 2 calls getData("user:42") → gets cached value immediately
// Thread 3 calls getData("user:99") → computes for different key (no blocking)

// Cache with expiration — store wrapper objects
record CacheEntry<V>(V value, long expiresAt) {
    boolean isExpired() { return System.currentTimeMillis() > expiresAt; }
}

ConcurrentHashMap<String, CacheEntry<String>> timedCache = new ConcurrentHashMap<>();

String getCached(String key, long ttlMillis) {
    timedCache.compute(key, (k, existing) -> {
        if (existing != null && !existing.isExpired()) {
            return existing; // still valid
        }
        // Expired or missing — recompute
        String freshValue = fetchFromDatabase(k).toString();
        return new CacheEntry<>(freshValue, System.currentTimeMillis() + ttlMillis);
    });
    CacheEntry<String> entry = timedCache.get(key);
    return entry != null ? entry.value() : null;
}

import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

// ConcurrentHashMap.newKeySet() — a concurrent Set backed by a CHM
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();

concurrentSet.add("alpha");
concurrentSet.add("beta");
concurrentSet.add("gamma");

// Thread-safe iteration, add, remove
concurrentSet.remove("beta");
System.out.println(concurrentSet.contains("alpha")); // true

// Alternatively, from an existing map:
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("x", 1);
map.put("y", 2);
Set<String> keySet = map.keySet(0); // default value for new entries added via Set.add()
keySet.add("z"); // adds "z" → 0 to the underlying map
System.out.println(map.get("z")); // 0

import java.util.concurrent.ConcurrentHashMap;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

// Accumulate values per key — e.g., grouping events by category
ConcurrentHashMap<String, List<String>> eventsByCategory = new ConcurrentHashMap<>();

void recordEvent(String category, String event) {
    // computeIfAbsent + add is safe because:
    // 1. computeIfAbsent atomically creates the list if absent
    // 2. CopyOnWriteArrayList.add is thread-safe
    eventsByCategory
        .computeIfAbsent(category, k -> new CopyOnWriteArrayList<>())
        .add(event);
}

recordEvent("login", "user:alice logged in");
recordEvent("login", "user:bob logged in");
recordEvent("error", "NullPointerException in PaymentService");

System.out.println(eventsByCategory.get("login").size()); // 2

import java.util.concurrent.ConcurrentHashMap;

// Constructor: ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)

// initialCapacity — pre-sizes the internal table to avoid early resizing
// If you know you'll store ~1000 entries, set it slightly above:
ConcurrentHashMap<String, Object> sized = new ConcurrentHashMap<>(1024);

// loadFactor — controls when the table resizes (default 0.75)
// In Java 8+, this is used ONLY for initial sizing — the actual resize
// threshold is always 0.75 * capacity internally.

// concurrencyLevel — in Java 8+, this is ONLY used to determine
// initial capacity. It no longer controls the number of segments/locks.
// Setting it to your expected thread count just helps initial sizing:
ConcurrentHashMap<String, Object> tuned = new ConcurrentHashMap<>(
    256,   // initialCapacity
    0.75f, // loadFactor (effectively ignored post-construction)
    64     // concurrencyLevel (used only for initial sizing)
);

// Performance tips:
// 1. Avoid unnecessary size() / isEmpty() calls — they require full traversal
//    and aggregation of per-segment counters (uses LongAdder internally)
long count = tuned.mappingCount(); // preferred over size() for large maps
// mappingCount() returns long (avoids int overflow for very large maps)

// 2. Use getOrDefault() instead of containsKey() + get()
// BAD: two lookups
if (sized.containsKey("x")) {
    Object v = sized.get("x"); // key might be removed between calls!
}
// GOOD: single atomic lookup
Object v = sized.getOrDefault("x", defaultValue);

// 3. Prefer merge/compute over get-then-put
// BAD: race condition between get and put
Integer old = sized.get("counter");
sized.put("counter", old == null ? 1 : (Integer) old + 1); // UNSAFE!
// GOOD: atomic
sized.merge("counter", 1, (a, b) -> (Integer) a + (Integer) b);

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// WRONG: check-then-act is NOT atomic — race condition!
if (!map.containsKey("counter")) {       // Thread A checks: absent
    map.put("counter", 1);               // Thread B also checks: absent
}                                         // Both threads insert — one update lost

// CORRECT: use putIfAbsent or computeIfAbsent
map.putIfAbsent("counter", 1);           // atomic check + insert

// WRONG: read-modify-write without atomicity
Integer current = map.get("counter");     // Thread A reads 5
map.put("counter", current + 1);          // Thread B also reads 5
                                          // Both write 6 — one increment lost!

// CORRECT: use atomic compute
map.compute("counter", (k, v) -> v == null ? 1 : v + 1);
// or
map.merge("counter", 1, Integer::sum);

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();

// Both of these throw NullPointerException:
// map.put(null, "value");    // NPE — null key
// map.put("key", null);      // NPE — null value

// Why? Ambiguity: map.get(key) returning null could mean:
//   (a) the key is mapped to null, or
//   (b) the key is not in the map
// In a concurrent context there is no safe way to distinguish these,
// so ConcurrentHashMap disallows null entirely.

// Use a sentinel value if you need to represent "absent" or "no value"
String EMPTY = "";
map.put("key", EMPTY); // use empty string as sentinel

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);

// Iterators do NOT throw ConcurrentModificationException
// They reflect the state at some point during or since creation
// Modifications during iteration MAY or MAY NOT be visible

for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
    // Another thread could add/remove entries right now
    // This iterator won't throw, but may or may not see those changes
}

// This is SAFE — won't throw, won't corrupt
// But the result is "weakly consistent" — not a point-in-time snapshot
// If you need a true snapshot, copy the map:
var snapshot = new java.util.HashMap<>(map); // copies current state

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// DANGEROUS: modifying the SAME map inside a compute function can deadlock
// if the two keys hash to the same bin, or cause unexpected behavior
map.computeIfAbsent("a", key -> {
    // DO NOT DO THIS — may deadlock or throw IllegalStateException
    // map.computeIfAbsent("b", k -> 2);  // recursive map modification!
    return 1;
});

// In Java 9+, recursive computeIfAbsent on the SAME key is detected
// and throws IllegalStateException to prevent infinite recursion

// SAFE alternative: compute the value outside the lambda
int valueForB = expensiveComputation();
map.putIfAbsent("b", valueForB);
map.computeIfAbsent("a", key -> 1);

import java.util.concurrent.ConcurrentHashMap;

ConcurrentHashMap<Long, Boolean> bigMap = new ConcurrentHashMap<>();

// size() returns int — overflows if map has > Integer.MAX_VALUE entries
int size = bigMap.size();             // may overflow!

// Use mappingCount() for large maps — returns long
long count = bigMap.mappingCount();   // safe for very large maps

// Also note: both are estimates in a concurrent context
// The count may change between the call returning and you using the value