Why is '397' used for ReSharper GetHashCode override?

Question

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?

Desiderative

Answer 1

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.

Likker

And 397 is happy. Don't we all just want to be happy? – Corley

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. – Japheth

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. – Injure

@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). – Hensley

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. – Petrify

Answer 2

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.

Virtuosic