什么是一个整数元组的好散列函数？

我有这个类...什么是一个整数元组的好散列函数？

public class StartStopTouple { 

    public int iStart; 
    public int iStop; 
    public int iHashCode; 

    public StartStopTouple(String start, String stop) { 
     this.iStart = Integer.parseInt(start); 
     this.iStop = Integer.parseInt(stop); 
    } 

    @Override 
    public boolean equals(Object theObject) { 

     // check if 'theObject' is null 
     if (theObject == null) { 
      return false; 
     } 
     // check if 'theObject' is a reference to 'this' StartStopTouple... essentially they are the same Object 
     if (this == theObject) { 
      return true; 
     } 

     // check if 'theObject' is of the correct type as 'this' StartStopTouple 
     if (!(theObject instanceof StartStopTouple)) { 
      return false; 
     } 

     // cast 'theObject' to the correct type: StartStopTouple 
     StartStopTouple theSST = (StartStopTouple) theObject; 

     // check if the (start,stop) pairs match, then the 'theObject' is equal to 'this' Object 
     if (this.iStart == theSST.iStart && this.iStop == theSST.iStop) { 
      return true; 
     } else { 
      return false; 
     } 
    } // equal() end 

    @Override 
    public int hashCode() { 
     return iHashCode; 
    } 
}

...我定义一个对象，对象之间只有iStart和iStop平等是在其他对象等于iStart和iStop。

因此，由于我已覆盖equals()，我需要覆盖hashCode()，但我不确定如何为此类定义好的散列函数。使用iStart和iStop创建这个类的哈希代码的好方法是什么？

来源

2011-06-06 Hristo

一个简单的“桶式散列散列”就足够了。应该帮助SO搜索。 HashMap和类似的实际上会重新散列散列值，所以偶数分布并不是非常重要。 – 2011-06-06 00:28:34

@pst ...你介意提供一些示例代码吗？ – Hristo 2011-06-06 00:29:37

这取决于'iStart'和'iStop'值的分布 - 如果它们介于'0-9'之间，那么'iStart * 10 + iStop'可能会很好。那么，你期待什么范围的输入？ – sarnold 2011-06-06 00:29:38

我会忍不住要利用这一点，特别是因为你要memoize的那样：

Long.valueOf((((long) iStart) << 32) | istop)).hashcode();

来源

2011-06-06 00:30:05

@泰德...你是什么意思我要记忆它？ – Hristo 2011-06-06 00:54:43

它从你的代码看起来就像你要计算一次并将值保存在'iHashCode'字段中。但是，如果你打算这样做，我建议你将'iStart'和'iStop'私有化并提供set/get方法。然后，如果“iStart”或“iStop”发生变化，您可以更新'iHashCode'。 – 2011-06-06 00:58:01

正确...这就是我所做的，所以当调用'hashCode（）'时，我可以返回它。我想我可以在每次调用hashCode（）时计算它，但我不确定这是好还是坏。 – Hristo 2011-06-06 01:00:24

从Bloch的“有效的Java”：

int iHashCode = 17; 
iHashCode = 31 * iHashCode + iStart; 
iHashCode = 31 * iHashCode + iStop;

注：31选择，因为由31乘法可以通过虚拟机的位操作进行优化。（但是由于@Ted Hopp提到的性能并不有用，因为您只计算一次该值。）

注意：如果iHashCode翻过最大的int，则无关紧要。

来源

2011-06-06 00:30:03 toto2

@toto ...我实际上正在阅读他的书，但我想我还没有到那个部分:) – Hristo 2011-06-06 00:32:02

代码是有点错误（并非常破碎）作为呈现。 'iHashCode'应该是'hash'（反之亦然）。这使用隐式整数溢出来实现“滚动”效果。 – 2011-06-06 00:32:04

@Hristo它是＃9。 – toto2 2011-06-06 00:36:27

最简单的可能是最好

iHashCode = iStart^iStop;

异或两个值的

注意，当启动和停止被交换时，这将给出相等的哈希码

作为诺特尔可能性，你可以做

iHashCode = ((iStart<<16)|(iStart>>>16))^iStop;

这第一桶偏移16开始，然后异或用它，因此至少显著位留出的异或停止（如果开始是从来没有超过65K大（更准确地2^16）你可以省略(iStart>>>16)部分）

来源

2011-06-06 00:36:30

我不认为这会起作用......如果你用6或9与15相结合，结果是一样的。 – Hristo 2011-06-06 00:44:55

开始的机会必须始终<停止，所以我会用这个算法。简单而有效。我怀疑你能分辨出这个和更复杂的东西之间的区别。 @Hristo当然会工作......问题只是它的效率。鉴于这些值范围在整个整数范围内，这并不是什么大问题。另外，除非你有一个包含数百万项目的集合，这样哈希码不能很快包装，否则它可能没有关系。 – MeBigFatGuy 2011-06-06 00:46:01

@MeBigFatGuy ...我刚刚举了一个反例。 6^9 = 0^15。 – Hristo 2011-06-06 00:53:05

什么是一个整数元组的好散列函数？

回答

相关问题