56
$\begingroup$

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function

$$ H = k \bmod \ 11$$

Now all the values will be placed one after another in 9 rows. For example, in the first bucket there will be $0, 11, 22 \dots$. In the second, there will be $1, 12, 23 \dots$ etc.

Let's say I decided to be a bad boy and use a non-prime as my hashing function - take 12. Using the Hashing function

$$ H = k \bmod \ 12$$

would result in a hash table with values $0, 12, 24 \dots $ in the first bucket, $1, 13, 25 \dots$ etc. in the second and so on.

Essentially they are the same thing. I didn't reduce collisions and I didn't spread things out any better by using the prime number hash code and I can't see how it is ever beneficial.

$\endgroup$
62
$\begingroup$

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$:

  • Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$.
  • Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$.
  • Keys $\{6,18,30,42,...\}$ will be hashed to bucket $6$.
  • Keys $\{9,21,33,45,...\}$ will be hashed to bucket $9$.

If $K$ is uniformly distributed (i.e., every key in $K$ is equally likely to occur), then the choice of $m$ is not so critical. But, what happens if $K$ is not uniformly distributed? Imagine that the keys that are most likely to occur are the multiples of $3$. In this case, all of the buckets that are not multiples of $3$ will be empty with high probability (which is really bad in terms of hash table performance).

This situation is more common that it may seem. Imagine, for instance, that you are keeping track of objects based on where they are stored in memory. If your computer's word size is four bytes, then you will be hashing keys that are multiples of $4$. Needless to say that choosing $m$ to be a multiple of $4$ would be a terrible choice: you would have $3m/4$ buckets completely empty, and all of your keys colliding in the remaining $m/4$ buckets.

In general:

Every key in $K$ that shares a common factor with the number of buckets $m$ will be hashed to a bucket that is a multiple of this factor.

Therefore, to minimize collisions, it is important to reduce the number of common factors between $m$ and the elements of $K$. How can this be achieved? By choosing $m$ to be a number that has very few factors: a prime number.

$\endgroup$
  • $\begingroup$ I just saw that my query is in alignment with your answer. Do you think the hash function in my query holds good? $\endgroup$ – overexchange Dec 27 '16 at 5:46
  • $\begingroup$ @overexchange: I replied to your question. This answer may also be of interest for you. $\endgroup$ – Mario Cervera Dec 28 '16 at 18:30
  • $\begingroup$ why is it so that choice of m matters only if K is skewed? isn't it true that we'll have worse performance with bad m even if K is uniformly distributed? $\endgroup$ – vorou Dec 4 '18 at 11:20
  • $\begingroup$ It depends on what you mean by "bad $m$". If you mean "small compared to the number of elements in the hash table" (i.e., high load factor), then, performance will be poor. However, if you mean "not prime", then this fact is not so important if all keys are equally likely because they will be distributed evenly in the hash table. The question itself provides an example. $\endgroup$ – Mario Cervera Dec 5 '18 at 21:22
16
$\begingroup$

Whether a collision is less likely using primes depends on the distribution of your keys.

If many of your keys have the form $a+k\cdot b$ and your hash function is $H(n)=n \bmod m$, then these keys go to a small subset of the buckets iff $b$ divides $n$. So you should minimize the number of such $b$, which can be achieved by choosing a prime.

If on the other hand you like to have $11$ to $12$ buckets and you know that differences which are multiples of $11$ are more likely than differences which are multiples of $2$ and $3$, you may choose $12$ for your very special application.

$\endgroup$
  • 1
    $\begingroup$ But if my keys do not have the form $a + k \times b$ then $m$ doesn't matter? Is that right? $\endgroup$ – CodyBugstein Apr 4 '13 at 23:58
  • 1
    $\begingroup$ @lmray, if your keys are uniformly distributed, $m$ doesn't matter. If they are not, it will depend on the precision distribution for $m$ to matter or not. $\endgroup$ – AProgrammer Apr 5 '13 at 11:02
  • $\begingroup$ Just reverted the last edit, I forgot that $12>11$. $\endgroup$ – frafl Apr 5 '13 at 11:19
  • 3
    $\begingroup$ Did you mean that "go to a small subset of the buckets iff $b$ divides $m$"? $\endgroup$ – Mikhail Dubov Sep 4 '15 at 23:34
8
$\begingroup$

Whether this has an impact (also) depends on how you treat collisions. When using some variants of open hashing, using primes guarantees empty slots are found as long as the table is sufficiently empty.

Try to show the following, for instance:

Assume we want to insert an element that hashes to address $a$ and resolve collisions by trying positions $a + i^2$ subsequently for $i=1,2,\dots$.

Show that this procedure always yields an empty position if the hash table is of size $p$, $p$ a prime larger than $3$, and at least half of all positions are free.

Hint: Use the fact that the residue class ring modulo $p$ is a field if $p$ is prime and therefore $i^2=c$ has at most $2$ solutions.

$\endgroup$
2
$\begingroup$

If your hash function is of the form $h(k)=a\times k \mod m$ where $m$ is prime and $a$ is chosen at random, then the probability that 2 distinct keys hash to the same bucket is $1\over m$. So for $m=1009$, $Pr\{h(x)=h(y), x\neq y\}=0.00099108027$ which is very small.

This scheme is known as: Universal Hashing.

$\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.