4
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Evil Sep 26 '16 at 21:40
  • $\begingroup$ 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. $\endgroup$ – Alan Wolfe Sep 26 '16 at 22:11
  • $\begingroup$ 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. $\endgroup$ – Alan Wolfe Sep 26 '16 at 22:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Pseudonym Sep 27 '16 at 2:54
  • 1
    $\begingroup$ 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. $\endgroup$ – KWillets Oct 4 '16 at 16:34
6
$\begingroup$

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.

Building the smallest decision tree is NP-hard in general, but there are heuristic algorithms that do a reasonable job. You might look at the ID3 algorithm, for instance; in many settings it does a pretty good job of building a small (though not necessarily minimal) decision tree. You can compare that to other ways of building perfect hash functions and see which is computationally more efficient for your particular data set. Probably the only way to know is to try it out; I'm not sure there is any theory that will give you a definitive answer, as the answer probably depends on characteristics of your dataset that will be hard to model in a theoretical setting.

$\endgroup$
1
$\begingroup$

A practical answer to this question is that the fastest lookup is the simplest. Make a flat array of the data items you want to look up, and make sure all your keys are pre-processed (before run time, possibly at compile time) from their key value into the array index that they correspond to.

Furthermore, doing this, if the data is truly static, and has duplicate values in it, you can make multiple keys point at the same value to deduplicate the data.

This is the fastest pragmatic solution, but doesn't answer the question about what sort of data structures might be helpful, for the cases where you can't preprocess the data and keys in this way.

More info on this and similar techniques, including performance timings and source code, is available here: http://blog.demofox.org/2016/10/03/is-code-faster-than-data-examining-hash-tables/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.