奇妙なHashSetにはcontainsが含まれています。

Question

JavaでHashSetが混乱しています。contains（）を使用するとhashcode（）とequals（）の結果が検索されますか？ しかし、この場合、正常に動作しません。 大規模なプロジェクトにこの種のコードを入れると、いつか問題になることがあります。 問題は最後のステートメントがFALSEで印刷されているのですか？contains（）がフードの中で何をしていますか？

class R 
{ 
    int count; 
    public R(int count) 
    { 
     this.count = count; 
    } 
    public String toString() 
    { 
     return "R(count attribution:" + count + ")"; 
    } 
    public boolean equals(Object obj) 
    { 
     if (obj instanceof R) 
     { 
      R r = (R)obj; 
      if (r.count == this.count) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 
    public int hashCode() 
    { 
     return this.count; 
    } 
} 
public class TestHashSet2 
{ 
    public static void main(String[] args) 
    { 
     HashSet hs = new HashSet(); 
     hs.add(new R(5)); 
     hs.add(new R(-3)); 
     hs.add(new R(9)); 
     hs.add(new R(-2)); 

     System.out.println(hs); 

     //change first element 
     Iterator it = hs.iterator(); 
     R first = (R)it.next(); 
     first.count = -3; 
     System.out.println(hs); 
     //remove 
     hs.remove(new R(-3)); 
     System.out.println(hs); 

     R r1 = new R(-3); 
     System.out.println(r1.hashCode()); 
     Iterator i = hs.iterator(); 
     R r2 = (R)i.next(); 
     System.out.println(r2.hashCode()); //same hashcode -3 
     System.out.println(r1.equals(r2)); //equals true 

     System.out.println("hs contains object which count=-3 ?" + hs.contains(new R(-3))); //false 
    } 
} 

Answer 1

HashSet店バケットの値は、バケットインデックスが計算されます。その背後にある考え方は、オブジェクトのハッシュコードを読み取ってバケットを1ステップで計算できるようになりました。つまり、はO（1）操作です。今、あなたはあなたの例で行わ何を見て

f(hashcode) := | 5 -> 1 
       | -3 -> 2 
       | 6 -> 3 

：あなたは、オブジェクトを削除したようなバケットを計算するハッシュ関数で

bucket object(hashcode) 
#1  5 
#2  -3 
#3  6 

：

は些細なハッシュセットを想像してみてバケット2で（関数を変更する）、バケット1のオブジェクトのハッシュコードを変更しました。

新しい機能は次のようになります。

f(hashcode) := | 5 -> 1 
       | 6 -> 3 

f(-3)はヌル（戻り偽）とハッシュコードを使用して実際のオブジェクトが返され-3ハッシュコード5を持つオブジェクトがあるべき場所格納されています。

Answer 2

問題がRオブジェクトのハッシュコードがを変更することができるということです。これは、hashCode()メソッドが従わなければならない契約の違反です。

---

この問題の原因を理解するには、ハッシュテーブルの仕組みを理解する必要があります。 Java HashSetは、そのコアにエントリの配列の配列を持っています。ハッシュテーブルにオブジェクトを配置すると、まずそのオブジェクトのハッシュコードが計算されます。それは、それがarray[index]始まるチェーンを検索し、オブジェクトがリストに存在しない場合、それを追加

index = hashcode % array.length 

を計算することによって、アレイ内のインデックスにハッシュコードを低下させます。

HashSetにオブジェクトが含まれているかどうかをテストするために、同じ計算を行い、同じハッシュチェーンを検索します。

しかし、テーブルに入っている間にハッシュコードを変更するオブジェクトを作成すると、上のアルゴリズムでは、最初に追加されたチェーンとは異なるチェーンのオブジェクトを（通常は）探します。もちろんそれは見つからないでしょう。

結果として、オブジェクトがセットのメンバーである間に、オブジェクトのハッシュコード契約が破られた場合、HashSetは異常に動作します。ハッシュコードの

「一般的な契約です：

• ---

  ここで（java.jang.Object＃ハッシュコードは（）を参照）は、Java 7 javadocが言っていることですJavaアプリケーションの実行中に同じオブジェクトに対して複数回呼び出されると、常にhashCodeメソッドは同じ整数を返さなければなりません。ただし、eqオブジェクトの比較が変更されます。この整数は、アプリケーションの1回の実行から同じアプリケーションの別の実行まで一貫している必要はありません。

• ...

は "何の情報を提供していない..."の注意点は、私を困惑。私は、オブジェクトハッシュコードがハッシュテーブルにある間に変更されないようにするルールもある場合にのみ機能すると思います。残念ながら、このルールは、あなたが探している場所には記載されていません。ドキュメントのバグ？

---

おそらく、ハッシュコードを「口頭契約」に変更しないという要件を呼ぶべきですか？:-)

Answer 3

オブジェクトをHashSetに挿入した後で値を変更すると、データ構造の整合性が損なわれます。その後、その仕事に頼ることはできません。

マップの値として可変オブジェクトを使用することは、一般的には悪い考えです。幸いにも、この目的のために最も一般的に使用されるクラス（String,Integer）は不変です。

Answer 4

これは、HashSetとHashMapsのキーとして可変オブジェクトを使用しないでください。

最初のイテレータは、hashCode 5でRオブジェクトを返しました。次に、そのオブジェクトのプロパティを変更しました（count）。しかし、ハッシュを強制的に再計算する必要はありません。したがって、HashSetに関する限り、カウントを-3に変更したオブジェクトは、ハッシュコード5に対応するバケットに残ります。次に、ハッシュコード-3に対応するバケットにあるオブジェクトを削除しました。元のR（-3）オブジェクトでした。その操作の後、バケットにハッシュコード-3のオブジェクトがないので、contains(new R(-3))はfalseを返します。あなたはハッシュセットに要素を追加するとき