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.