Sorted arrays are most memory efficient

The most memory efficient data structure of storing and accessing uniformly distributed integers is a sorted array, then using interpolation search to retrieve the values in log₂(log₂(n)). If there is more memory available some spots can be left empty to have a collection of patches that are internally sorted and with respect to each other. When looking for an element the search essentially only has to take place within one patch, as the correct patch will be found in the first step, this leads to a complexity independent of the number of elements stored in the hash table and becomes a function of the load factor, the ratio of available spots, so called buckets, and the number of elements stored in the table.

But my keys are not uniform

Now this is all good but what if the keys we want to store are not uniform? This is where patchmap comes in. By sorting the keys by their hash value the order becomes pseudorandom. If the hash function is good then the values that it produces will be uniform even if the keys themselves are not. Therefore by combining a good hash function with a order based on the hash values a data structure can be created that stores keys or key-value pairs in a very memory efficient way and that can linearily interpolate between a (randomly) sorted array and a hash table.

Competing with google::sparse_hash_map

The patchmap achieves a good speed/space trade-off, but it cannot beat googles sparse hash map although the comparison to it and sparsepp were not even very fair in the first place as these are the two hash tables that minimize not the average memory consumption but the peak memory consumption. Each time the other hash tables (including the patchmap) have to grow they reserve a new contiguous block of memory, copy the values from the old table, that has become too small, into the new table, therefore taking up at least 2x more memory during each grow operation. To make the comparison fair I first switch from this simple growing scheme to a hashed array tree.

A hashed array tree allows the hash table to grow virtually in place, at some additional cost. By carefully tuning the maximum load factor before expanding and the expansion factor the patchmap can be made to compete with google::sparse_hash_map .

How to make a good hash function?

I had been thinking about good hash functions for a long time so it was not hard to combine two multiplications and a binary rotation to get a hash function that had a very even output. This is similar to what Malte Skarupke ended up doing starting with a single multiplication with the golden ratio, aka fibonacci hashing and composing it with a bitshift. Galois Field multiplications are a great building block too, but my laptop is a little old and therefore struggles with carry-less multiplications.

The backstory

Recently I wanted to compute a large number of large histograms. The fastest way of computing histograms involves hash tables. As c++ is my favorite programming language I had chosen std::unordered_map as the backend. Everything was going smoothly just as I had imagined but then when I was running the code on my laptop instead of the servers at my institute everything froze. The memory required was around 8 times of what I had anticipated. It turns out I was triggering close to the worst case for the std::unordered_map as I was mapping 16-bit values to 16-bit values on a 64-bit machine. The std::unordered_map is a chaining hash table which means that for each pair of 16-bit values it needs to store a 64-bit pointer, this creates an especially large overhead in this case. I ended up sorting the values first and then computing the histograms from the sorted arrays, which takes much longer, but uses the minimum amount of memory. But I still had more memory available, I was just using 6 GB out of the 16 GB I had in my laptop. Would it not be great if there was a data structure that could interpolate between the two solutions? Or at least if there was a hash table that was more memory efficient?

And before I even found out that there were indeed hash tables that are way more efficient I had an idea that I needed to try.

The idea is as has been hinted at to interpolate between a sorted array and a hash table. That is mapping the keys linearly to the hash table and resolving collisions based on the numerical value of the key should they occur. This works well if the keys are uniformly distributed and in this case has the added effect of essentially sorting the keys in O(1) time and O(1) memory, not in place however as for this to work there is some fractional extra space needed, at least 5% extra would be good.

Comparing to other approaches

This approach might look very similar to the one suggested in "Ordered Hash Tables" (01 January 1974) O. Amble D. E. Knuth but there is a mayor difference in that the hash tables there are ordered first by the hash of the keys and then by the value of the key. If the entries are however only ordered by the hash value there exists a global order, which all of a sudden allows advanced search strategies like interpolation search and binary search.

In fact the approach is much more similar to robin hood hashing with linear probing because if two keys collide at the same position the key whose hash value is lower will also have been displaced more and will therefore displace the key with the larger hash value, therefore keeping up the same order. There has however been no hash table using robin hood hashing with linear probing that takes advantage of this fact.

Availability

https://github.com/1ykos/ordered_patch_map

[ C++17, open source, beta stadium, let me know if you want to use it, I will try to make it work for you! ]

Detailed description

For a more detailed description of the inner workings of the patchmap you can have a look at (open-access):

http://www.dcc.ufla.br/infocomp/index.php/INFOCOMP/article/view/581