86

JavaHashMapはputメソッドを使用して K/V ペアを に挿入しHashMapます。putメソッドを使用して、 as 10 とas 17HashMap<Integer, Integer>のエントリが 1 つあるとします。keyvalue

これに 10,20 を挿入するHashMapと、同じキー 10 による衝突のため、前のエントリがこのエントリに置き換えられます。

キーが衝突するHashMapと、古い K/V ペアが新しい K/V ペアに置き換えられます。

だから私の質問は、HashMap連鎖衝突解決技術をいつ使用するのですか?

linkedlistキーが 10、値が 17,20の a を形成しなかったのはなぜですか?

4

9 に答える 9

125

ペアを挿入してから を挿入する(10, 17)と、(10, 20)技術的に衝突は発生しません。特定のキーの古い値を新しい値に置き換えるだけです10(どちらの場合も、10 は 10 に等しく、10 のハッシュ コードは常に 10 であるため)。

複数のキーが同じバケットにハッシュされると、衝突が発生します。その場合、それらのキーを区別できるようにする必要があります。連鎖衝突解決は、これに使用される技術の 1 つです。

例として、2 つの文字列"abra ka dabra"およびがそれぞれ"wave my wand"ハッシュ コード100およびを生成するとし200ます。配列の合計サイズが 10 であると仮定すると、それらは両方とも同じバケット (100 % 10および200 % 10) になります。チェーン化により、 を実行するたびmap.get( "abra ka dabra" );に、キーに関連付けられた正しい値が得られます。Java のハッシュ マップの場合、これはequalsメソッドを使用して行われます。

于 2013-10-30T19:20:45.260 に答える
32

キーでは、メソッドをHashMap含むオブジェクトです。hashCode()equals(Object)

Map に新しいエントリを挿入すると、hashCodeが既に認識されているかどうかがチェックされます。次に、このハッシュコードを使用してすべてのオブジェクトを反復処理し、それらが等しいかどうかをテストし.equals()ます。等しいオブジェクトが見つかった場合、古い値が新しい値に置き換えられます。そうでない場合は、マップに新しいエントリが作成されます。

通常、マップについて言えば、2 つのオブジェクトが同じであるが異なる場合に衝突を使用します。hashCodeそれらは内部的にリストに保存されます。

于 2013-10-30T19:22:26.050 に答える
9

実際、リンクされたリストを形成できた可能性があります。Map契約でエントリを置き換える必要があるだけです。

V put(K key, V value)

指定された値をこのマップ内の指定されたキーに関連付けます (オプションの操作)。マップに以前にキーのマッピングが含まれていた場合、古い値は指定された値に置き換えられます。(マップ m は、m.containsKey(k) が true を返す場合にのみ、キー k のマッピングを含むと言われます。)

http://docs.oracle.com/javase/6/docs/api/java/util/Map.html

値のリストを格納するマップの場合、Multimap. Google は次のとおりです: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Map に似たコレクションですが、複数の値を 1 つのキーに関連付けることができます。同じキーで異なる値を指定して put(K, V) を 2 回呼び出すと、マルチマップにはキーから両方の値へのマッピングが含まれます。

編集：衝突の解決

それは少し違います。衝突は、2 つの異なるキーがたまたま同じハッシュ コードを持つ場合、または異なるハッシュ コードを持つ 2 つのキーが基になる配列の同じバケットにマッピングされる場合に発生します。

のソースを検討してくださいHashMap（ビットとピースを削除）：

public V put(K key, V value) {
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // i is the index where we want to insert the new element
    addEntry(hash, key, value, i);
    return null;
}

void addEntry(int hash, K key, V value, int bucketIndex) {
    // take the entry that's already in that bucket
    Entry<K,V> e = table[bucketIndex];
    // and create a new one that points to the old one = linked list
    table[bucketIndex] = new Entry<>(hash, key, value, e);
}

EntryのクラスがどのHashMapようにしてリストのように振る舞うかに興味がある人は、 が を実装HashMapする独自の静的Entryクラスを定義していることがわかりますMap.Entry。ソースコードを表示すると、自分で確認できます。

HashMap の GrepCode

于 2013-10-30T19:21:41.963 に答える
2

衝突と重複には違いがあります。衝突は、ハッシュコードとバケットが同じであることを意味しますが、重複すると、同じハッシュコード、同じバケットになりますが、ここでは equals メソッドが表示されます。

衝突が検出され、既存のキーに要素を追加できます。ただし、重複の場合は新しい値に置き換えられます。

于 2017-01-04T21:54:28.410 に答える
1

あなたの例には衝突はありません。同じキーを使用するため、古い値は新しい値に置き換えられます。ここで、同じハッシュ コードにマップされる 2 つのキーを使用すると、衝突が発生します。しかし、その場合でも、HashMap が値を置き換えます! 衝突が発生した場合に値を連鎖させたい場合は、リストを値として使用するなどして、自分で行う必要があります。

于 2013-10-30T19:20:53.930 に答える
1

そうすることは定義されていません。この機能を実現するには、キーを値のリストにマップするマップを作成する必要があります。

Map<Foo, List<Bar>> myMap;

または、 Google コレクション/グアバ ライブラリの Multimap を使用することもできます

于 2013-10-30T19:20:57.367 に答える