15

According to this question a .Net dictionary resizes its allocated space to prime numbers that are at least twice the current size. Why is it important to use prime numbers and not just twice the current size? (I tried to use my google-fu powers to find an answer, but to no avail)

4
  • as a side idea to you question, does anyone know a tree-like balanced data structure that resizes to prime sizes ? maybe I should post another question Jan 9, 2011 at 11:36
  • what is the tree data structure behind .Net's dictionary then ? Jan 9, 2011 at 11:39
  • I asked the question over here stackoverflow.com/questions/4639122/… Jan 9, 2011 at 12:34
  • 1
    @costy None, it's a hash table not a tree. Jan 9, 2011 at 13:24

3 Answers 3

17

The bucket in which an element is put is determined by (hash & 0x7FFFFFF) % capacity. This needs to be uniformly distributed. From this it follows that if multiple entries which are a multiple of a certain base (hash1 = x1 * base, hash2 = x2 * base,...) where base and capacity aren't coprime (greatest common divisor > 1) some slots are over used, and some are never used. Since prime numbers are coprime to any number except themselves, they have relatively good chances of achieving a good distribution.

One particularly nice property of this is that for capacity > 30 the contribution of each bit to the hashcode is different. So if the variation of the hash is concentrated in only a few bits it will still lead to a good distribution. This explains why capacities which are powers of two are bad: they mask out the high bits. A set of numbers where only the high bits are different isn't that unlikely.

Personally I think they choose that function badly. It contains an expensive modulo operation and if the entries are multiples of the prime-capacity its performance breaks down. But it seems to be good enough for most applications.

11

It is an algorithm implementation detail related to choosing a good hashing function and which provides uniform distribution. A non-uniform distribution increases the number of collisions, and the cost of resolving them.

1
  • 7
    Choosing prime number does not provide uniform distribution, no need to oversimplify. With hashsize = prime_number, you have absolutely same chance of getting collisions as with hashsize = 2^k or any other. It's just that some hash sizes make collisions look 'unpredictable', 'random' or 'uniformly distributed'. On the other hand, having hashsize = 2^k would mean that any hash function based on xor will suck. Jan 9, 2011 at 11:19
5

Because of the mathematics of prime numbers.They can not be factored into different smaller numbers. When you divide the hash number from the stored items you thus get an equal distribution. If you would not have a prime number, depending on the objects, the distribution may not be even.

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.