Hash Tables with Pseudorandom Global Order

Main Article Content

Wolfgang Brehm

Abstract

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.

Article Details

How to Cite
BREHM, Wolfgang. Hash Tables with Pseudorandom Global Order. INFOCOMP Journal of Computer Science, [S.l.], v. 18, n. 1, p. 20-25, june 2019. ISSN 1982-3363. Available at: <http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/581>. Date accessed: 20 july 2019.
Section
Software Engineering