Hashing without bucket locks
A lock free hash map lets many threads insert, find, and remove concurrently with no per bucket mutex. Each bucket points into a shared lock free linked list, and the bucket array holds atomic pointers updated by CAS.
The resize problem
The hardest part is growing the table. A naive design must move every key when load rises, and doing that atomically while others read is brutal. The classic solution is the split ordered list by Shalev and Shavit.
- All keys live in one sorted lock free list, ordered by the bit reversed value of their hash.
- Bucket pointers are shortcuts into this single list.
- Doubling the table just adds new bucket pointers between existing nodes.
Because the underlying list never has to be rebuilt, resizing only initializes new buckets lazily, never moving data.
Operations
Insert and delete reduce to inserting or marking nodes in the underlying lock free sorted list using CAS, with logically deleted nodes marked before being physically unlinked.
Key idea
A lock free hash map keeps keys in one bit reversed sorted lock free list with bucket pointers as shortcuts, so the table can double without ever relocating existing entries.