Hash Table: Relation between position of a value and Hash table size

Question

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

Answer 1

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.

Answer 2

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.