2
$\begingroup$

Assume one wants to store $1000$ distinct integers of $5$ digits in a hash table that is defined once for all (the intent is to hard-code it).

We have some freedom to change its behavior by changing the number of buckets and/or the hashing function.

Is there a theory that can help minimize the worst-case or average-case lookup time, in the same way you can optimize a binary search tree ?

I am more after a practical solution, meaning that accesses to the optimal table should be truly faster than with a table built without care.


The space requirement is a reasonable constant factor, say $2$ or $3$ times the number of integers. An array of $100000$ slots would be out of question.

$\endgroup$
  • $\begingroup$ Are the 1000 integers known in advance? Can we choose our hash function after seeing those 1000 integers? $\endgroup$ – D.W. Jun 21 '17 at 22:45
  • $\begingroup$ @D.W.: yes to both questions. $\endgroup$ – Yves Daoust Jun 22 '17 at 0:51
4
$\begingroup$

You can use the (minimal) perfect hash function, which is like in your case static (because dynamic insertions / deletions require rehashing), so there is no collision resolution - there are none. The only problem is to find one, but with $n = 1000$ you may brute force it, or use existing software like CMPH or gperf.

There is one worth reading Near-Optimal Space Perfect Hashing Algorithms.

Since you didn't give the space requirement, when the hash is not minimal it is far easier to find.

$\endgroup$
4
$\begingroup$

It is always possible to build a static hash table which has guaranteed O(1) lookup time, provided you allow O(N) empty slots.

For example, a cuckoo hash table will give you a definite found or not found indication with at most two entries examined. Unfortunately, it requires that half the entries in the table be empty to provide this guarantee, so 1000 entries would need a table of 2000 words -- or perhaps 2048 to make hash computations cheaper. There is no additional overhead, since there are no chain links or anything of the sort.

If two words per entry is too much, you can explore the trade-off between the constant number of cells which need to be examined and the density of the table. For example, if you allow each slot to hold two values, you can increase the hash-table density to about 80%, but the number of comparisons to determine where and whether an entry is in the table increases to maximum four instead of two. With four hash functions instead of two and one entry per slot, you can increase the density to 99%, but now you might need to compute up to four hash values as well as doing the four comparisons.

In practice, the hash function for a cuckoo hash can be quite simple (eg. three products xor'd together and a shift, or even simpler if you are prepared to try more possibilities during table construction) and the table can be built in expected time O(N) (and with a reasonably small constant).

Since the discovery of cuckoo hashing, a number of similar datastructures have been invented with the same O(1) guarantee, generally allowing a larger density (and thus a smaller space overhead), but again at the cost of an increased (but constant) number of probes. In general, the approach is to attempt to store the candidate matches consecutively to take advantage of modern CPUs memory caches and potential compare parallelism. If that fits your use case, you might want to look at hopscotch hashing.

If you are willing to expend more time constructing the static table, you could use a perfect hash, which requires only one lookup because it is collision-free. The more time you are willing to spend, the smaller a table you will be able to construct. While it is possible to find a hash which allows 100% utilization of the hash table, the hash function itself needs some storage which is O(N) with a very small constant (a few bits per entry in the table.)

$\endgroup$
  • $\begingroup$ I think that the fist methods you mentioned are what I need. In the case of perfect hashing, I believe that the cost of evaluation of the hash function would exceed that of a simple strategy. $\endgroup$ – Yves Daoust Jun 22 '17 at 15:00
  • $\begingroup$ @yves: that's my guess, too, but it's worth experimenting. It will also depend on how often you expect the lookup to fail. For example, if most lookups succeed, a simple linear-probe closed hash will beat a cuckoo hash (only one hash computation and good locality for the scan) but if most lookups fail the cuckoo hash starts to look better. $\endgroup$ – rici Jun 22 '17 at 15:06
  • $\begingroup$ Most lookups will succeed (say 99%). $\endgroup$ – Yves Daoust Jun 22 '17 at 15:34
  • $\begingroup$ @YvesDaoust: I did a benchmark with 1000 32-bit numbers using both a cuckoo hash and a linear-probe, and there wasn't a measurable difference at 99% success. (Roughly 7 ns per lookup on a Core i5 laptop.) At medium success rates (60-80%) both slow down a bit; there is still little difference (11 ns per lookup) but at low rates the cuckoo hash starts to get faster again while the linear-probe steadily gets slow, ending at 14 ns. I don't really understand why the cuckoo hash gets faster but I suspect branch prediction. $\endgroup$ – rici Jun 22 '17 at 19:45
  • $\begingroup$ @YvesDaoust: I also tried increasing density. Linear probing obviously gets slower as density increases, degrading to 9 ns at 60%, 11 ns at 67% and 15 ns at 80%. I couldn't push cuckoo hashing much beyond 60%; it also degrades but not as much (it starts to take a noticeable amount of time to find a hash, but that only matters to the preprocessing). $\endgroup$ – rici Jun 22 '17 at 19:52

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.