publication . Conference object . 2018

An Efficient Wait-free Resizable Hash Table

Panagiota Fatourou; Nikolaos D. Kallimanis; Thomas Ropars;

English

Published: 16 Jul 2018

Publisher: ACM Press

Summary

Abstract

This paper presents an efficient wait-free resizable hash table. To achieve high throughput at large core counts, our algorithm is specifically designed to retain the natural parallelism of concurrent hashing, while providing wait-free resizing. An extensive evaluation of our hash table shows that in the common case where resizing actions are rare, our implementation outperforms all existing lock-free hash table implementations while providing a stronger progress guarantee.

doi: 10.1145/3210377.3210408

Subjects

free text keywords: [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Hash table, Resizing, Hash function, Concurrent data structure, Parallel computing, Throughput, Computer science, Multi-core processor, Implementation

Related Organizations