Concurrent Hash Table Designs

Summary

The next milestone is to build a fully thread-safe hash map.Up to this point, the focus has been entirely on single-threaded performance: minimizing memory overhead, improving cache locality, and squeezing out every last bit of throughput from the underlying data layout. However, real-world applications rarely stay single-threaded. To be practically useful, a hash map must behave correctly—and efficiently—under concurrent access.Before jumping straight into implementation, it’s worth stepping back and studying how existing thread-safe hash map implementations approach this problem. Different designs make different trade-offs between simplicity, scalability, memory usage, and read/write performance. By examining these approaches side by side, we can better understand which ideas scale cleanly—and where the pitfalls are—when multiple threads hit the same structure at once.In this part, I’ll walk through the most common strategies used in real-world concurrent hash maps, and highlight the core trade-offs that shape their performance and complexity.1) Global Lock (the synchronized approach)#The most straightforward way to make a hash map thread-safe is to wrap the entire implementation with a single global lock, effectively placing the same synchronization barrier around every public operation.public V get(Object key) { synchronized (mutex) { ... } } public V put(K key, V value) { synchronized (mutex) { ... } } public V remove(Object key) { synchronized (mutex) { ... } } With this approach, all methods are forced to acquire the exact same lock before accessing the internal state of the map.This includes not only the obvious mutating operations such as put and remove, but also:get, containsKeyresize, rehashclear, sizeand essentially every other method that touches the internal data structuresFrom a correctness standpoint, this strategy is almost trivial to reason about. Thread safety is guaranteed entirely by the properties provided by the lock itself:Mutual exclusion en...