The Magic Constant

The hash_long function is found a lot of places in the kernel.  Amongst other places it is how PIDs are stored in a table.

The has_long function boils down to

unsigned long hash_long(unsigned long val, unsigned int bits)
{
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 – bits);
}

When I stumbled across this I was curious as to where 0x9e370001 came from. After a bit of searching, I found this:
(from “Understanding the Linux Kernel”)

The Magic Constant

You might wonder where the 0xe370001 constant (= 2,654,404,609) comes from. This hash function is based on a multiplication of the index by a suitable large number, so that the result overflows and the value remaining in the 32-bit variable can be considered as the result of a modulus operation. Knuth suggested that good results are obtained when the large multiplier is a prime approximately in golden ration to 2^32 (32 bit being the size of x86 registers). Now, 2,654,404,609 is a prime near to 2^32 * (sqrt(5) -1)/2 that can also be easily multiplied by additions and bit shifts, because it is equal to 2^31 + 2^29 -2^25 -2^19-2^16+1.

In other words, pulled out of Knuth’s and other’s asses.

Do people just sit around thinking about this type of stuff? My guess would be yes. All I know is my new favorite number is now 2,654,404,609.