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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Are the 1000 integers known in advance? Can we choose our hash function after seeing those 1000 integers? $\endgroup$
    – D.W. ♦
    Jun 21, 2017 at 22:45
  • $\begingroup$ @D.W.: yes to both questions. $\endgroup$
    – user16034
    Jun 22, 2017 at 0:51

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
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.)

Improve this answer
$\endgroup$
7
  • $\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$
    – user16034
    Jun 22, 2017 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, 2017 at 15:06
  • $\begingroup$ Most lookups will succeed (say 99%). $\endgroup$
    – user16034
    Jun 22, 2017 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, 2017 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, 2017 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.