# A Dynamic Hash Table for the GPU

arXiv: https://arxiv.org/abs/1710.11246 · HTML: https://mlsanity.com/paper/1710.11246/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Oct 2017.

## Built on by (most cited first, 3 of 3)

- [ASH: A Modern Framework for Parallel Spatial Hashing in 3D Perception](https://mlsanity.com/paper/2110.00511/) (2021)
- [GPU Semiring Primitives for Sparse Neighborhood Methods](https://mlsanity.com/paper/2104.06357/) (2021)
- [Toward Robust and Efficient ML-Based GPU Caching for Modern Inference](https://mlsanity.com/paper/2509.20979/) (2025)

## Abstract (arXiv)

We design and implement a fully concurrent dynamic hash table for GPUs with comparable performance to the state of the art static hash tables. We propose a warp-cooperative work sharing strategy that reduces branch divergence and provides an efficient alternative to the traditional way of per-thread (or per-warp) work assignment and processing. By using this strategy, we build a dynamic non-blocking concurrent linked list, the slab list, that supports asynchronous, concurrent updates (insertions and deletions) as well as search queries. We use the slab list to implement a dynamic hash table with chaining (the slab hash). On an NVIDIA Tesla K40c GPU, the slab hash performs updates with up to 512 M updates/s and processes search queries with up to 937 M queries/s. We also design a warp-synchronous dynamic memory allocator, SlabAlloc, that suits the high performance needs of the slab hash. SlabAlloc dynamically allocates memory at a rate of 600 M allocations/s, which is up to 37x faster than alternative methods in similar scenarios.