Hash Tables with Pseudorandom Global Order

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.