只有整數的對象的散列碼

如何以通用（和高性能）的方式實現散列碼，同時最小化具有2個或更多整數的對象的衝突？只有整數的對象的散列碼

更新：正如很多人所說，你無法消除colist entierly（老實說，沒有考慮它）。所以我的問題應該是如何以適當的方式最小化碰撞，編輯以反映這種情況。

使用NetBeans的自動生成失敗;例如：

public class HashCodeTest { 
    @Test 
    public void testHashCode() { 
     int loopCount = 0; 
     HashSet<Integer> hashSet = new HashSet<Integer>(); 
     for (int outer = 0; outer < 18; outer++) { 
      for (int inner = 0; inner < 2; inner++) { 
       loopCount++; 
       hashSet.add(new SimpleClass(inner, outer).hashCode()); 
      } 
     } 
     org.junit.Assert.assertEquals(loopCount, hashSet.size()); 
    } 

    private class SimpleClass { 
     int int1; 
     int int2; 

     public SimpleClass(int int1, int int2) { 
      this.int1 = int1; 
      this.int2 = int2; 
     } 

     @Override 
     public int hashCode() { 
      int hash = 5; 
      hash = 17 * hash + this.int1; 
      hash = 17 * hash + this.int2; 
      return hash; 
     } 
    } 
}

來源

2012-04-05 Mikael Sundberg

爲什麼你需要*消除*碰撞？通常最小化碰撞就足夠了，而且這個代碼在這方面做得非常好。 – 2012-04-05 18:59:02

是的，你是正確的，我更新了我的問題。我不知道我同意它在這樣一個小子集失敗時做得很好（雖然優化升技會失敗） – 2012-04-05 19:02:49

沒有辦法完全消除散列衝突。你的方法基本上是最小化衝突的首選方法。

來源

2012-04-05 18:57:08

您可以以一般（和高性能）的方式實現散列碼，而不用 colisions用於具有2個或更多個整數的對象。

當對32位（一個整數）進行散列（32位以上）（如2個或更多整數）時，在技術上不可能有零衝突。

來源

2012-04-05 18:57:55 TacticalCoder

創建零衝突的散列方法是不可能的。散列法的想法是，你需要一大組對象並將其映射到一組較小的整數。你可以做的最好的事情是儘量減少你在對象的一個子集中碰到的碰撞次數。

來源

2012-04-05 18:58:18 Jeffrey

這就是日食自動生成：

@Override 
public int hashCode() { 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + getOuterType().hashCode(); 
    result = prime * result + int1; 
    result = prime * result + int2; 
    return result; 
}

而與此代碼的測試用例通過......

PS：不要忘記實現equals()！

來源

2012-04-05 19:01:31 barsju

正如其他人所說的那樣，將衝突最小化以消除衝突更爲重要 - 尤其是因爲您沒有說明您打算使用多少個衝突。與1000個桶中的5個物品發生零碰撞比2個桶中有5個物品要容易得多！即使有很多水桶，你的碰撞看起來可能與1000桶和1001非常不同。

另一件需要注意的事情是，你提供的散列很可能甚至不是最終的HashMap使用。例如，如果你看看OpenJDK HashMap code，你會發現你的密鑰的hashCode通過一個私有的hash方法（該鏈接中的第264行）進行重新哈希。因此，如果您正在經歷創建精心構造的自定義哈希函數以減少衝突的麻煩（而不是簡單的自動生成的哈希函數），請確保您也瞭解誰將使用它以及如何使用它。

來源

2012-04-05 19:43:59 yshavit

只有整數的對象的散列碼

回答

相關問題