Parallel Hash
Parallel Hash Tables are concurrent data structures that allow multiple threads to simultaneously insert, lookup, and delete key-value pairs with minimal contention — requiring careful design to avoid the serial bottleneck of a single global lock while maintaining correctness under concurrent access, with implementations ranging from simple lock-striping to sophisticated lock-free algorithms.
Concurrency Approaches
| Approach | Contention | Complexity | Throughput |
|---|---|---|---|
| Global Lock | Very High | Simple | Poor (serial) |
| Lock Striping | Medium | Medium | Good |
| Read-Write Lock | Medium (reads) | Medium | Good for read-heavy |
| Lock-Free (CAS) | Low | Very High | Excellent |
| Per-Bucket Lock | Low-Medium | Medium | Very Good |
Lock Striping (Java ConcurrentHashMap approach)
- Hash table divided into S segments (stripes), each with its own lock.
- Thread acquires only the lock for the target segment → others can proceed in parallel.
- With 16 stripes: Up to 16 threads can modify different segments simultaneously.
- Java ConcurrentHashMap (Java 8+): Actually uses per-bucket CAS + synchronized blocks.
Lock-Free Hash Tables
- Use Compare-And-Swap (CAS) atomic operations — no locks at all.
- Insert: CAS to atomically place entry in bucket. If CAS fails (another thread modified) → retry.
- Resize: Most complex operation — must atomically migrate entries from old to new table.
- Split-Ordered Lists (Shalev & Shavit): Hash table where resize doesn't move elements — elements stay in a single sorted lock-free linked list, buckets are just entry points into the list.
Cuckoo Hashing (Concurrent)
- Two hash functions h1, h2 — each key has exactly 2 possible locations.
- Lookup: Check locations h1(key) and h2(key) — always O(1).
- Insert: If both locations occupied → "cuckoo" displaces one → displaced key moves to its alternate location.
- Concurrent variant: Lock-free lookups, fine-grained locks for inserts.
- Used in: Network switches (exact-match forwarding tables), GPU hash tables.
GPU Parallel Hash Tables
- Thousands of threads inserting simultaneously → need massive parallelism.
- Open addressing (linear/quadratic probing) preferred on GPUs — better memory coalescing than chaining.
- Use atomicCAS for insertion: `atomicCAS(&table[slot], EMPTY, key)`.
- cuCollections (NVIDIA): CUDA-optimized concurrent hash maps.
Performance Characteristics
| Operation | Lock-Striped | Lock-Free | GPU Hash |
|---|---|---|---|
| Insert | O(1) amortized | O(1) amortized | O(1) expected |
| Lookup | O(1) | O(1), wait-free | O(1) coalesced |
| Delete | O(1) | O(1) or lazy | O(1) tombstone |
| Resize | Lock all stripes | Incremental | Rebuild |
Parallel hash tables are a fundamental building block of concurrent systems — from database indexing and network packet processing to GPU-accelerated analytics, the ability to perform millions of concurrent key-value operations per second is essential for modern parallel applications.