parallel hash table
**Parallel Hash Tables** are the **concurrent data structures that enable multiple threads to perform insert, lookup, and delete operations simultaneously on a shared key-value store — where the design must balance throughput (millions of operations per second), correctness (linearizable or sequentially consistent behavior), and scalability (performance improving with core count rather than degrading due to contention)**.
**Why Parallel Hash Tables Are Hard**
A sequential hash table is trivial: hash the key, index into the bucket array, handle collisions. But when multiple threads operate concurrently, every access to a bucket is a potential data race. Naive locking (one mutex per table) serializes all operations. Fine-grained locking (per-bucket) improves concurrency but adds overhead and complexity. Lock-free designs eliminate locks entirely but require careful atomic operations and memory ordering.
**Concurrent Hash Table Designs**
- **Striped Locking**: Partition buckets into N stripes, each protected by an independent lock. Operations on different stripes proceed in parallel. Typical stripe count: 16-256. Java's ConcurrentHashMap (pre-Java 8) used this approach.
- **Lock-Free with CAS**: Open-addressing (linear probing or Robin Hood hashing) with atomic compare-and-swap for insertion. Each slot stores a key-value pair atomically (128-bit CAS for 64-bit key + 64-bit value). Lookup: probe sequentially from hash position, compare keys atomically. Insert: CAS empty slot with new key-value. No locks, no deadlocks.
- **Read-Copy-Update (RCU)**: Optimized for read-heavy workloads. Readers access the hash table without any synchronization (no locks, no atomics). Writers create a modified copy of the affected bucket and atomically swap the pointer. Old version is garbage-collected after all readers have finished (grace period). Used in the Linux kernel.
- **Cuckoo Hashing**: Each key has two possible positions (from two hash functions). Insertion displaces existing keys to their alternative position (cuckoo eviction). Concurrent cuckoo hashing uses fine-grained locks on buckets with hazard-pointer-based garbage collection. Provides O(1) worst-case lookup.
**GPU Hash Tables**
GPU hash tables exploit massive parallelism but face unique constraints:
- **Open Addressing Only**: Pointer-chasing (chained hashing) causes severe warp divergence and poor memory coalescing. Linear probing with power-of-2 table sizes enables coalesced memory access.
- **Atomic Insert**: atomicCAS on 64-bit or 128-bit slots. GPU atomics on global memory have high latency (~100 cycles) but throughput scales with the number of warps.
- **Warp-Cooperative Probing**: A full warp cooperatively probes the table — each thread checks a different slot, and warp-level ballot/vote determines if the key was found. 32x improvement in probe throughput.
**Performance Characteristics**
| Design | Read Throughput | Write Throughput | Memory Overhead |
|--------|----------------|-----------------|----------------|
| Striped locks | Good (parallel reads) | Moderate (lock contention) | Low |
| Lock-free open addressing | Excellent | Good | Moderate (load factor) |
| RCU | Excellent (zero overhead reads) | Low (copy cost) | High (old copies) |
| GPU warp-cooperative | Very high (billions ops/s) | Very high | Moderate |
**Parallel Hash Tables are the essential concurrent building block** — providing O(1) expected-time key-value access for multi-threaded and GPU-accelerated applications where sequential hash tables would become a serialization bottleneck.