Hash Tables with Pseudorandom Global Order

Main Article Content

Wolfgang Brehm


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, W. (2019). Hash Tables with Pseudorandom Global Order. INFOCOMP Journal of Computer Science, 18(1), 20-25. Retrieved from http://infocomp.dcc.ufla.br/index.php/infocomp/article/view/581
Software Engineering