Back to Search
Start Over
Concurrent hash tables
- Source :
- PPOPP
- Publication Year :
- 2016
- Publisher :
- ACM, 2016.
-
Abstract
- Concurrent hash tables are one of the most important concurrent data structures with numerous applications. Since hash table accesses can dominate the execution time of the overall application, we need implementations that achieve good speedup. Unfortunately, currently available concurrent hashing libraries turn out to be far away from this requirement in particular when contention on some elements occurs.Our starting point for better performing data structures is a fast and simple lock-free concurrent hash table based on linear probing that is limited to word-sized key-value types and does not support dynamic size adaptation. We explain how to lift these limitations in a provably scalable way and demonstrate that dynamic growing has a performance overhead comparable to the same generalization in sequential hash tables.We perform extensive experiments comparing the performance of our implementations with six of the most widely used concurrent hash tables. Ours are considerably faster than the best algorithms with similar restrictions and an order of magnitude faster than the best more general tables. In some extreme cases, the difference even approaches four orders of magnitude.
- Subjects :
- Primary clustering
Theoretical computer science
Computer science
Universal hashing
Linear probing
Dynamic perfect hashing
Hash function
02 engineering and technology
Parallel computing
Linear hashing
Hash table
020202 computer hardware & architecture
K-independent hashing
Hopscotch hashing
Hash tree
Open addressing
SHA-2
0202 electrical engineering, electronic engineering, information engineering
Cryptographic hash function
020201 artificial intelligence & image processing
Consistent hashing
Perfect hash function
Double hashing
Subjects
Details
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
- Accession number :
- edsair.doi...........af8ae22a8abc3b7d6e63f0e3ff2b550a