Warum lässt meine HashTable keine Schlüsselkollisionen zu?

Question

Ich habe gelesen, dass HashTable denselben Schlüssel auf mehrere Werte abbilden kann. Das ist, was Kollision ist.

Jetzt führe ich das Programm wie folgt aus:

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

Mein Denken sagt mir, ich sollte aa y ab .

Die tatsächliche Leistung ist jedoch ab

Warum ist das so? Wo ist dann die Kollision?

Answer 1

Es gibt keine Kollision. Ein HashTable-Eintrag bildet einen Schlüssel auf nur einen Wert ab.

Die dritte Zeile in Ihrem Beispiel:

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

ersetzt das Mapping von a a aa mit einer Abbildung von a a ab .

Nachdem Ihre vier Codezeilen vollständig ausgeführt wurden, hTable hat nur ein Mapping: a a ab .

Answer 2

Eine Kollision findet nur statt intern . Zum Benutzer sind aufgelöst transparent.

Deshalb kann eine Hashtable ein Wörterbuch sein - sie ordnet jeden Schlüssel genau einem Wert zu. Wenn sie auf mehr als 1 Wert abgebildet würde, wäre sie kein Wörterbuch.

Answer 3

Hashtable ordnet nicht denselben Schlüssel mehreren Werten zu. Kollision ist, dass mehrere Schlüssel können auf denselben Hash-Wert abgebildet werden . Sie wird von der Datenstruktur selbst aufgelöst, die für Sie transparent ist.

Wenn Sie aa und ab durch hTable.get("a") erhalten wollen, müssen Sie Dictionary<String,List<String>> und hängen Sie die Liste mit den Werten desselben Schlüssels an.

In Ihrem Code

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

Die Tasten sind die gleichen. Bei der zweiten Operation wurde also "ab" verwendet, um "aa" zu überschreiben. Deshalb erhalten Sie nur "ab".

Answer 4

HashTable ist Schlüssel -> Wert-Zuordnung. Das bedeutet, dass Sie nicht mehrere Werte für mehr als einen Schlüssel haben können. Sie müssen zwei Datenstrukturen kombinieren, um mehrere Werte mit einem Schlüssel zu speichern.

Zum Beispiel, Sie können eine linkList in Ihre HashTable einfügen. Zum Beispiel

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

jetzt können Sie dies tun, indem Sie aa y ab Wert;

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

Ich empfehle Ihnen dringend, sich mit den Grundlagen der Datenstruktur und des Algorithmus vertraut zu machen.

Answer 5

Sie möchten Werte anhand ihrer Schlüssel abrufen. Ein Array erfüllt diesen Zweck, ist aber auf die Verwendung ganzzahliger Schlüssel beschränkt und kann zu viel Platz beanspruchen (denken Sie nur an die Speicherung von Werten an den Positionen 0 und 1000, Sie müssen das gesamte Array für 2 Elemente reservieren).

HashTables lösen diese beiden Probleme mit:

• eine dispersive nicht-injektive Funktion die ein Array von Bytes mit variabler Länge in ein Array von Bytes mit fester Länge umwandelt. Das bedeutet, dass Sie hash(bytes_1) == hash(bytes_2) haben, aber es passiert nicht zu oft und wenn bytes_1 ~ bytes_2 sind die Hashes unterschiedlich;
• einen Index der verwendeten Hashes . Wenn die Funktion ein Array von 10 Bytes zurückgibt, gibt es 2^80 Möglichkeiten, so dass Sie eine sortierte Liste der Hashes führen müssen, auf die Sie bereits gestoßen sind;
• ein Array aus verknüpften Listen . Der Index von Hashes bildet den Hash mit der Position im Array ab.

Die Kollision bedeutet, dass zwei Schlüssel denselben Hash haben: map.put("key1", "value1"); map.put("key2", "value2") Schlüssel1 und Schlüssel2 könnten in derselben verknüpften Liste landen.