HashTableは同じキーを複数の値にマップできることを読んだ。それが衝突です。なぜ私の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
のですか？その後、衝突はどこにありますか？
衝突はありません。 HashTableエントリは、キーを1つの値にマップします。
あなたのサンプルの3行目：
hTable.put("a", "ab");
がaからabへのマッピングでaaにaからのマッピングを置き換えます。
コードの実行が完了した後、hTableには、a〜abの1つのマッピングしかありません。
内部ではが発生します。です。 ユーザには、が透過的に解決されます（）。
ハッシュテーブルは辞書になることができます。これは、各キーを正確に1つの値にマッピングします。 2つ以上の値にマッピングされている場合は、辞書ではありません。
+1は衝突が内部のものであることを指摘しています。あなたの第2段落の文言はちょっと変わったようです。衝突を透過的に解決するため、辞書ではありません。 –
@Laurence：私は同意する、1秒 – Mehrdad
ハッシュテーブルは、同じキーを複数の値にマップしません。衝突は、複数のキーが同じハッシュ値にマップされる可能性があります。それはあなたにトランスペアレントなデータ構造自体によって解決されます。
hTable.get（ "a"）でaaとabを取得する場合は、Dictionary<String,List<String>>を作成し、同じキーの値を追加する必要があります。あなたのコードで
hTable.put("a", "aa");
hTable.put("a", "ab");
キーは同じです。したがって、2番目の操作では "ab"を使用して "aa"を上書きしました。だからこそあなたは「ab」だけを得るのです。
大丈夫、それは意味： "複数のキーが同じハッシュ値にマップされる可能性がある"私は思ったキーが同じで、ハッシュ値も同じだと思った。私は正しい？ – user900721
はい、あなたは正しいです。しかし、キーが同じでなくても、ハッシュ値は同じになる可能性があります。それはいわゆる「衝突」です。 –
Okパーフェクト。私は理解した。ありがとう！次に起こることは、衝突の場合、どの値を取得しなければならないかをどのように知っているか？ – user900721
HashTableはKey - > Valueマッピングです。つまり、複数のキーに対して複数の値を設定することはできません。 2つのデータ構造を結合して、複数の値を1つのキーに格納する必要があります。
たとえば、 あなたは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
データ構造とアルゴリズムの基本を踏襲することを強くお勧めします。
キーで値を取得する必要があります。配列はこの目的を果たしますが、整数キーを使用することに制限されており、余分なスペースを使用する可能性があります（0と1000の位置にのみ値を格納すると考えると、配列全体を2つの要素に割り当てる必要があります）。
ハッシュテーブルは、これらの問題の両方を解決します。これは、ハッシュ（bytes_1）==ハッシュ（bytes_2）があることを意味しますが、が頻繁に発生しません。があり、ハッシュが異なる場合はbytes_1〜bytes_2です。
衝突は、2つのキーが同じハッシュを持つことを意味します。map.put("key1", "value1"); map.put("key2", "value2") key1とkey2が同じリンクリストに巻き込まれる可能性があります。
衝突は内部実装の詳細であり、2つのキーが同じ方法でハッシュしたときに、同じキーが複数回使用されたときではありません。 @Mehrdadが指摘しているように、それらは透過的に解決されます（モジュロパフォーマンスの低下）。そうでない場合は、単一のキーの複数の値ではなく、他のキー（同じ表のセルにハッシュされたキー）によって不思議に上書きされるキーがあります。 –
@Lauenece：私は1）2つのキーが同じ方法でハッシュするときに行う必要がある2）1つのキーの複数の値ではなく、他のキーで不思議なように上書きされるキー。もう少し説明してください。 – user900721
私は本当にそれをコメントの空間にはっきりと説明することはできません。良いアルゴリズムの本や、おそらくWikipediaの記事http://en.wikipedia.org/wiki/Hash_tableのハッシュテーブルについて読んでみてください。これらは実装の詳細です。 'Hashtable'クラスを*使用するだけの場合は、これらの詳細を知る必要はありません。インタフェース/契約を理解するだけです。 'Hashtable'は' Dictionary'を拡張して 'Dictionary'の契約に従い、' Dictionary'の文書は '任意の' Dictionary'オブジェクトの中で、全てのキーが最大一つの値に関連していると言います。 –