在计算索引时使用 & 与 MOD 运算符有什么区别（Hash Table 实现）？

Question

对于一般哈希 table 实现：

所以，问题是，两者之间有什么区别：

def _get_index(self, key):

   # compute the hashcode
   hash_code = hash(key)
   array_index = hash_code & 15  # FIXME : why?
   return array_index

和

 array_index = hash_code % 15

例如：对于输入：

hm =MyHashMap()
hm.put("1", "sachin")
hm.put("2", "sehwag")
hm.put("3", "ganguly")
print(hm.get("1"))
print(hm.get("2"))
print(hm.get("3"))

输出：

sachin
sehwag
ganguly

'&' 运算符而不是 '%' 这对我来说没有意义？因为它在计算索引时并不总是作为 % 运算符工作，但是，我已经看到开发人员在 Hashtable

的某些实现中使用 &

有什么建议吗？

Answer 1

array_index = hash_code & 15

等同于（正值）：

array_index = hash_code % 16

它仅适用于数字的所有有效位都是 1 的情况（即数字的形式为 2**n - 1）。

两者都删除了数字位的最高部分。

位掩码比除法快得多。所以在可能的情况下使用它来加速计算。每次看到：

b = a % modulo

与a > 0和modulo是2的幂(modulo == 2**n)，可以写成：

b = a & (modulo-1)

相反。如果模不是 2 的幂，那么就不能那样做（编译语言优化器通常用更快的位 masking/shifting 操作替换 2 模或 divisions/multiplications 的幂）

即使在汇编语言中位掩码确实比 division/modulus 快得多，python 也会被解释并且速度优化并不是很明显。无论如何，如果目的是屏蔽位，& 运算符更有意义。

What's the difference between using & vs MOD operators in calculating indexes (Hash Table implementation)?