Kollisionsauflösung in Java HashMap

Lesezeit: 8 Minuten

Benutzer-Avatar
Benutzer2938723

Java HashMap Verwendet put Methode zum Einfügen des K/V-Paares HashMap. Nehmen wir an, ich habe verwendet put Methode und jetzt HashMap<Integer, Integer> hat einen Eintrag mit key als 10 und value als 17.

Wenn ich hier 10,20 einfüge HashMap es ersetzt einfach den vorherigen Eintrag durch diesen Eintrag aufgrund einer Kollision wegen des gleichen Schlüssels 10.

Wenn der Schlüssel kollidiert HashMap ersetzt das alte K/V-Paar durch das neue K/V-Paar.

Also meine Frage ist wann kommt das HashMap Verwenden Sie die Chaining-Kollisionsauflösungstechnik?

Warum es sich nicht bildete a linkedlist mit Schlüssel als 10 und Wert als 17,20?

  • Hey, wer wertet all diese richtigen Antworten ab? Dieses Verhalten wird schließlich von der Map-Schnittstelle benötigt.

    – Axel

    30. Oktober 2013 um 19:22 Uhr

  • @Axel: Ich denke, das liegt daran, dass die Leute das OP missverstanden haben. Das OP möchte im Grunde wissen, was passiert, wenn mehrere Schlüssel in denselben Bucket gehasht werden. Dann wird die Kollisionsauflösung verwendet. Alle anderen Antworten gehen weiter über Multi-Maps und was nicht …

    – Sanjay T. Sharma

    30. Oktober 2013 um 19:26 Uhr


  • Das OP gibt jedoch explizit das Beispiel an, zwei Elemente mit demselben Schlüssel (10) zu platzieren, und fragt sich, warum nicht beide unterschiedlichen Werte gespeichert werden. Und das ist das Verhalten einer MultiMap.

    – Axel

    30. Oktober 2013 um 19:53 Uhr


  • Dies kann mit dem Quellcode von HashMap.getEntry bestätigt werden. Es ist ziemlich klar, dass der Eintrag eine Liste mit unterschiedlichen Schlüsselwerten für denselben Hashcode ist.

    – Zaiping Bie

    13. Mai 2015 um 2:56 Uhr

Benutzer-Avatar
Sanjay T. Sharma

Wenn Sie das Paar einfügen (10, 17) und dann (10, 20), gibt es technisch keine Kollision. Sie ersetzen nur den alten Wert durch den neuen Wert für einen bestimmten Schlüssel 10 (da in beiden Fällen 10 gleich 10 ist und auch der Hash-Code für 10 immer 10 ist).

Eine Kollision tritt auf, wenn mehrere Schlüssel in denselben Bucket gehasht werden. In diesem Fall müssen Sie sicherstellen, dass Sie zwischen diesen Schlüsseln unterscheiden können. Die Verkettungskollisionsauflösung ist eine dieser Techniken, die dafür verwendet wird.

Nehmen wir als Beispiel an, dass zwei Zeichenfolgen "abra ka dabra" und "wave my wand" Hash-Codes liefern 100 und 200 beziehungsweise. Angenommen, die Gesamtgröße des Arrays beträgt 10, landen beide im selben Bucket (100 % 10 und 200 % 10). Verkettung stellt dies sicher, wann immer Sie es tun map.get( "abra ka dabra" );, erhalten Sie am Ende den richtigen Wert, der dem Schlüssel zugeordnet ist. Im Fall der Hash-Map in Java erfolgt dies durch die Verwendung von equals Methode.

  • Der Eimer speichert also die Adresse der Kette und die Kette enthält Knoten; jeder Knoten eine Schlüssel/Wert-Struktur hat? In diesem Fall gibt es also einen Knoten in einer Kette mit dem Schlüssel als “abra ka dabra” und einen anderen Knoten mit dem Schlüssel als “winke meine Hand” in derselben Kette, richtig?

    – Benutzer2938723

    31. Oktober 2013 um 17:20 Uhr


  • @ user2938723: Ja, im Grunde enthält jeder Array-Slot eine “Kette” von Schlüssel-Wert-Paaren.

    – Sanjay T. Sharma

    31. Oktober 2013 um 18:11 Uhr

  • Java verwendet also welchen Kollisionsbehandlungsmechanismus? und warum ?

    – dinesh kandpal

    19. März 2020 um 17:59 Uhr

Benutzer-Avatar
Guillaume Poussel

In einem HashMap der Schlüssel ist ein Objekt, das enthält hashCode() und equals(Object) Methoden.

Wenn Sie einen neuen Eintrag in die Map einfügen, wird geprüft, ob die hashCode ist schon bekannt. Dann durchläuft es alle Objekte mit diesem Hashcode und testet ihre Gleichheit mit .equals(). Wenn ein gleich Objekt gefunden wird, ersetzt der neue Wert den alten. Wenn nicht, wird ein neuer Eintrag in der Karte erstellt.

Wenn Sie über Karten sprechen, verwenden Sie normalerweise Kollision wenn zwei Objekte dasselbe haben hashCode aber sie sind anders. Sie werden intern in einer Liste gespeichert.

Benutzer-Avatar
iluxa

Es hätte tatsächlich eine verkettete Liste bilden können. Es ist nur so dass Map Vertrag erfordert es, den Eintrag zu ersetzen:

V put(K key, V value)

Ordnet den angegebenen Wert dem angegebenen Schlüssel in dieser Zuordnung zu (optionale Operation). Wenn die Zuordnung zuvor eine Zuordnung für den Schlüssel enthielt, wird der alte Wert durch den angegebenen Wert ersetzt. (Eine Abbildung m enthält genau dann eine Abbildung für einen Schlüssel k, wenn m.containsKey(k) wahr zurückgeben würde.)

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

Damit eine Karte Wertelisten speichern kann, muss es a sein Multimap. Hier ist Googles: http://google-collections.googlecode.com/svn/trunk/javadoc/com/google/common/collect/Multimap.html

Eine Sammlung ähnlich einer Karte, die jedoch mehrere Werte mit einem einzigen Schlüssel verknüpfen kann. Wenn Sie put(K, V) zweimal mit demselben Schlüssel, aber unterschiedlichen Werten aufrufen, enthält die Multimap Zuordnungen vom Schlüssel zu beiden Werten.

Bearbeiten: Kollisionsauflösung

Das ist ein bisschen anders. Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel zufällig denselben Hash-Code haben oder zwei Schlüssel mit unterschiedlichen Hash-Codes zufällig demselben Bucket im zugrunde liegenden Array zugeordnet werden.

In Betracht ziehen HashMap‘s Quelle (Teile entfernt):

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);
}

Für diejenigen, die neugierig sind, wie die Entry Klasse ein HashMap Es stellt sich heraus, dass sich wie eine Liste verhält HashMap definiert seine eigene Statik Entry Klasse, die implementiert Map.Entry. Sie können sich selbst davon überzeugen, indem Sie sich den Quellcode ansehen:

GrepCode für HashMap

  • “oder zwei Schlüssel mit unterschiedlichen Hash-Codes werden zufällig demselben Bucket im zugrunde liegenden Array zugeordnet”. Wie würde das passieren? Ich dachte, unterschiedlicher Hash = unterschiedlicher Eimer. nicht wahr?

    – Ahmad Abdelghany

    31. Mai 2016 um 23:23 Uhr

Benutzer-Avatar
Rajarshee Mitra

Zunächst einmal haben Sie das Konzept des Hashings ein wenig falsch verstanden, und es wurde von @Sanjay korrigiert.

Und ja, Java implementiert tatsächlich eine Kollisionsauflösungstechnik. Wenn zwei Schlüssel auf denselben Wert gehasht werden (da das verwendete interne Array eine endliche Größe hat und die Methode hashcode() irgendwann denselben Hashwert für zwei verschiedene Schlüssel zurückgibt), wird zu diesem Zeitpunkt eine verknüpfte Liste im Bucket gebildet Ort, an dem alle Informationen als Map.Entry-Objekt eingegeben werden, das ein Schlüssel-Wert-Paar enthält. Der Zugriff auf ein Objekt über einen Schlüssel erfordert im schlimmsten Fall O(n), wenn der Eintrag in einer solchen Liste vorhanden ist. Der Vergleich zwischen dem übergebenen Schlüssel und jedem Schlüssel in einer solchen Liste erfolgt durch die Methode equals().

Obwohl ab Java 8 die verknüpften Listen durch Bäume ersetzt werden (O(log n))

Benutzer-Avatar
Entwickler

In Ihrem Fall geht es nicht um Kollisionsauflösung, es handelt sich lediglich um das Ersetzen des älteren Werts durch einen neuen Wert für denselben Schlüssel, weil Java HashMap darf keine Duplikate enthalten (d. h. mehrere Werte) für das Selbe Schlüssel.

In Ihrem Beispiel wird der Wert 17 einfach durch 20 für denselben Schlüssel 10 in der HashMap ersetzt.

Wenn Sie versuchen, einen anderen/neuen Wert für denselben Schlüssel einzugeben, handelt es sich nicht um das Konzept der Kollisionsauflösung, sondern es wird einfach der alte Wert durch einen neuen Wert für denselben Schlüssel ersetzt. Es ist wie HashMap wurde entworfen und Sie können einen Blick auf die unten stehende API (Hervorhebung von mir) werfen hier.

öffentlicher V-Put (K-Taste, V-Wert)

Ordnet den angegebenen Wert dem angegebenen Schlüssel in dieser Zuordnung zu. Wenn die Zuordnung zuvor eine Zuordnung für den Schlüssel enthielt, wird der alte Wert ersetzt.


Andererseits kommen Kollisionsauflösungstechniken nur dann ins Spiel, wenn mehrere Schlüssel enden mit demselben Hashcode (dh sie fallen in dieselbe Bucket-Position), wo bereits ein Eintrag gespeichert ist. HashMap handhabt die Kollisionsauflösung, indem es das Konzept der Verkettung verwendet, dh es speichert die Werte in einer verketteten Liste (oder einem ausgeglichenen Baum seit Java8, abhängig von der Anzahl der Einträge).

Benutzer-Avatar
Pradeep

Wenn mehrere Schlüssel im selben Hash-Code landen, der im selben Bucket vorhanden ist. Wenn derselbe Schlüssel unterschiedliche Werte hat, wird der alte Wert durch den neuen Wert ersetzt.

Die Liked-Liste wurde im Worst-Case-Szenario ab Java 8-Version in einen ausgewogenen Binärbaum konvertiert.

Kollisionen treten auf, wenn 2 unterschiedliche Schlüssel denselben Hashcode () -Wert generieren. Wenn es dann mehr Kollisionen gibt, führt dies zu einer schlechtesten Leistung der Hashmap.

Objekte, die gemäß der equals-Methode gleich sind, müssen denselben hashCode-Wert zurückgeben. Wenn beide Objekte denselben Has-Code zurückgeben, werden sie in denselben Bucket verschoben.

Benutzer-Avatar
Hutashan Chandrakar

Es gibt einen Unterschied zwischen Kollision und Duplikation. Kollision bedeutet, dass Hashcode und Bucket gleich sind, aber im Duplikat wird es derselbe Hashcode, derselbe Bucket sein, aber hier kommt die gleiche Methode ins Bild.

Kollision erkannt und Sie können Element zu vorhandenem Schlüssel hinzufügen. aber im Falle einer Vervielfältigung ersetzt es den Neuwert.

1252500cookie-checkKollisionsauflösung in Java HashMap

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy