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

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 . 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 ?

• 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. – Tom van der Zanden Nov 18 '15 at 13:52
• @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. – user153465 Nov 18 '15 at 13:56
• "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. – Raphael Nov 18 '15 at 19:56

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.

• Thank you for the answer. Thus, implementation wise, I do need to set S as a power of 2 to have a better distribution. – user153465 Nov 18 '15 at 17:20
• See also this question: cs.stackexchange.com/questions/48461/hash-table-in-practice – Ran G. Nov 18 '15 at 17:20
• 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. – Ran G. Nov 18 '15 at 17:28
• 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. – D.W. Nov 18 '15 at 18:23

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.