Concurrent collections question 67 of 180 senior
How does ConcurrentHashMap work since Java 8?
- It uses 16 segments, each with its own lock
- Correct: It locks the head node of a single bin with
synchronized, uses CAS for empty bins, and turns a long collision chain into a red-black tree - It copies the whole table on every write
- It is backed by a
ConcurrentSkipListMap
Java 7 used segments: a fixed array of sub-maps, each with its own lock, giving 16 writers in parallel by default. Java 8 dropped that. Writes CAS an empty bin directly; if the bin is occupied, the writer synchronizes on the head node, so the lock granularity is one bucket rather than one sixteenth of the table.
Two more pieces worth naming. A bin whose chain exceeds 8 entries, in a table of at least 64, becomes a red-black tree, so a hash collision attack degrades to O(log n) rather than O(n). And resizing is cooperative: a thread that finds a resize in progress helps transfer bins instead of blocking.
size() is not a counter under a lock. It sums a LongAdder-style set of striped cells, so it is
accurate only when nobody is writing.
Quiz yourself on Concurrent collections Suggest a correction