3
$\begingroup$

I need to know whether hash table size, $S$ has any impact on distribution of a value in hash table.

At the moment I'm using SHA512 and I can tolerate up to 50 elements in any bucket, and I have $10^6$ elements; I set hash table length to $S=50000$. This is far more larger than what is suggested in the literature [1]. However, if I reduce the table length I would get overflow (as I have tested and saw it).

To find position of an element in hash table I do $hash(val) mod S$.

Question: Does $S$ play any role in distribution of the value in hash table? In other words, do I need to set $S$ as a prime number or power of two ?

[1]. http://www14.in.tum.de/personen/raab/publ/balls.pdf

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Does your reference suggest anything about the size of the hash table? I only see asymptotics in the paper. Why are you using SHA512? For a hash table it is uncommon to use a cryptographic hash function since they have terrible performance and you don't need security guarantees. If your hash function behaves well there's no need to choose a specific value of $S$, any number is fine. $\endgroup$ – Tom van der Zanden Nov 18 '15 at 13:52
  • $\begingroup$ @TomvanderZanden No, it does not suggest. Well, I'm implementing a cryptographic protocol, and cryptopp library allows me to use hash function. So in order to reduce collision probability I think I need to use cryptographic hash function. $\endgroup$ – user153465 Nov 18 '15 at 13:56
  • $\begingroup$ "So in order to reduce collision probability I think I need to use cryptographic hash function." -- no, you don't. Cryptographic properties are a superset of what you need. $\endgroup$ – Raphael♦ Nov 18 '15 at 19:56
1
$\begingroup$

An an ideal world - the answer is no. (but life is not ideal..)

In an ideal world, a hash function can be imagined as a random function, that takes a random input $x$ to a random place in $S$, uniformly distributed. In this case, the size of $S$ doesn't change the distribution -- any item is always uniform over $[1,...,S]$, no matter what $S$ is.
(Of course, a smaller $S$ will mean more collisions, but I think you understand that part).

However, in the real world, it matters how things are implemented. For instance, you say that use SHA512, and I assume your output is 512 bits (but it doesn't matter if you use a smaller digest size). This means, that (assuming SHA is closed to being ideal), that any item is sent to a uniform location over $[1,...,2^{512}-1]$. But your $S$ is smaller, say, $S=5000$. How do you "fold" the hash output into $[1,...,S]$? This transformations changes the distribution over $[1,...,S]$ and it may not be uniform anymore (unless you carefully choose $S$ and carefully make this transformation "balanced"). For instance, if $S$ is not a power of 2, some locations will be more probable than others: simply because of the pigeonhole principle, any transformation from $[1,...,2^{512}-1]$ to $[1,...,S]$ cannot be (perfectly) balanced.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for the answer. Thus, implementation wise, I do need to set S as a power of 2 to have a better distribution. $\endgroup$ – user153465 Nov 18 '15 at 17:20
  • $\begingroup$ See also this question: cs.stackexchange.com/questions/48461/hash-table-in-practice $\endgroup$ – Ran G. Nov 18 '15 at 17:20
  • $\begingroup$ Setting $S$ as a power of 2: theoretically it will equalize the distribution. Practically, for large enough $S$, it may not make any noticeable difference, but may be easier and/or faster to implement. This depends on the specifics of your systems. $\endgroup$ – Ran G. Nov 18 '15 at 17:28
  • 1
    $\begingroup$ Mapping the output to $[1,..,5000]$ does not introduce any noticeable non-uniformity. If you try to quantify the amount of non-uniformity, you'll discover that it is incredibly (exponentially) small -- far too small to matter. In fact, there's no need for $S$ to be a power of 2; just reducing modulo $S$ will be fine. See my answer. $\endgroup$ – D.W.♦ Nov 18 '15 at 18:23
3
$\begingroup$

No. If you use SHA512, you can use any modulus $S$ you want: it doesn't need to be prime. A power of two is fine and is no better or worse than a prime.

The reason is that the cryptographic properties of SHA512 ensure that the output of SHA512 is (for all practical purposes) essentially a uniformly random 512-bit string. Because $2^{512}$ is so much larger than your modulus, after reducing modulo $S$, the result will be approximately uniform. Any non-uniformity will be incredibly, exponentially small: so small that it's not detectable within your lifetime, or the lifetime of the solar system. (I know there's another answer that claims non-uniformity is a problem, but that answer failed to quantify the extent of the non-uniformity and thus came to the wrong conclusion; the amount of non-uniformity is so exponentially small that it's completely irrelevant in practice).

So, go ahead and use any modulus that's convenient. It doesn't need to be a power of two or a prime number, if you're using SHA512 as your hash function.

|cite|improve this answer
$\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.