On Extending a Fixed Size, Persistent and Lock-Free Hash Map Design to Store Sorted Keys
Miguel Areias and Ricardo Rocha
December 2018
Abstract
Searching is a crucial time-consuming part of many programs, and using
a good search method instead of a bad one often leads to a substantial
increase in performance. Hash tries are a trie-based data structure
with nearly ideal characteristics for the implementation of hash
maps. In this paper, we present a novel, simple and concurrent hash
map design that fully supports the concurrent search, insert and
remove operations on hash tries designed to store sorted keys. To the
best of our knowledge, our design is the first concurrent hash map
design that puts together the following characteristics: (i) use fixed
size data structures; (ii) use persistent memory references; (iii) be
lock-free; and (iv) store sorted keys. Experimental results show that
our design is quite competitive when compared against other
state-of-the-art designs implemented in Java.
Bibtex
@InProceedings{areias-ispa18,
author = {M. Areias and R. Rocha},
title = {{On Extending a Fixed Size, Persistent and Lock-Free Hash Map Design to Store Sorted Keys}},
booktitle = {Proceedings of the 16th International Symposium on Parallel and Distributed Processing
with Applications (ISPA 2018)},
pages = {415--422},
publisher = {IEEE Computer Society},
editor = {M. Dong and R. Ranjan and M. Cafaro and W. Wang},
month = {December},
year = {2018},
address = {Melbourne, Australia},
}
Download Paper
PDF file
IEEE Computer Society