167

Like many of you, I use ReSharper to speed up the development process. When you use it to override the equality members of a class, the code-gen it produces for GetHashCode() looks like:

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (Key != null ? Key.GetHashCode() : 0);
            result = (result * 397) ^ (EditableProperty != null ? EditableProperty.GetHashCode() : 0);
            result = (result * 397) ^ ObjectId;
            return result;
        }
    }

Of course I have some of my own members in there, but what I am wanting to know is why 397?

  • EDIT: So my question would be better worded as, is there something 'special' about the 397 prime number outside of it being a prime number?
Yves M.
  • 29,855
  • 23
  • 108
  • 144
programmer
  • 4,342
  • 4
  • 24
  • 21

2 Answers2

181

Probably because 397 is a prime of sufficient size to cause the result variable to overflow and mix the bits of the hash somewhat, providing a better distribution of hash codes. There's nothing particularly special about 397 that distinguishes it from other primes of the same magnitude.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198
  • 81
    And 397 is happy. Don't we all just want to be happy? – Russell B Jun 28 '12 at 00:53
  • 2
    Okay, but why it has to be prime, and why it has to be of that exact magnitude? If it has to be prime, why not 2 or 2147483647? I guess to get nice mutation (and only reason for this multiplication is mutation) we don't need number to be prime. We need multiplicator to have relatively same number or zeroes and ones, preferably without explicit patterns. 397=110001101b complies. Still not sure about magnitude. – Andriy K Mar 18 '15 at 13:45
  • 5
    As Nick said, there's nothing particularly special about it. It doesn't NEED to be that size, that's just a number that's big enough that when you are calculating a hash the result will overflow (since GetHashCode() returns an Int32). Selecting a prime is just helpful for distribution, I don't have a math degree so I'm not going to try and explain it, but multiplication by a prime will have a result that's more well distributed than multiplication by any other arbitrary number. – Ben Randall Oct 14 '15 at 01:40
  • @AndriyK 2 is a very small size for a Hash Table. Your load factor would be the smallest possible load factor for a prime number-based Hash Table size. As the load factor approaches 0, the proportion of unused areas in the hash table increases, but there is not necessarily any reduction in search cost. So it is literally the worst possible size for a Hash Table. In other words, you can think of `* 397` as defining the size of the hash table, which is what the FNV hash algorithm does (but it recommends 1099511628211 for _64-bit_ hashes, which don't apply well to 32 bit ints). – John Zabroski Jan 18 '21 at 23:48
  • It's worth noting that FNV's recommended number is for hashing a sequence of *bytes*, whereas ReSharper's number is for hashing a sequence of *ints* (the inner hash codes). That means multiplying by a large number and making the result mod 2^32 is prone to converging, which is not desirable for a hash function. – fernacolo Mar 09 '23 at 01:58
19

The hash that resharper uses looks like a variant of the FNV hash. FNV is frequently implemented with different primes. There's a discussion on the appropriate choice of primes for FNV here.

kybernetikos
  • 8,281
  • 1
  • 46
  • 54