Get the latest tech news

Designing a Fast Concurrent Hash Table

I recently released papaya, a fast and feature-complete concurrent hash table for Rust. In this post I want to dive into the design and research that went into creating it, as well as why you might consider using it over existing solutions.

While there are many interesting strategies such as cuckoo, robin-hood, or hopscotch hashing, these are expensive to implementing concurrently requiring extra synchronization, especially with a metadata table. I'd be interested in a formalization of probe limits and their relationship to load factor, but this number seems to work very consistently in practice, and avoids the need to synchronize a concurrent counter. This limitation is common in academic literature, and leapfrog falls back to spinlocks for arbitrary value types, which is unfortunate for a general purpose map.

Get the Android app