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

| cite | improve this answer | |
$\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
  • $\begingroup$ In most cases, it would be sufficient if the modulus had no prime factors smaller than 13. The larger the smallest prime factor of the modulus is, the smaller the chance that keys with common factors with the modulus will be unexpectedly common in the population of keys. Most of the time it's overkill to insist the modulus be prime. You may be interested in this article: linkedin.com/pulse/… $\endgroup$ – WaltK Jan 11 at 5:56
18
$\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.

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

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

First of all, the question is phrased incorrectly. The following are equivalent and correct expressions of the intended question:

  • why must we use a prime number as the modulo of the hash value (not "in the hashing function)

or equivalently and more succinctly:

  • why must the size of a hash table be a prime number?

The proper answer to this question lies in the context, and that context is open addressing with double hashing collision resolution.

Where you compute:

hashval1 = hashfcn1(k) // for initial location
hashval2 = hashfcn2(k) // probing increment

hashval1 is used for the initial insertion probe. If that location is empty, then you insert the (k, v) and you’re done, never using hashval2. If that location is occupied, then you jump hashval2 addresses to (hashval1 + hashval2) % arraysize, and repeat to see if the location is empty. If that location is again not empty, then you jump another hashval2 addresses to (hashval1 + 2 * hashval2) % arraysize. And so on.

Here’s the key: HOW MANY TIMES DO YOU PROBE BEFORE GIVING UP?

If every element of the array is potentially a target, then the answer is: you probe n-times. This is easy to visualize with linear probing, you write a for (i = 0; i < n; ++i) loop for probing which breaks early if a empty slot is found. It’s no different with double hashing, with the exception that the probe increment is hashval2 rather than 1. But this leads to a problem, you’re not guaranteed to probe every slot in the array when hashval2 > 1. Simple example of this: array size = 10 and hashval2 = 2; in this example you only ever probe the even or odd slots, in fact, you end up probing each slot twice, which is pointless. Even if you make the array size an odd number like 15, if probe increment is 5 then the probe sequence will be (let’s use hashval1 = 0): 0, 5, 10, 0, 5, 10, 0 5, 10, 0, 5, 10, 0, 5, 10. You keep probing the same three occupied slots over and over.

What’s the problem here? The problem is that the hash table size and hashval2 share common factors, in this case 5. So we need the hash table size and hashval2 to share no factors. Since hashval2 is a function of k and post modulo lies in the range of 0 < hashval2 < array size, there’s nothing we can do about hashval2. That leaves the array size. The array size in double hashing must be guaranteed to have no factors in common with hashval2. Thus by simple math, the array size must be a prime number.

Example: Array size = 11 (a prime number). hashval1 = 1.

hashval2 = 1; // 1,2,3,4,5,6,7,8,9,10,0 <-- probing sequence
hashval2 = 2; // 1,3,5,7,9,0,2,4,6,8,10
hashval2 = 3; // 1,4,7,10,2,5,8,0,3,6,9
hashval2 = 4; // 1,5,9,2,6,10,3,7,0,4,8
hashval2 = 5; // 1,6,0,5,10,4,9,3,8,2,7
hashval2 = 6; // 1,7,2,8,3,9,4,10,5,0,6
hashval2 = 7; // 1,8,4,0,7,3,10,6,2,9,5
hashval2 = 8; // 1,9,6,3,0,8,5,2,10,7,4
hashval2 = 9; // 1,10,8,6,4,2,0,9,7,5,3
hashval2 = 10;// 1,0,10,9,8,7,6,5,4,3,2

You always probe a maximum of the number of slots in the hash table; i.e., every slot has an equal chance of hosting a value. But since the probe increment is itself a hash value, it is uniformly distributed over the size of the hash table which eliminates the clustering you get with other collision resolution algorithms.

TL;DR: a hash table size that is a prime number is the ONLY way to guarantee that you do not accidentally re-probe a previously probed location.

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