2

HashTable は同じキーを複数の値にマップできることを読みました。それが衝突です。

今、私はこのようにプログラムを実行します:

Dictionary<String,String> hTable = new Hashtable<String,String>();
hTable.put("a", "aa");
hTable.put("a", "ab");
System.out.println(""+hTable.get("a"));

私の考えでは、 と を取得する必要がaaありabます。

しかし、実際の出力はab

なぜそうなのですか？その場合、衝突はどこにありますか？

4

5 に答える 5

3

衝突はありません。HashTable エントリは、キーを 1 つの値のみにマップします。

サンプルの 3 行目:

hTable.put("a", "ab");

からへのマッピングを からaへのマッピングに置き換えます。aaaab

4 行のコードの実行が完了すると、tohTableのマッピングが 1 つだけになります。aab

于 2011-08-20T04:29:25.193 に答える
3

衝突は内部でのみ発生します。ユーザーにとっては、透過的に解決されます。

そのため、ハッシュテーブルはディクショナリになることができます。各キーを正確に 1 つの値にマップします。複数の値にマップされている場合、辞書にはなりません。

于 2011-08-20T04:30:49.317 に答える
2

HashTable はキー -> 値のマッピングです。つまり、複数のキーに対して複数の値を持つことはできません。複数の値を 1 つのキーに格納する 2 つのデータ構造を組み合わせる必要があります。

たとえば、HashTable 内に linkList を配置できます。例えば

HashTable<String,LinkedList<String>> table = new HashTable();
LinkedList<String> list = new LinkedList();
list.add("aa");
list.add("ab");
table.add("a",list);

これで、 aaとabの値を取得できます。

table.get("a").get(0); // returns aa
table.get("a").get(1); // returns ab

データ構造とアルゴリズムの基本を確認することを強くお勧めします。

于 2011-08-20T05:00:07.837 に答える
2

Hashtable は、同じキーを複数の値にマップしません。衝突とは、複数のキーが同じハッシュ値にマップされる可能性があることです。これは、透過的なデータ構造自体によって解決されます。

hTable.get("a") で aa と ab を取得したい場合Dictionary<String,List<String>>は、同じキーの値を持つリストを作成して追加する必要があります。

あなたのコードで

hTable.put("a", "aa");
hTable.put("a", "ab");

キーは同じです。したがって、2 番目の操作では、「aa」をオーバーライドするために「ab」を使用しました。そのため、「ab」しか取得できません。

于 2011-08-20T04:31:50.967 に答える
1

You want to retrieve values by their keys. An array serves this purpose but is restricted to using integer keys and may use too much space (think about storing values at position 0 and 1000 only, you have to allocate the entire array for 2 elements).

HashTables solve both of these problems with:

  • a dispersive non-injective function that converts an array of bytes of variable length in a fixed length array of bytes. This means that you have hash(bytes_1) == hash(bytes_2) but it doesn't happen too often and if bytes_1 ~ bytes_2 the hashes are different;
  • an index of used hashes. If the function returns an array of 10 bytes you have 2^80 possibilities, so you need to keep a sorted list of the hashes that you already encountered;
  • an array of linked lists. The index of hashes maps the hash with the position in the array.

The collision means that two keys have the same hash: map.put("key1", "value1"); map.put("key2", "value2") key1 and key2 might wind up in the same linked list.

于 2011-08-20T06:09:20.707 に答える