在从密钥的哈希码计算哈希表桶索引的同时,为什么当桶的数组大小为2的幂时,我们在分割(模数)后避免使用余数？
在计算哈希时,你需要尽可能多的信息,在整个比特范围内以低廉的价格进行分配:例如,32位无符号整数通常是好的,除非你有很多(> 30亿)项目存储在哈希表中.
它将哈希代码转换为您真正感兴趣的存储桶索引.当存储桶数量为2的幂时,您需要做的就是在哈希码h和(n-1)之间进行AND运算,结果等于h mod n.
这可能是坏的原因是AND操作只是从哈希码中丢弃比特 - 高级比特.这可能是好的也可能是坏的,取决于其他事情.一方面,它会非常快,因为AND比分区快得多(并且是你选择使用2个数量的桶的通常原因),但另一方面,糟糕的散列函数可能有低位中的熵较差:也就是说,当散列数据发生变化时,较低位的变化不大.
京公网安备 11010802040832号 | 京ICP备19059560号-6 