Fastest static associative map

Let's say that I wanted to build a key to value associative map where the only requirement was that lookup times were fast.

Once built, the associative map would not allow inserts, deletes, or modifications, so is a static data structure.

What would the best algorithm be for making and using such a thing?

I'm interested to know if there is a provable "best solution", or if it's provably NP-Hard or similar.

Here are some ideas of my own:

Minimally Perfect Hash

My best idea would be to use minimal perfect hashing. I would find a hashing algorithm that hashes the $N$ known inputs to $[0,N)$, that resulting value being able to be looked up in an array.

I would want to find the computationally cheapest (average time) hashing algorithm for my data set.

However, finding a minimally perfect hash function is a challenging problem already without wanting the computationally cheapest one.

Feature Based Indexing

Another thought I have would be to look at my input and find bits which are differing between items. For instance, file paths may have a lot of the same characters in them, especially if they are absolute paths to the same deep folder.

I could find where the bits are that matter and make a tree of objects out of them.

The challenge here I think is that I would ideally want a balanced tree, and it might be hard to test all the permutations of bits that actually matter, to make the tree as balanced as possible.

I think Ideally, my hope is that the entire tree could go away, and I could instead take the bits that mattered and make some equation like "xor bit 2 against bit 3 and add bit 5" to come up with an index into an array.

• In that particular case the data type used for key and number of elements makes a huge difference. If the fastest possible lookup is needed a bit relaxed (almost minimal perfect hash) is extremely easier to find (based on my own pursuit for huge data) and the resulting function is cheaper. Do you need it to be minimal? With such tree construction you can just count number of elements having particular bit set, but the function requires a lot of multiplications so probably this is not good direction. – Evil Sep 26 '16 at 21:40
• I can go from non minimal perfect hash to minimal perfect hash via a switch statement and enums in C++, so minimal is not strictly required. Switch statements aren't free of course, so non minimal by itself adds a little overhead. – Alan Wolfe Sep 26 '16 at 22:11
• oh but for what it's worth, all of my purposes are likely to be strings as keys. Sometimes ~16 characters for a unique identifier, sometimes maybe a file path and it could be a lot more. – Alan Wolfe Sep 26 '16 at 22:13
• If you expect to be searching for keys which are not there some reasonable proportion of the time, you may want to consider plain old perfect hashing, not "minimal". This avoids some key comparisons on lookup failure, and the less-constrained problem will make a smaller hash function easier to find. Oh, and don't forget tries. – Pseudonym Sep 27 '16 at 2:54
• There isn't really one answer. Look into PATRICIA or crit-bit trees for long key lookups. The tradeoff depends on relative costs of character or bit comparisons and arithmetic, hash-related instructions, as well as caching and other optimizations such as prefetch and branch prediction. Then you also have properties of the data to consider. – KWillets Oct 4 '16 at 16:34

Here's a way to think about the feature-based approach: you select a set of candidate features, then look for the smallest decision tree that assigns each of the $N$ keys a different index in $[0,N)$ using only those features. This is effectively a way of building a perfect hash, where the hash function is expressed as a decision tree applied to the feature vector constructed from the input.