Why .Net dictionaries resize to prime numbers?

According to this question a .Net dictionary resizes its allocated space开发者_如何学C 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)

---

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.

---

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.

---

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.