2 つの等しくないオブジェクトが同じハッシュコードを持つ可能性があることは、私の理解です。HashMap Java から追加または取得するときに、これはどのように処理されますか?
5 に答える
それらは同じバケットに追加されるだけで、equals()
それらを区別するために使用されます。各バケットには、同じハッシュ コードを持つオブジェクトのリストを含めることができます。
理論的には、指定されたクラスの任意のオブジェクトのハッシュ コードと同じ整数を返すことができますが、それは、ハッシュ マップのすべてのパフォーマンス上の利点を失い、事実上、オブジェクトをリストに格納することを意味します。
HashMap では、キーとその連想値がバケット内のリンクされたリスト ノードに格納され、キーは基本的にハッシュコードではなく equals() メソッドを使用してハッシュマップで比較されます。
hm.put("a","aValue"); // Suppose hashcode created for key "a" is 209
hm.put("b","bValue"); // Here hashcode created for key "b" is 209 as well.
a.equals(b)
返品の場合true
、bValue
交換aValue
して返品bValue
いたします。a.equals(b)
が返された場合false
、バケット リストに別のノードが作成されるため、呼び出すと、 since isget("b")
が取得されます。bValue
a.equals(b)
false
その場合、IdentityHashMap を使用できます。この場合、同じハッシュを持つ異なるオブジェクトは、ID に基づいて異なると見なされます。
2 つの等しくないオブジェクトのハッシュ値が同じである場合、両方のオブジェクトが同じスロット (バケットと呼ばれることもあります) に配置される必要があるため、ハッシュ テーブルで衝突が発生します。ハッシュ アルゴリズムは、このような衝突を解決する必要があります。大学のアルゴリズム コースの薄れつつある記憶を振り返ると、これを行うための 3 つの基本的な方法を思い出すことができます。
- ハッシュ テーブルで次の空のスロットを探し、そこにオブジェクトを配置します。長所: 実装が簡単、短所: オブジェクトのクラスタリングが発生し、パフォーマンスが低下する可能性がある、容量を超える可能性がある
- 競合が発生した場合に使用する二次ハッシュ関数を用意します: 長所: 通常は高速、短所: 2 番目のハッシュ関数を作成する必要があり、それでも衝突が発生する可能性があり、容量を超える可能性があります
- ハッシュ テーブルの競合するスロットからオブジェクトのリンク リストを作成します。長所/短所: 通常、適切なハッシュ関数と負荷係数に対して高速ですが、最悪の場合、線形検索に低下する可能性があります
Java ハッシュ クラスは 3 番目の方法を使用していると思いますが、組み合わせアプローチを使用する可能性があります。ただし、適切なハッシュの鍵は、ハッシュ テーブルに十分な容量があることを確認し、適切なハッシュ関数を作成することです。保持しているオブジェクトと同じ数のバケットしか持たないハッシュ テーブルでは、競合が発生する可能性があります。通常、ハッシュ テーブルは格納するオブジェクト数の約 2 倍の大きさにする必要があります。Java の HashMap は必要に応じて拡張されますが、必要に応じて初期容量と負荷係数を与えることができます。
ハッシュ関数はプログラマ次第です。すべてのオブジェクトに対して 0 を返すこともできますが、それはハッシュ (ストレージと取得の両方) が O(1) ではなく O(n) になることを意味します... または、簡単に言えば、犬が遅くなります。
参照: http://www.coderanch.com/t/540275/java/java/objects-hashcode-HashMap-retrieve-objects