java - HashMap を使用して HashSet を実装する際の問題はありますか?

Question

Java では、HashSet は HashMap を使用して実装されます。そのため、アイテムをセットに追加すると、次のコードが実行されます。

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

異なるが等しいハッシュを持つ 2 つのオブジェクトが HashSet に追加されるとどうなるか。それ（HashSet）には両方のオブジェクトが含まれますか、それとも何が起こりますか？

score 5 · Accepted Answer

hashmap は.equals()と同様に使用します.hash()。.equals()true を返さない限り、2 つのことは同じではありません。同じことがハッシュセットにも当てはまります。

そのため、2 つのオブジェクトが異なるが同じハッシュを持つ場合、それらは両方とも格納され、両方とも利用可能になり.equals()ますfalse。

内部的には、オブジェクトを格納する場所を決定するためにハッシュが使用されることは事実ですが、同じハッシュを持つ複数のオブジェクトを格納することもできます (複雑になるため、パフォーマンスがわずかに低下しますが、それだけです)。

score 1 · Accepted Answer

はい、ハッシュマップには両方の要素が含まれます。使用する特定の方法は見つかりませんが、衝突に対処する一般的な方法には、各バケットにリンクされたリストを使用する方法や、近くの空のバケットに要素を貼り付ける方法などがあります。

2 に答える 2