java - ハッシュ関数とキー

Question

Kathy Sierra の本を読んでいるときに、次のコードの断片に出くわしました。

m.put("k1", new Dog("aiko"));   // add some key/value pairs
m.put("k2", Pets.DOG);
m.put(Pets.CAT, "CAT key");
Dog d1 = new Dog("clover");
m.put(d1, "Dog key");
m.put(new Cat(), "Cat key");

マップは、キーと値の形式でデータを格納するために使用されます。キーとして「k1」または new Cat() を入力すると、キーに実際に何が格納されるのか誰か教えてくれませんか? これらのオブジェクトへの参照は保存されていますか、それともハッシュコードの値ですか? 私はこれと完全に混乱しています。ご意見をお聞かせください。

さらに詳しい資料を教えていただければ幸いです。

score 2 · Accepted Answer

マップはN個のバケットの配列です。

このput()メソッドは、キーを呼び出すことから始まりhashCode()ます。このハッシュコードから、モジュロを使用してマップ内のバケットのインデックスを取得します。

次に、見つかったバケットに関連付けられたリンクリストに格納されているエントリを繰り返し処理し、equals()メソッドを使用して各エントリキーをキーと比較します。

1つのエントリに自分のキーと等しいキーがある場合、その値は新しい値に置き換えられます。それ以外の場合は、新しいキーと新しい値を使用して新しいエントリが作成され、バケットに関連付けられたリンクリストに保存されます。

CatインスタンスとStringインスタンスが等しくなることはないため、Stringキーに関連付けられた値が、Catキーに関連付けられた値を配置することによって変更されることはありません。

score 0 · Accepted Answer

HashMap が使用される場合、その中のキーは一意です。このキーの一意性は、検討中のオブジェクトのクラスが提供する equals() および hashCode() メソッドの定義から Java でチェックされます。

これは、最初に equals() メソッドを使用して比較し、それが等しい場合は hashCode() を使用して比較することによって行われます。同じオブジェクト。

したがって、 equals() テストに合格すると、マップには一意のキーが必要なため、オブジェクトはマップに挿入されません。したがって、マップのキーであるオブジェクトの各 hashCode 値は、hashCode 値の範囲に対して異なるバケットを形成し、オブジェクトはそれに応じてグループ化されます。

例を提供するために編集します。

たとえば、2 つのオブジェクトが値 "hello" と "hlleo" を持つ String 属性を持ち、オブジェクトのハッシュコードが文字の ASCII 値の合計になるように hashCode() 関数がプログラムされているとします。 String 属性と equals() メソッドは、String 属性の値が等しい場合に true を返します。

したがって、上記の場合、equals() は文字列が等しくないため false を返しますが、hashCode は同じになります。したがって、2 つのオブジェクトは同じハッシュコードバケットに配置されます。

それが役立つことを願っています。

score 0 · Accepted Answer

オブジェクトによって定義されます。

hashCode() と equals() メソッドを作成して、ハッシュテーブルに格納できるようにする必要があります。

合理的に実用的である限り、クラス Object によって定義された hashCode メソッドは、個別のオブジェクトに対して個別の整数を返します。(これは通常、オブジェクトの内部アドレスを整数に変換することによって実装されますが、この実装手法は JavaTM プログラミング言語では必要ありません。)

java.lang.Object の javadoc を参照してくださいhttp://docs.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode ()

または、説明のためにこれを読むことができます http://www.javaworld.com/javaworld/javaqa/2002-06/01-qa-0621-hashtable.html

役立つことを願っています