parallel hash table

**Parallel and Concurrent Hash Tables** are the **data structures that enable multiple threads to simultaneously insert, lookup, and delete key-value pairs with O(1) average-case time per operation — where the concurrent access patterns (multiple threads hitting the same bucket) require careful synchronization strategies ranging from fine-grained locking to lock-free CAS operations to GPU-optimized open-addressing schemes, making concurrent hash tables one of the most performance-critical data structures in parallel computing**. **Why Concurrent Hash Tables Are Hard** A sequential hash table achieves O(1) operations trivially. When multiple threads access it concurrently: inserts can race on the same bucket (data corruption), resizes require atomically replacing the entire table while other threads are reading, and high contention on popular buckets serializes access. The goal is to maximize throughput while guaranteeing correctness. **CPU Concurrent Hash Tables** - **Striped Locking**: Divide buckets into K lock groups. Each lock protects N/K buckets. Threads accessing different lock groups proceed in parallel. Granularity trade-off: more locks = more parallelism but more memory overhead. - **Lock-Free (CAS-Based)**: Each bucket is a CAS-modifiable pointer to a chain of entries. Insert: allocate entry, CAS the bucket head pointer from old_head to new_entry (with new_entry->next = old_head). Retry on CAS failure. No locks, no deadlocks. Memory reclamation (hazard pointers, epoch-based) is the hard part. - **Robin Hood Hashing**: Open-addressing with displacement — entries with longer probe sequences displace entries with shorter sequences. Excellent cache performance. Concurrent version uses per-slot locks or CAS on slot metadata. - **Concurrent Cuckoo Hashing**: Two hash functions, two tables. Each key can be in one of two positions. Insert displaces existing entries in a chain of moves. Lock-free cuckoo hashing uses CAS on each slot. Maximum load factor ~95% with fast lookups (always ≤2 probes). **GPU Hash Tables** GPU hash tables face unique challenges: millions of simultaneous threads, no per-thread stack for linked list recursion, and global memory atomics are slow under contention. - **Open Addressing**: Linear probing with CAS on each slot. Empty sentinel indicates available slots. Load factor limited to 70-80% to keep probe lengths manageable. - **Cuckoo Hashing on GPU**: Two hash tables in global memory. Each lookup checks exactly 2 positions — perfectly deterministic memory access count, ideal for GPU's SIMT execution. Insertion uses CAS with eviction chains. - **Warp-Cooperative**: Each warp (32 threads) cooperates on a single lookup/insert. Thread 0 hashes, all 32 threads probe 32 candidate slots in parallel, any thread finding the key reports to the warp via __ballot_sync. 32x probe throughput. **Performance Characteristics** CPU concurrent hash tables achieve 100-500 million operations/second on modern 32-core systems. GPU hash tables achieve 1-5 billion operations/second on high-end GPUs. The bottleneck is almost always memory latency, not computation. Parallel Hash Tables are **the concurrent data structure workhorse** — providing the constant-time key-value access that databases, caches, deduplication engines, and graph algorithms depend on, scaled to billions of operations per second through careful lock-free and hardware-aware design.