hash 算法中的魔数常量

常用的hash常量 

点击(此处)折叠或打开

1. magic = 0x9e370001; // 2654404609

是怎么得来的呢？

在hash散列过程中，通常用基于表项的索引，乘一个适当的大数，于是结果溢出，就把保留下来的32位结果，作为模数操作的结果（hash 值）。Knuth建议，要得到一个理想的结果（任意一个32位内的整数集合，hash后的hash 值比较均衡的分布，冲突概率最小），这个数就应该接近黄金分割数的一个素数。这里，2654404609就是最接近 

点击(此处)折叠或打开

1. 2^32 * （sqrt(5) - 1） / 2

的一个素数， 这个数可以方便的通过加法和位移运算得到：

点击(此处)折叠或打开

1. 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1