On the Correctness of a Lock-Free Compression-based Elastic Mechanism for a Hash Trie Design
Miguel Areias and Ricardo Rocha
2022
Abstract
A key aspect of any hash map design is the problem of dynamically
resizing it in order to deal with hash collisions. Compression in
tree-based hash maps is the ability of reducing the depth of the
internal hash levels that support the hash map. In this context,
elasticity refers to the ability of automatically resizing the
internal data structures that support the hash map operations in order
to meet varying workloads, thus optimizing the overall memory
consumption of the hash map. This work extends a previous lock-free
hash trie map design to support elastic hashing, i.e., expand
saturated hash levels and compress unused hash levels, such that, at
each point in time, the number of levels in a path is adjusted, as
closely as possible, to the set of keys that is stored in the data
structure. To materialize our design, we introduce a new compress
operation for hash levels, which requires redesigning the existing
search, insert, remove and expand operations in order to maintain the
lock-freedom property of the data structure. Experimental results show
that elasticity effectively improves the search operation and, in
doing so, our design becomes very competitive when compared to other
state-of-the-art designs implemented in Java.
Bibtex
@Article{areias-computing22,
author = {M. Areias and R. Rocha},
title = {{On the Correctness of a Lock-Free Compression-based Elastic Mechanism for a Hash Trie Design}},
journal = {Computing},
pages = {1--27},
year = {2022},
}
Download Paper
PDF file
Springer