TY - JOUR
AU - Brehm, Wolfgang
PY - 2019
TI - Hash Tables with Pseudorandom Global Order
JF - INFOCOMP Journal of Computer Science; Vol 18 No 1 (2019): June 2019
KW -
N2 - Given a sorting of the keys stored in a hash table one can guarantee a worst case time complexity for associations of O(log(n)) and an average complexity of O(log(log(n)), thereby improving upon the guarantees usually encountered for hash tables using open addressing. The idea is to use the numerical order given by a hashing function and resolve collisions upholding said order by using bubble sort on the small patches that inevitably form. The name \texttt{patchmap} has been devised for the implementation of this data-structure and the source code is freely available.
UR - http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/581