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.