Take the 2-minute tour ×

Supposing simple uniform hashing, that being, any given value is equally like to hash into any of the slots of the hash. Why is it better to use a table of size 127 and not 128? I really don't understand what's the problem with the power of 2 numbers. Or how it actually makes any difference at all.

When using the division method, we usually avoid certain values of m (table size). For example, m should not be a power of 2, since if m = 2^p , then h(k) is just the p lowest-order bits of k.

Let's suppose the possible elements are only between 1 and 10000 and I picked the table size as 128. How can 127 be better? So 128 is 2^6 (1000000) and 127 is 0111111. What difference does this make? All numbers (when hashed) are still going to be the p lowest-order bits of k for 127 too. Did I get something wrong?

I'm looking for some examples as I really can't understand why is this bad. Thanks a lot in advance!

PS: I am aware of: Hash table: why size should be prime?

share|improve this question
> PS: I am aware of: Hash table: why size should be prime? - then read it again, or link through to this one –  sehe May 8 '11 at 20:25
@sehe The thread you linked makes a supposition that the elements inside have a relationship ("Then if a bunch of strings all having the same first char are fed in, then the results will all be the same modulo k") –  Clash May 8 '11 at 21:23
@Clash: Sorry, but if you insist that it is not necessary to optimize against collisions for your specific hash, you might be confusing indexing with hashing. A perfect hash can be used as an index, but all possible values have to be known up front. With such a configuration it doesn't matter even if the number of buckets is actually a factorial (n!). But that is not the generic science behind hashing. –  sehe May 8 '11 at 21:31
OT: Clash is a very nice screen name to use when talking about hash collisions :) –  sehe May 8 '11 at 21:31
Because real data is almost never uniformly distributed. If you hash strings using 128, you'll get 26 buckets filled unevenly and the rest empty. If you use 127 you'll probably get them all filled more evenly. –  phkahler May 9 '11 at 19:36

7 Answers 7

up vote 18 down vote accepted


That is wrong (or I misunderstood..). k % 127 depends on all bits of k. k % 128 only depends on the 7 lowest bits.


If you have a perfect distribution between 1 and 10,000. 10,000 % 127 and 10,000 % 128 both will turn this in a excellent smaller distribution. All buckets will contain 10,000 /128 = 78 (or 79) items.

If you have a distribution between 1 and 10,000 that is biased, because {x, 2x, 3x, ..} occur more often. Then a prime size will give a much, much better distribution as explained in this answer. (Unless x is exactly that prime size.)

Thus, cutting off the high bits (using a size of 128) is no problem whatsoever if the distribution in the lower bits is good enough. But, with real data and real badly designed hash functions, you will need those high bits.

share|improve this answer
You are right Ishtar. But this is equivalent to saying that any multiple of 128 % 128 (the higher order bits are always multiples of 128) is going to be 0, which for me, is obvious. 127 on the other hand does not have this property, but there will be even more multiples of 127, so this should be even worse, shouldn't it? I don't understand the problem with ignoring the higher bits. –  Clash May 8 '11 at 21:14
@Clash - The real problem in ignoring the higher bits is that people write lousy hash functions. So if your table needs a good distribution it would be silly to ignore those extra bits of effort. Making good hashes is hard, so with a prime size you're just being tolerant. –  Ishtar May 8 '11 at 21:29
@Clash: the problem with ignoring the higher bits is that it's normal for a given data set to vary in only some bits. (E.g., a bunch of string variables representing paths might agree on the first dozen characters. Or, ages might agree on all but the bottom 6 bits.) If those are the bits you're throwing out, you're going to have a lot of collisions. –  Neil G May 8 '11 at 23:35

If you have a perfect hash function that has an even distribution, then it doesn't matter.

share|improve this answer
If you don't, it might happen that a recursive collision appears, thus making it impossible for a certain item to be saved in the hashtable. With prime number size (or perfect hash function), this will not occur. –  Corkscreewe May 8 '11 at 20:05
That would really depend on what the table does on a collision. –  Nick ODell May 8 '11 at 20:08
My hash function is the modulus operator. This is not a perfect hash, is it? I actually haven't reached perfect hashing yet, but from what I have read this has more to do in the fact that no new key is being inserted, the elements are static. –  Clash May 8 '11 at 20:31
@Clash, that's a pretty bad hash function if you are modding by the table size because higher-order bits are not used in the hash function. Why don't you just copy std::hash<int>? –  Neil G May 8 '11 at 20:38
@Neil, this is what I'm trying to understand. How is using a prime, that's close to a prime of two, or any other number near a power of two, better than a power of two? BTW: There is no hash in std as far as I know. There is std::map, but I think inside it works as a binary tree (could be wrong) –  Clash May 8 '11 at 20:58

First off, it's not about picking a prime number. For your example, if you know your data set will be in the range 1 to 10,000, picking 127 or 128 won't make a difference bc it's a poor design choice.

Rather, it's better to pick a REALLY large prime like 3967 for your example so that each data will have its own unique key/value pair. You just want to also minimize collisions. Picking 127 or 128 for your example won't make a difference bc all 127/128 buckets will be uniformly filled (this is bad and will degrade the insertion and lookup run time O(1) to O(n)) as opposed to 3967 (which will preserve the O(1) run times)


The design of the "hash function" is somewhat of a black art. It can be highly influenced by the data that's intended to be stored in the hashing-based data structure, so the discussion on a sensible hashing function can often stray into a discussion about specific inputs.

As why primes are "preferred", one has to consider an "adversary" analysis, that is suppose I designed a general hashing-based data structure, how would it perform given the worst input from an adversary. Since performance is dictated by hashing collisions the question becomes what's the hash to use that minimizes collision in the worst condition. One such condition is when the input are always numbers divisible by some integer, say 4. If you use N = 128 then any number divisible by 4 mod 128 is still divisible by 4, which means only buckets 4, 8, 12, ... are always ever used, resulting in 25% utilization of the data structure. Primes effectively reduces the likelihood of such scenario occurring, with numbers > N.

share|improve this answer
Correct me if I'm wrong, but 3976 will have multiple values in each bucket. –  Nick ODell May 8 '11 at 20:11
@Nick I think he read 1000. I know 127 and 128 are bad for 10000. What I want to understand is, why is it better to take a prime and not just any other number? Why is a power of 2 bad? Say then I picked 16384 (2^14). Why is 16381 better? Thanks –  Clash May 8 '11 at 20:15
Sorry, typoe: i meant 3967. Well, it goes back to the design of the hash function. For now, if you assume a bare, hash function that just takes a number (btwn 1 and 10,000) and takes it modulo by 3967 it practically ensures we have zero collisions in the table. Also the large prime makes our table almost 4x larger and will ensure that collisions have a low probability of happening –  mattkc7 May 8 '11 at 20:15
I don't see why 127 is "small" and 3967 is "really big". All that matters is the load factor. If you're storing 10 elements, 127 is perfectly fine, and will probably incur fewer cache misses. –  Neil G May 8 '11 at 20:46
@mattkc7, what do you mean with "binary is a power of two"? I thought binary was simply another base for representing numbers. I also don't see how half of the hash is getting chopped off when a power of two is used. –  Clash May 8 '11 at 21:31

Wikipedia actually has a good summary of this:


They point out that some hash functions are designed to operate ONLY with prime numbers. This article explains why powers of two are bad:


share|improve this answer

Nick is right that in general, the hash table size doesn't matter. However, in the special case where open addressing with double hashing is used (in which the interval between probes is computed by another hash function) then a prime number-sized hash table is best to ensure that all hash table entries are available for a new element (as Corkscreewe mentioned.)

share|improve this answer

I cannot prove it anymore, although I remember having to do so in an exam at university a million years ago, but optimal hash sizes are not merely prime. You want to pick a prime number N such that N = 4*M − 1 (where M is also an integer).

That makes 31 a better number of buckets than 29. M is 8 when N is 31, but there is no integral M when N is 29.

As I said, I no longer remember the math to prove this. It was in a theory course taught by Rachel Manber, Udi’s wife, about 25 years ago or so.

share|improve this answer

Division Method

"When using the division method, we usually avoid certain values of m (table size). For example, m should not be a power of 2, since if m = 2p , then h(k) is just the p lowest-order bits of k."


To understand why m = 2p uses only the p lowest bits of k, you must first understand the modulo hash function h(k) = k % m.

The key can be written in terms of a quotient q, and remainder r.

k = nq + r

Choosing the quotient to be q = m allows us to write k % m simply as the remainder in the above equation:

k % m = r = k - nm,  where r < m

Therefore, k % m is equivalent to continuously subtracting m a total of n times (until r < m):

k % m = k - m - m - ... - m,  until r < m

Lets try hashing the key k = 91 with m = 24 = 16.

  91 = 0101 1011
- 16 = 0001 0000
  75 = 0100 1011
- 16 = 0001 0000
  59 = 0011 1011
- 16 = 0001 0000
  43 = 0010 1011
- 16 = 0001 0000
  27 = 0001 1011
- 16 = 0001 0000
  11 = 0000 1011

Thus, 91 % 24 = 11 is just the binary form of 91 with only the p=4 lowest bits remaining.

Important Distinction:

This pertains specifically to the division method of hashing. In fact, the converse is true for the multiplication method as stated in CLRS:

"An advantage of the multiplication method is that the value of m is not critical... We typically choose [m] to be a power of 2 since we can then easily implement the function on most computers."

share|improve this answer

Your Answer


