私の理解では、次のように思います。
私は正しいですか？
正しければ、次の質問HashMapがあります。オブジェクトのハッシュコードを内部的に使用します。では、2 つのオブジェクトが同じハッシュコードを持つことができる場合、どのHashMapキーを使用するかを追跡するにはどうすればよいでしょうか?
HashMapオブジェクトのハッシュコードを内部で使用する方法を誰かが説明できますか?
ハッシュマップは次のように機能します (これは少し単純化されていますが、基本的なメカニズムを示しています)。
キーと値のペアを格納するために使用する「バケット」がいくつかあります。各バケットには一意の番号があり、それがバケットを識別します。キーと値のペアをマップに入れると、ハッシュマップはキーのハッシュ コードを調べ、キーのハッシュ コードを識別子とするバケットにペアを格納します。例: キーのハッシュ コードは 235 -> ペアはバケット番号 235 に格納されます (1 つのバケットに複数のキーと値のペアを格納できることに注意してください)。
ハッシュマップでキーを指定して値を検索すると、指定したキーのハッシュ コードが最初に調べられます。次に、ハッシュマップは対応するバケットを調べ、与えられたキーとバケット内のすべてのペアのキーを比較しますequals()。
これで、これがマップ内のキーと値のペアを検索するのに非常に効率的であることがわかります。キーのハッシュ コードによって、ハッシュマップは検索対象のバケットをすぐに認識できるため、そのバケットの内容に対してテストするだけで済みます。
上記のメカニズムを見ると、キーのhashCode()およびequals()メソッドに必要な要件もわかります。
2 つのキーが同じ (比較するとequals()が返さtrueれる) 場合、それらのhashCode()メソッドは同じ数値を返す必要があります。キーがこれに違反すると、等しいキーが異なるバケットに格納される可能性があり、ハッシュマップはキーと値のペアを見つけることができなくなります (同じバケットを検索するため)。
2 つのキーが異なる場合、それらのハッシュ コードが同じかどうかは問題ではありません。ハッシュコードが同じ場合、それらは同じバケットに格納されます。この場合、ハッシュマップを使用equals()してそれらを区別します。
あなたの 3 番目の主張は正しくありません。
2 つの等しくないオブジェクトが同じハッシュ コードを持つことは完全に合法です。これは、マップが指定されたキーで可能なエントリをHashMapすばやく見つけることができるように、「最初のパス フィルター」として使用されます。次に、同じハッシュ コードを持つキーが、指定されたキーと等しいかどうかがテストされます。
2 つの等しくないオブジェクトが同じハッシュ コードを持つことができないという要件は望ましくありません。(また、他のクラスが同じハッシュを生成する可能性があるため、異なる型がオブジェクトのフィールドを使用してハッシュ コードを生成することさえできないことも意味します。)
HashMapEntryオブジェクトの配列です。
HashMapオブジェクトの単なる配列と考えてください。
これが何であるかを見てくださいObject：
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
…
}
各Entryオブジェクトはキーと値のペアを表します。バケットに複数の がある場合、フィールドnextは別のオブジェクトを参照します。EntryEntry
2 つの異なるオブジェクトのハッシュ コードが同じである場合があります。この場合、2 つのオブジェクトが 1 つのバケットに保存され、リンクされたリストとして表示されます。エントリ ポイントは、最近追加されたオブジェクトです。このオブジェクトは、nextフィールドなどを持つ別のオブジェクトを参照します。最後のエントリは を参照していnullます。
HashMapデフォルトのコンストラクタでを作成する場合
HashMap hashMap = new HashMap();
アレイは、サイズ 16 およびデフォルトの 0.75 ロード バランスで作成されます。
hash % (arrayLength-1)要素を配置する位置 (バケット番号) を計算するHashMap値が上書きされます。バケットに少なくとも 1 つの要素が既にある場合、新しい要素が追加され、バケットの最初の位置に配置されます。そのnextフィールドは古い要素を参照します。
hash % (arrayLength-1)Entry。目的の要素が見つからない場合は、戻りますnull http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.htmlで優れた情報を見つけることができます。
要約する：
HashMap はハッシュの原理に基づいて動作します
put(key, value): HashMap は、キーと値の両方のオブジェクトを Map.Entry として格納します。Hashmap は hashcode(key) を適用してバケットを取得します。衝突がある場合、HashMap は LinkedList を使用してオブジェクトを格納します。
get(key): HashMap はキー オブジェクトのハッシュコードを使用してバケットの場所を見つけ、keys.equals() メソッドを呼び出して LinkedList 内の正しいノードを識別し、Java HashMap 内のそのキーに関連付けられた値オブジェクトを返します。
ハッシュコードは、ハッシュマップがチェックするバケットを決定します。equals()バケットに複数のオブジェクトがある場合は、( ) メソッドを使用して、バケット内のどのアイテムが目的のアイテムに等しいかを見つけるために線形検索が行われます。
つまり、完全なハッシュコードがあれば、ハッシュマップへのアクセスは一定であり、バケットを反復処理する必要はありません (技術的には、MAX_INT バケットも必要です。Java 実装は、同じバケット内のいくつかのハッシュ コードを共有して、スペース要件を削減します)。最悪のハッシュコード (常に同じ数値を返す) を持っている場合、マップ内のすべてのアイテム (それらはすべて同じバケット内にあります) を検索して必要なものを取得する必要があるため、ハッシュマップへのアクセスは直線的になります。
ほとんどの場合、適切に作成されたハッシュコードは完全ではありませんが、多かれ少なかれ一定のアクセスを提供するのに十分なほど一意です。
You're mistaken on point three. Two entries can have the same hash code but not be equal. Take a look at the implementation of HashMap.get from the OpenJdk. You can see that it checks that the hashes are equal and the keys are equal. Were point three true, then it would be unnecessary to check that the keys are equal. The hash code is compared before the key because the former is a more efficient comparison.
If you're interested in learning a little more about this, take a look at the Wikipedia article on Open Addressing collision resolution, which I believe is the mechanism that the OpenJdk implementation uses. That mechanism is subtly different than the "bucket" approach one of the other answers mentions.
import java.util.HashMap;
public class Students {
String name;
int age;
Students(String name, int age ){
this.name = name;
this.age=age;
}
@Override
public int hashCode() {
System.out.println("__hash__");
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
System.out.println("__eq__");
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Students other = (Students) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
public static void main(String[] args) {
Students S1 = new Students("taj",22);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Output:
__ hash __
116232
__ hash __
116201
__ hash __
__ hash __
2
ここで、オブジェクト S1 と S2 の両方が異なるコンテンツを持っている場合、オーバーライドされた Hashcode メソッドが両方のオブジェクトに対して異なる Hashcode(116232,11601) を生成することはほぼ確実です。異なるハッシュ コードがあるため、今は EQUALS メソッドを呼び出す必要さえありません。異なるハッシュコードは、オブジェクト内の異なるコンテンツを保証するためです。
public static void main(String[] args) {
Students S1 = new Students("taj",21);
Students S2 = new Students("taj",21);
System.out.println(S1.hashCode());
System.out.println(S2.hashCode());
HashMap<Students,String > HM = new HashMap<Students,String > ();
HM.put(S1, "tajinder");
HM.put(S2, "tajinder");
System.out.println(HM.size());
}
}
Now lets change out main method a little bit. Output after this change is
__ hash __
116201
__ hash __
116201
__ hash __
__ hash __
__ eq __
1
We can clearly see that equal method is called. Here is print statement __eq__, since we have same hashcode, then content of objects MAY or MAY not be similar. So program internally calls Equal method to verify this.
Conclusion
If hashcode is different , equal method will not get called.
if hashcode is same, equal method will get called.
Thanks , hope it helps.
2 つのオブジェクトが等しい場合は、ハッシュコードが同じであることを意味しますが、その逆ではありません。
2 つの等しいオブジェクト ------> 同じハッシュコードを持つ
2 つのオブジェクトが同じハッシュコード ----xxxxx を持っています --> それらは等しくありません
HashMap の Java 8 更新 -
コードでこの操作を行います-
myHashmap.put("old","old-value");
myHashMap.put("very-old","very-old-value");
したがって、ハッシュコードが両方のキーに対して返され、同じ"old"であるとします"very-old"。それからどうなるでしょう。
myHashMapは HashMap であり、最初にその容量を指定しなかったとします。したがって、Java のデフォルトの容量は 16 です。新しいキーワードを使用してハッシュマップを初期化するとすぐに、16 個のバケットが作成されます。最初のステートメントを実行したとき-
myHashmap.put("old","old-value");
次に、ハッシュコード"old"が計算され、ハッシュコードも非常に大きな整数になる可能性があるため、Javaは内部的にこれを行いました-（ハッシュはここのハッシュコードで、>>>は右シフトです）
hash XOR hash >>> 16
より大きな図として示すと、0 から 15 の間のインデックスが返されます。これで、キー"old"と値のペア"old-value"が Entry オブジェクトのキーと値のインスタンス変数に変換されます。次に、このエントリ オブジェクトがバケットに格納されます。または、特定のインデックスで、このエントリ オブジェクトが格納されると言えます。
参考までに- Entry は Map インターフェイスのクラスです- Map.Entry、これらの署名/定義
class Entry{
final Key k;
value v;
final int hash;
Entry next;
}
次のステートメントを実行すると、
myHashmap.put("very-old","very-old-value");
と"very-old"同じハッシュコードを与える"old"ため、この新しいキーと値のペアは同じインデックスまたは同じバケットに再度送信されます。ただし、このバケットは空ではないためnext、Entry オブジェクトの変数を使用して、この新しいキーと値のペアを格納します。
これは、同じハッシュコードを持つすべてのオブジェクトの連結リストとして保存されますが、TRIEFY_THRESHOLD は値 6 で指定されます。したがって、これに達すると、連結リストは最初の要素を根。
各 Entry オブジェクトは、キーと値のペアを表します。バケットに複数のエントリがある場合、Field next は他のエントリ オブジェクトを参照します。
2 つの異なるオブジェクトの hashCode が同じである場合があります。この場合、2 つのオブジェクトが 1 つのバケットに保存され、LinkedList として表示されます。エントリ ポイントは、最近追加されたオブジェクトです。このオブジェクトは、次のフィールドなどを持つ他のオブジェクトを参照します。最後のエントリが null を参照しています。デフォルトのコンストラクターで HashMap を作成する場合
アレイは、サイズ 16 とデフォルトの 0.75 ロード バランスで作成されます。
HashMap がどのように機能するかについては詳しく説明しませんが、現実に関連付けることで HashMap がどのように機能するかを思い出すことができるように、例を示します。
Key、Value、HashCode、およびバケットがあります。
しばらくの間、それぞれを次のように関連付けます。
Map.get(key) の使用:
スティービーは、VIP 社会の別荘に住んでいる友人 (ジョス) の家に行きたいと思っています。Josse の住所は彼の SSN です (これは人によって異なります)。SSN に基づいて協会の名前を見つけるためのインデックスが維持されています。このインデックスは、HashCode を見つけるためのアルゴリズムと見なすことができます。
Map.put(key,Value) の使用
これは、HashCode を見つけることによってこの値に適した社会を見つけ、値が保存されます。
これがお役に立てば幸いです。これは変更可能です。
ハッシュ マップはハッシュの原理に基づいて動作します
HashMap get(Key k) メソッドは、キー オブジェクトの hashCode メソッドを呼び出し、返された hashValue を独自の静的ハッシュ関数に適用して、キーと値が Entry (Map.エントリー）。したがって、前の行から、キーと値の両方がエントリ オブジェクトの形式としてバケットに格納されていると結論付けました。そのため、バケツに値だけが格納されていると考えるのは正しくなく、面接官に良い印象を与えることはありません。
key が null の場合、Null キーは常にハッシュ 0、つまりインデックス 0 にマップされます。
key が null でない場合、キー オブジェクトで hashfunction が呼び出されます。上記のメソッドの 4 行目、つまり key.hashCode() を参照してください。したがって、key.hashCode() が hashValue を返した後、4 行目は次のようになります。
int hash = hash(hashValue)
そして今、返された hashValue を独自のハッシュ関数に適用します。
なぜ hash(hashValue) を使用してハッシュ値を再度計算するのか疑問に思うかもしれません。答えは、低品質のハッシュ関数を防御することです。
最終的なハッシュ値を使用して、エントリ オブジェクトが格納されているバケットの場所を見つけます。エントリ オブジェクトは次のようにバケットに格納されます (ハッシュ、キー、値、バケットインデックス)