在 Java 中创建 Hashmap 的实现时使用什么 - 取模或按位 AND 运算符？

Question

我有一项大学作业，其中我们要创建自己的 HashMap 实现。在赋值中，当计算要放入数组中的条目的索引时，它说使用模运算符：

int index = key.hashCode() % array.length;

但是从我自己的研究中收集到的所有内容来看，正确的方法是使用按位 AND 运算符：

int index = key.hashCode() & (array.length - 1);

这些方法有哪些优点/缺点？这重要还是首选？谢谢！

Answer 1

模运算符可以产生重复项，所以我猜你的赋值规范是错误的，因为模运算符只能输出数字从0到array.length-1

例如，假设长度为 3。哈希码很大，并且根据密钥本身计算，因此它们可以是任何东西。模数 3 只能产生数字 {0,1,2}，所以重复的可能性非常高

1111 mod 3 -> 是 1

2221 mod 3 -> 也是 1

因此我们有重复的索引，这破坏了索引的目的，因为它们不再是唯一的。

Answer 2

这一切都与分布、验证和优化有关：负数

int

（某些

hashCode()

）的模可能会返回负值。

这里的按位与是一种优化，删除不需要的位（负位符号），从而避免额外的负检查：如果我从第一个答案中获取示例，这里是使用模数和使用按位与的一些值的结果。

System.out.printf("1111 %% 3 = %d%n", 1111 % 3); // 1111 % 3 = 1
System.out.printf("2221 %% 3 = %d%n", 2221 % 3); // 2221 % 3 = 1
System.out.printf("3331 %% 3 = %d%n", 3331 % 3); // 3331 % 3 = 1
System.out.printf("-1 %% 3 = %d%n", -1 % 3); // -1 % 3 = -1

System.out.printf("1111 & 2 = %d%n", 1111 & 2); // 1111 & 2 = 2
System.out.printf("2221 & 2 = %d%n", 2221 & 2); // 2221 & 2 = 0
System.out.printf("3331 & 2 = %d%n", 3331 & 2); // 3331 & 2 = 2
System.out.printf("-1 & 2 = %d%n", -1 & 2);     // -1 & 2 = 2

您可以在这里看到结果：https://onlinegdb.com/ffVoyifb0

这也意味着分布不同 - 这可能是它在

HashMap

中使用的另一个原因。

请注意，要使其发挥作用，

array.length

可能应该是 2 的倍数：

// good = only 2^4 = 16 possible values
array.length = 16 = 0b0001_0000
array.length - 1 = 15 = 0b0000_1111

// bad = only two possible values
array.length = 17 = 0b0001_0001
array.length - 1 = 16 = 0b0001_0000

在 JDK 7 中，

HashMap

构造函数尝试查找 2 的容量倍数：https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util /HashMap.java#L198

Answer 3

模运算符对于所有大小的哈希图都是正确的。它将尽可能均匀地在所有存储桶中分配哈希码。

但是Java的

HashMap

使用位与运算来获取桶号。当桶的数量是2的幂时，那么

& (array.length - 1)

相当于

% array.length

，但是简单的按位运算比取模要快，需要除法运算。

虽然模数运算符适用于任意数量的存储桶，但如果存储桶的数量为 2 的幂，则出于性能原因，请使用等效的位与运算。

Answer 4

按位 AND 运算符将给出第二个运算符范围内的结果，并在该范围内提供良好的随机性，例如：

9 & 3 将给出 1
9 % 3 将给出 0

6 & 3 将得到 2
6 % 3 将再次给出 0

12 & 3 将给出 0
12 % 3 将再次给出 0

此外，与模数相比，按位运算速度更快，因为模数运算在处理过程中经历多个步骤。 这就是为什么在 Map 实现中最好使用按位与取模运算来分散计算索引的结果。

Answer 5

通常，如果您确定哈希值与输入数据强烈去相关并且哈希值的所有位都已正确加扰，那么您只会使用位掩码操作。

如果您的哈希函数或身份哈希函数不好，则使用余数（通常是素数）可以在平滑分布和最小化冲突方面提供一些改进。但比较慢。

如果您应用一些数论，您还可以使用其他变换。根据场景而定。