The comments on the answer you link to already briefly try to explain why 17
and 23
are not good primes to use here.
A lot of .NET classes that make use of hash codes store elements in buckets. Suppose there are three buckets. Then all objects with hash code 0, 3, 6, 9, ... get stored in bucket 0. All objects with hash code 1, 4, 7, 10, ... get stored in bucket 1. All objects with bucket 2, 5, 8, 11, ... get stored in bucket 2.
Now suppose that your GetHashCode()
uses hash = hash * 3 + field3.GetHashCode();
. This would mean that unless hash
is large enough for the multiplication to wrap around, in a hash set with three buckets, which bucket an object would end up in depends only on field3
.
With an uneven distribution of objects across buckets, HashSet<T>
cannot give good performance.
You want a factor that is co-prime to all possible number of buckets. The number of buckets itself will be prime, for the same reasons, therefore if your factor is prime, the only risk is that it's equal to the number of buckets.
.NET uses a fixed list of allowed numbers of buckets:
public static readonly int[] primes = {
3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369};
Your factor should be one that .NET doesn't use, and that other custom implementations are equally unlikely to use. This means 23
is a bad factor. 31
could be okay with .NET's own containers, but could be equally bad with custom implementations.
At the same time, it should not be so low that it gives lots of collisions for common uses. This is a risk with 3
and 5
: suppose you have a custom Tuple<int, int>
implementation with lots of small integers. Keep in mind that int.GetHashCode()
just returns that int
itself. Suppose your multiplication factor is 3
. That means that (0, 9)
, (1, 6)
, (2, 3)
and (3, 0)
all give the same hash codes.
Both of the problems can be avoided by using sufficiently large primes, as pointed out in a comment that Jon Skeet had incorporated into his answer:
EDIT: As noted in comments, you may find it's better to pick a large prime to multiply by instead. Apparently 486187739 is good...
Once upon a time, large primes for multiplication may have been bad because multiplication by large integers was sufficiently slow that the performance difference was noticeable. Multiplication by 31
would be good in that case because it can be implemented as x * 31
=> x * 32 - x
=> (x << 5) - x
. Nowadays, though, the multiplication is far less likely to cause any performance problems, and then, generally speaking, the bigger the better.