爲什麼HashSet允許相同的項目，如果hashcodes是不同的？

Question

HashSet類有一個add(Object o)方法，它不會從另一個類繼承。該方法的Javadoc說明如下：

如果指定的元素不存在，則將該元素添加到此集合中。更正式地說，如果該集合不包含e2這樣的(e==null ? e2==null : e.equals(e2))，則將指定元素e添加到該集合。如果該集合已包含該元素，則該呼叫將保持該集合不變並返回false。

換句話說，如果兩個對象相等，那麼第二個對象將不會被添加，並且HashSet將保持不變。但是，我發現如果對象e和e2具有不同的哈希碼，則不是這樣，儘管事實上是e.equals(e2)。下面是一個簡單的例子：

import java.util.HashSet; 
import java.util.Iterator; 
import java.util.Random; 

public class BadHashCodeClass { 

    /** 
    * A hashcode that will randomly return an integer, so it is unlikely to be the same 
    */ 
    @Override 
    public int hashCode(){ 
     return new Random().nextInt(); 
    } 

    /** 
    * An equal method that will always return true 
    */ 
    @Override 
    public boolean equals(Object o){ 
     return true; 
    } 

    public static void main(String... args){ 
     HashSet<BadHashCodeClass> hashSet = new HashSet<>(); 
     BadHashCodeClass instance = new BadHashCodeClass(); 
     System.out.println("Instance was added: " + hashSet.add(instance)); 
     System.out.println("Instance was added: " + hashSet.add(instance)); 
     System.out.println("Elements in hashSet: " + hashSet.size()); 

     Iterator<BadHashCodeClass> iterator = hashSet.iterator(); 
     BadHashCodeClass e = iterator.next(); 
     BadHashCodeClass e2 = iterator.next(); 
     System.out.println("Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): " + (e==null ? e2==null : e.equals(e2))); 
    } 

從主方法的結果是：

Instance was added: true 
Instance was added: true 
Elements in hashSet: 2 
Element contains e and e2 such that (e==null ? e2==null : e.equals(e2)): true 

如上面的例子中清楚地示出，HashSet的是能夠添加兩個元素，其中e.equals(e2)。

我打算假設這是而不是 Java中的一個錯誤，並且事實上存在一些完全合理的解釋。但我無法弄清楚究竟是什麼。我錯過了什麼？

Answer 1

我想你真正想要問的是：「爲什麼HashSet的對象添加與不相等的散列碼，即使他們自稱是平等的」

我的問題和你發佈的問題之間的區別在於，你認爲這種行爲是一個錯誤，因此你從這個角度來看它會感到悲傷。我認爲其他海報已經做了足夠的工作來解釋爲什麼這不是一個錯誤，但是他們沒有解決潛在的問題。

我會盡力在這裏做;我建議您改述一下您的問題，以消除對Java中糟糕文檔/錯誤的指責，這樣您可以更直接地探索爲什麼您遇到了您所看到的行爲。

---

的equals()單證狀態（強調）：

注意，這是通常需要覆蓋hashCode方法每當這個方法被覆蓋，以便維持用於hashCode方法一般合同，其中規定等於對象必須具有相同的散列碼。

equals()和hashCode()之間的合同是不是在Java規範只是一個惱人的怪癖。它在算法優化方面提供了一些非常有價值的好處。通過假設a.equals(b)意味着a.hashCode() == b.hashCode()，我們可以直接調用equals()進行一些基本等同性測試。特別是，上面的can be turned around-a.hashCode() != b.hashCode()的不變量意味着a.equals(b)將是錯誤的。

如果你看一下HashMap的代碼（HashSet內部使用），你會發現一個內部靜態類Entry，像這樣定義的：

static class Entry<K,V> implements Map.Entry<K,V> { 
    final K key; 
    V value; 
    Entry<K,V> next; 
    int hash; 
    ... 
} 

HashMap存儲密鑰的散列碼與密鑰一起和價值。因爲在密鑰存儲在映射中的時間內，哈希代碼不會發生變化（請參閱Map的文檔「」）如果以影響等於的方式更改對象的值，則不會指定映射的行爲比較對象是地圖中的關鍵字「）HashMap可以安全地緩存該值。通過這樣做，只需要爲地圖中的每個鍵調用hashCode()一次，而不是每次檢查鍵時。

現在讓我們看看put()，我們看到這些緩存的哈希實施冤大頭，與上面的不變一起：

public V put(K key, V value) { 
    ... 
    int hash = hash(key); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
    Object k; 
    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
     // Replace existing element and return 
    } 
    } 
    // Insert new element 
} 

尤其注意的是，條件永遠只能調用key.equals(k)如果哈希碼相同，並且由於short-circuit evaluation，密鑰不是完全相同的對象。通過這些方法的合約，HashMap應該可以安全地跳過這個呼叫。如果您的對象執行不正確，則由HashMap做出的這些假設不再成立，您將收回不可用的結果，包括集合中的「重複」。

---

請注意，您的要求「HashSet的...有一個add(Object o)方法，這是不是從另一個類繼承」是不太正確的。儘管其母公司類別,AbstractSet未實施此方法，但父母界面,Set確實規定了該方法的合同。 Set接口不涉及散列，只涉及相等，因此它根據與(e==null ? e2==null : e.equals(e2))相等的方式指定此方法的行爲。只要你遵守合同，HashSet按照文件記錄，但儘可能避免浪費工作。然而，只要你違反規則，HashSet不能指望以任何有用的方式行事。

請考慮如果您嘗試將對象存儲在TreeSet中，並且執行得不正確Comparator，您同樣會看到無意義的結果。我記錄了一些TreeSet在另一個問題中使用不可信Comparator時的行爲方式的例子：how to implement a comparator for StringBuffer class in Java for use in TreeSet?

Answer 2

因爲hashcode()真的實行非常嚴重，

它會嘗試在每個隨機桶等同於每個add()，如果從hashcode()返回恆定值，它不會讓你輸入任何

Answer 3

@Override 
public int hashCode(){ 
    return new Random().nextInt(); 
} 

每次評估時，您都返回不同的代碼以顯示同一對象。顯然你會得到錯誤的結果。

---

add（）函數如下：

public boolean add(E e) { 
return map.put(e, PRESENT)==null; 
} 

和put（）是

public V put(K key, V value) { 
    if (key == null) 
     return putForNullKey(value); 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
      V oldValue = e.value; 
      e.value = value; 
      e.recordAccess(this); 
      return oldValue; 
     } 
    } 

    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 

如果您發現第一個已經被計算出這是你的情況不同的是，爲什麼對象被添加。 equals（）只有在對象的哈希值相同時纔會進入圖片，即發生衝突。因爲如果哈希是不同的equals（）永遠不會執行

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 

瞭解更多關於什麼短路是。因爲e.hash == hash是錯誤的沒有其他評估。

我希望這會有所幫助。

Answer 4

你已經違反了equals/hashCode基本合同：

從hashCode()文檔：

如果兩個對象根據equals相等（Object）方法，然後調用hashCode方法對這兩個對象的每一個都必須產生相同的整數結果。

和從equals：

注意，這是通常需要覆蓋hashCode方法每當這個方法被覆蓋，以便維持用於hashCode方法一般合同，其中指出相等的對象必須具有相同的哈希碼。

HashSet依靠equals和hashCode正在一貫的執行 - 這個名字HashSet的Hash部分基本上意味着「這個類使用hashCode以提高效率。」如果兩種方法一致執行而非，則所有投注均關閉。

這是不應該在實際代碼發生，因爲你不應該違反實時代碼合同...

Answer 5

它不要求哈希碼是所有元素不同！只需要兩個元素不相等。

HashCode首先用於查找對象應該佔據的散列桶。如果hadhcodes不同，則假定對象不相等。如果hashcodes相等，則使用equals()方法確定相等性。 hashCode的使用是一種效率機制。

And ...
您的哈希碼實現違反了它不應該改變的合同，除非對象標識字段發生變化。