A Lock-Free Hash Table
Here’s a Google Tech Talk of Cliff Click discussing a Java hash table implementation that supports concurrent access using compare-and-swap rather than locking:
I present a lock-free concurrent Hash Table implementation with better single-thread performance than most Hash Tables, and better multi-thread performance than all other implementations I tried. I demonstrate scaling up to 768 CPUs even with high mutation rates. I show correctness by looking at the problem in a very different light than the usual “happens-before” / memory-order / fencing style of thinking.
