[LINUX] 32-Bit-Eingabe / beliebige Bitausgabe Hash-Funktion

Hash-Funktion vom 32-Bit-Wert bis zur angegebenen Bitlänge. Aus dem Linux-Kernel.

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

Für die magische Zahl "0x9e370001" (16) / "2654404609" (10) wird eine Primzahl nahe dem goldenen Schnitt des 32-Bit-Werts 2 ^ 32 * (sqrt (5) -1) / 2 = 2654435769.5 ausgewählt.

// 2^32 * (sqrt(5) - 1) / 2 = 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 = 2654404609