在计算索引（哈希表实现）时使用&vs MOD运算符有什么区别？

Question

对于常规哈希表实现：

• 计算密钥的哈希值， hash(key)=hashcode

• 将哈希代码映射到表/数组。 hashcode % array_length = index

• 一旦我们得到索引，我们就在该索引的链表中添加一个节点（键、值、更新下一个指针）。

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

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的幂，那么就不能这样做（编译语言优化器通常用更快的位掩蔽/移位操作代替2模的幂或除法/乘法）