parallel hash table
**Parallel Hash Tables** are the **concurrent data structures that allow multiple threads to simultaneously insert, lookup, and delete key-value pairs with high throughput and low contention** — requiring careful design of hash functions, collision resolution, and synchronization mechanisms to avoid the serialization bottleneck of lock-based approaches, with implementations spanning CPU lock-free designs, GPU-optimized cuckoo hashing, and distributed hash tables that scale to billions of entries across multiple machines.
**Why Parallel Hash Tables Are Hard**
- Sequential hash table: O(1) average insert/lookup → extremely efficient.
- Naive parallel: Lock the entire table → only one thread operates at a time → no speedup.
- Fine-grained locking: Lock per bucket → better but lock overhead + contention on hot buckets.
- Lock-free: Use atomic CAS (Compare-and-Swap) → best throughput but complex implementation.
**Concurrent Hash Table Approaches**
| Approach | Mechanism | Throughput | Complexity |
|----------|-----------|-----------|------------|
| Global lock | Single mutex | Very low | Trivial |
| Striped locks | Lock per bucket group | Medium | Low |
| Read-write lock | RWLock per stripe | Good for read-heavy | Medium |
| Lock-free (CAS) | Atomic operations | High | High |
| Cuckoo hashing | Two hash functions, constant lookup | Very high | High |
| Robin Hood | Linear probing with displacement | Good | Medium |
**Lock-Free Insert (Linear Probing)**
```c
bool insert(HashTable *ht, uint64_t key, uint64_t value) {
uint64_t slot = hash(key) % ht->capacity;
while (true) {
uint64_t existing = __atomic_load(&ht->keys[slot]);
if (existing == EMPTY) {
// CAS: atomically try to claim slot
if (__atomic_compare_exchange(&ht->keys[slot],
&existing, key)) {
__atomic_store(&ht->vals[slot], value);
return true; // Inserted
}
}
if (existing == key) return false; // Duplicate
slot = (slot + 1) % ht->capacity; // Probe next
}
}
```
**GPU Hash Tables**
- GPU has thousands of threads → extreme parallelism → needs specialized design.
- **Challenges**: No per-thread locks (too expensive), shared memory limited, warp-level coordination.
- **GPU Cuckoo Hashing**:
- Two hash functions h₁, h₂. Each key has exactly 2 possible locations.
- Insert: Try h₁, if occupied → evict to h₂ of displaced key → chain continues.
- Lookup: Check only 2 locations → constant time, cache-friendly.
- GPU-friendly: Fixed number of memory accesses → predictable performance.
**cuDPP / SlabHash (GPU)**
```cuda
// Build hash table on GPU (millions of inserts in parallel)
gpu_hash_table_build(keys, values, num_entries, table);
// Parallel lookup
gpu_hash_table_lookup(query_keys, num_queries, table, results);
// Throughput: 500M+ inserts/sec on modern GPU
```
**Distributed Hash Tables (DHT)**
- Keys distributed across nodes: node = hash(key) % num_nodes.
- Each node holds a local hash table for its key range.
- Consistent hashing: Minimize redistribution when nodes join/leave.
- Examples: Redis Cluster, Memcached, Amazon DynamoDB (underlying).
**Performance Benchmarks**
| Implementation | Platform | Throughput |
|---------------|----------|------------|
| std::unordered_map (single thread) | CPU | ~30M ops/s |
| tbb::concurrent_hash_map | CPU (32 cores) | ~200M ops/s |
| Lock-free linear probing | CPU (32 cores) | ~600M ops/s |
| GPU cuckoo hash | GPU (A100) | ~2000M ops/s |
Parallel hash tables are **the fundamental building block for high-throughput concurrent data access** — from database query engines to GPU-accelerated graph analytics to distributed caching systems, the ability to perform billions of key-value operations per second across many threads is essential for any system that must maintain fast random access to large datasets under heavy concurrent load.