Java Hashtableクラス - これは私の思うように動作しますか？特定の質問が含まれています

Question

私が書いたNodeというクラスがあります。 Nodeの2つのフィールド（私のhashCode（）関数に影響を与えない3番目のフィールドもあります）を考慮に入れて、hashCode（）関数をオーバーライドします。私は3つのフィールドをすべて考慮するequals（）関数も書きました。

私は、新しいノードがハッシュテーブル内のものと重複しているかどうかを、新しいノードを作成するときに簡単に確認できるように、Hashtableクラスを使ってノードを格納しようとしています。これまでのところ私はこの

Hashtable<Node,Node> hashTbl = new Hashtable<Node,Node>(); 
... 
Node node1 = // some new node 
hashTbl.put(node1,node1); 
... 

はだから今、私がnode1とまったく同じハッシュ値を持っていますが、等号（）メソッドで定義されたノード1に等しくないnode2という新しいノードを作ると言っています。私はnode2がハッシュテーブル内の何かの重複（それではない）かどうかをチェックしたいが、もし私がconstainsKey（）を使うなら、それは私に偽陽性を与えないだろうか？ containsValue（）を使うことは、ハッシュテーブルの効率を利用していないようです。だから私はこれをいかに効率的に行うことができますか？

また、私はhashTbl.put（arg1、arg2）を呼び出すと、arg1のhashCode（）関数を呼び出し、その値を使ってarg2を配置する「配列」内のインデックスを探します。この権利？

ご迷惑をおかけして申し訳ありません。誰にもありがとう。

Answer 1

最初に、ハッシュテーブル以外のHashSet（または同様のもの）が必要な場合があります。ハッシュテーブルではなく、メンバーシップをチェックするだけです.HashSetを使用すると、すべてのキーに値を指定する必要はありません。

あなたの質問に答えるために、値が入力される配列内のどのスロットが決定されますが、すべてのスロットは実際にリンクされたリストです。新しいキーがリンクリストの他のどのキーとも.equalでない場合、新しいキーと値はリンクされたリスト内の自分のノードに入れられます。すべてのオブジェクトに対して1を返すだけで、完全に合法であり、正しい.hashcodeの実装です。この実装の唯一の問題は、ハッシュテーブルや類似のデータ構造をリンクリストに変換することです（明らかに、ハッシュテーブルのすべてのパフォーマンス上の利点を失うことになります）。

要するに、.hashcodeメソッドは正常に動作します。 .equalではない多数のオブジェクトを配置すると、同じハッシュコードを持つ場合、パフォーマンスは低下しますが、コードは引き続き正しく機能します。

Answer 2

あなたは、本質的に正しい：ハッシュテーブルは（ところで、HashMapは、新しい、より推奨クラスである）で、あなたのオブジェクトを置くためにバケツを見つけることhashCode()を使用して衝突（同じバケット内の別のオブジェクトが）がある場合、それは。 equals(Object)を使用して、この新しいオブジェクトが既にハッシュ内のオブジェクトの1つと等しいかどうかを調べる（またはルックアップキーがキーと値のペアの1つに一致するかどうかを調べるために）各バケット内のリストを使用します。したがって、すべての衝突の最悪の場合、ハッシュはO（N）操作のリストに変わります。あなたが指摘しているように、これは非効率的です。

あなたのequals(Object)が正しい限り、機能的な問題はありません。あなたのhashCodeが多すぎる競合を生成する場合、効率の問題です。基本的に、2つのオブジェクトが等しい場合、それらは正しいために同じhashCodeを持つ必要があります。 2つのオブジェクトが等しくない場合、ハッシュ効率のために異なるハッシュコードを持つ必要があります。

Answer 3

HashTable（またはHashMap）にはN個のビンが含まれています。ビンは複数のオブジェクトを保持できます。 （各ビンは実質的にMap.Entryのリンクされたリストです）。キーのhashCode（）は、ビンを決定するために使用されます。しかし、ビンを決定した後、キーにequals（）を使用して、キーが既に存在するかどうかを確認します。したがって、node1とnode2をHashTableに入れ、両方が同じhashCode（）であるが等しくない場合、それらは同じビンに入りますが、そのビンは2つのキーnode1を持つ長さ2のリンクリストになりますノード2、および対応する値が含まれます。

containsKey（）は、hashCode（）を使用してビンを検索しますが、そのビンのすべてのキーでequalsを実行するため、誤検出をしません。束のキーに同じhashCodeを持たせると、HashTableが遅く非効率的になります（実際には、すべての値が同じhashCodeを持つ場合、リンクされたリストに格納されます）。