Dynamic-sized nonblocking hash tables

This paper presents nonblocking hash table algorithms that support resizing in both directions: shrinking and growing. The heart of the table is a freezable set abstraction, which greatly simplifies the task of moving elements among buckets during a resize. Furthermore, the freezable set abstraction makes possible the use of highly opti-mized implementations of individual buckets, including implemen-tations in which a single flat array is used for each bucket, which improves cache locality. We present lock-free and wait-free variants of our hash table, to include fast adaptive wait-free variants based on the Fastpath/Slow-path methodology. In evaluation on SPARC and x86 architectures, we find that performance of our lock-free implementation is consis-tently better than the current state-of-the-art split-ordered list, and that performance for the adaptive wait-free algorithm is compelling across microbenchmark configurations