什麼是一個整數元組的好散列函數？

我有這個類...什麼是一個整數元組的好散列函數？

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

什麼是一個整數元組的好散列函數？

回答

相關問題