java - 哈希表哈希避免负哈希码

Question

我想知道为什么Hashtable避免使用负哈希码？

int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

哪里(hash & 0x7FFFFFFF)使有符号位从 0 变为正数，但为什么我们不能将有符号的 32 位整数视为无符号？甚至使用模块化技巧使其变得积极。例如，

public static long int_mod(int hashcode, int tab_length){
     return (hashcode % tab_length + tab_length) % tab_length;  
}

score 11 · Accepted Answer

该值必须介于0和之间，tab.length - 1因为它用作tab存储值（和溢出元素）的内部数组（在这种情况下）的索引。因此，它不能为负数。

我认为(hash & 0x7FFFFFFF) % tab.length优先使用(hashcode % tab.length + tab.length) % tab.length它是因为它更快而不会过度增加冲突的机会，但是您必须找到设计文档或与原始开发人员交谈才能确定。

score 2 · Accepted Answer

...但是为什么我们不能...

你问为什么选择一个特定的实现。没有人能告诉你，除了代码的原始作者，如果他或她记得的话。

总是有多种方法可以在代码中实现一个想法。编写代码的人必须选择其中之一。事后问为什么没有选择另一个特定的实现是没有多大意义的。

score 2 · Accepted Answer

如果你保持你的容量为 2 的幂，

private static final int CAPACITY = 64;
private static final int HASH_MASK = CAPACITY - 1;

final int index = obj.hashCode() & HASH_MASK;

基本上，屏蔽掉除您感兴趣的低位之外的所有位。假设较低的 N 位具有与整个哈希码一样均匀的分布。

score 1 · Accepted Answer

Java 没有原生的无符号类型。如果hashCode将有负值，那么我们将不得不在我们hashCode用作数组索引的任何地方应用这样的屏蔽技巧。

score 1 · Accepted Answer

表面上我们不能将有符号的 int 视为无符号的原因很明显：最初的 Java 开发人员认为无符号支持是不必要的复杂化，因为无符号算术可能会令人困惑。从那以后，这对 Java 来说还不是一个足够大的问题来解决。

正如verdesmerald 所提到的，由于没有明确的记录说明为什么(hash & 0x7FFFFFFF) % tab.length选择了某些东西来影响您的巧妙改装，尽管我们可以找到该决定的理由，但最终我们只能推测为什么做出它。

语义的最后一点，这可能并不那么重要：Hashtable 没有使用负哈希码，因为哈希码被“转换”为索引的非负形式。

score 0 · Accepted Answer

除了他自己（也许还有他的同事）之外，没有人能告诉你为什么原始作者选择了那个实现。无论如何，这并不重要，因为它工作正常。

关于你提议的实现：它可能没有做你认为它应该做的事情。您应该刷新 java 中 % 运算符的实际作用：例如这里。将整数溢出添加到混合中，您建议的表达式可能会导致负值...

6 回答 6