Hash Tables with Pseudorandom Global Order - Brehm, Wolfgang (INFOCOMP Journal of Computer Science, 2019)
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 patchmap has been devised for the implementation of this data-structure and the source code is freely available.