Wie gehen HashTables mit Kollisionen um?

97

Ich habe in meinen Abschlussklassen gehört, dass a HashTableeinen neuen Eintrag in den 'nächsten verfügbaren' Bucket legt, wenn der neue Schlüsseleintrag mit einem anderen kollidiert.

Wie würde der HashTableimmer noch den korrekten Wert zurückgeben, wenn diese Kollision auftritt, wenn mit dem Kollisionsschlüssel ein Rückruf angefordert wird?

Ich gehe davon aus, dass der Typ Keysare Stringund der hashCode()von Java generierte Standardwert zurückgegeben werden.

Welche Strategien gibt es für den Umgang mit Kollisionen, wenn ich meine eigene Hashing-Funktion implementiere und sie als Teil einer Nachschlagetabelle (dh a HashMapoder Dictionary) verwende?

Ich habe sogar Notizen zu Primzahlen gesehen! Informationen aus der Google-Suche nicht so klar.

Alex
quelle

Antworten:

92

Hash-Tabellen behandeln Kollisionen auf zwei Arten.

Option 1: Indem jeder Bucket eine verknüpfte Liste von Elementen enthält, die mit diesem Bucket gehasht werden. Aus diesem Grund kann eine fehlerhafte Hash-Funktion das Nachschlagen in Hash-Tabellen sehr langsam machen.

Option 2: Wenn alle Hash-Tabelleneinträge voll sind, kann die Hash-Tabelle die Anzahl der vorhandenen Buckets erhöhen und dann alle Elemente in der Tabelle neu verteilen. Die Hash-Funktion gibt eine Ganzzahl zurück, und die Hash-Tabelle muss das Ergebnis der Hash-Funktion nehmen und es an die Größe der Tabelle anpassen, damit sichergestellt ist, dass sie in den Bucket gelangt. Wenn Sie also die Größe erhöhen, werden die Modulo-Berechnungen erneut aufbereitet und ausgeführt. Wenn Sie Glück haben, werden die Objekte möglicherweise an verschiedene Eimer gesendet.

Java verwendet sowohl Option 1 als auch Option 2 in seinen Hash-Tabellen-Implementierungen.

ams
quelle
1
Gibt es bei der ersten Option einen Grund, warum eine verknüpfte Liste anstelle eines Arrays oder sogar eines binären Suchbaums verwendet wird?
1
Die obige Erklärung ist auf hohem Niveau, ich denke nicht, dass es einen großen Unterschied zwischen verknüpfter Liste und Array macht. Ich denke, ein binärer Suchbaum wäre übertrieben. Ich denke auch, wenn Sie sich mit Dingen wie ConcurrentHashMap und anderen beschäftigen, gibt es viele Details zu Implementierungen auf niedriger Ebene, die einen Leistungsunterschied bewirken können, die in der obigen Erklärung auf hoher Ebene nicht berücksichtigt werden.
ams
2
Woher wissen wir, welcher Gegenstand zurückkommt, wenn eine Verkettung verwendet wird, wenn wir einen Schlüssel erhalten?
ChaoSXDemon
1
@ChaoSXDemon Sie können die Liste in der Kette nach Schlüssel durchsuchen. Doppelte Schlüssel sind nicht das Problem. Das Problem sind zwei verschiedene Schlüssel mit demselben Hashcode.
Ams
1
@ams: Welches ist bevorzugt? Gibt es eine Grenze für die Hash-Kollision, nach der der 2. Punkt von JAVA ausgeführt wird?
Shashank Vivek
77

Wenn Sie über "Hash-Tabelle wird einen neuen Eintrag in den 'nächsten verfügbaren' Bucket platzieren, wenn der neue Schlüsseleintrag mit einem anderen kollidiert." Gesprochen haben, sprechen Sie über die offene Adressierungsstrategie der Kollisionsauflösung von Hash-Tabellen.


Es gibt verschiedene Strategien für Hash-Tabellen, um Kollisionen aufzulösen.

Die erste Art einer großen Methode erfordert, dass die Schlüssel (oder Zeiger auf sie) zusammen mit den zugehörigen Werten in der Tabelle gespeichert werden. Dazu gehören außerdem:

  • Separate Verkettung

Geben Sie hier die Bildbeschreibung ein

  • Offene Adressierung

Geben Sie hier die Bildbeschreibung ein

  • Zusammengewachsenes Hashing
  • Kuckuckshashing
  • Robin Hood Hashing
  • 2-Choice-Hashing
  • Hopscotch-Hashing

Eine weitere wichtige Methode zur Behandlung von Kollisionen ist die dynamische Größenänderung , die verschiedene Möglichkeiten bietet:

  • Ändern der Größe durch Kopieren aller Einträge
  • Inkrementelle Größenänderung
  • Monotone Tasten

BEARBEITEN : Die oben genannten Informationen stammen aus wiki_hash_table , wo Sie nachsehen sollten, um weitere Informationen zu erhalten.

herohuyongtao
quelle
3
"[...] erfordert, dass die Schlüssel (oder Zeiger darauf) zusammen mit den zugehörigen Werten in der Tabelle gespeichert werden". Vielen Dank, dies ist der Punkt, der beim Lesen von Mechanismen zum Speichern von Werten nicht immer sofort klar ist.
mtone
27

Für die Behandlung von Kollisionen stehen mehrere Techniken zur Verfügung. Ich werde einige von ihnen erklären

Verkettung: Bei der Verkettung verwenden wir Array-Indizes, um die Werte zu speichern. Wenn der Hashcode des zweiten Werts ebenfalls auf denselben Index verweist, ersetzen wir diesen Indexwert durch eine verknüpfte Liste, und alle Werte, die auf diesen Index verweisen, werden in der verknüpften Liste gespeichert, und der tatsächliche Array-Index zeigt auf den Kopf der verknüpften Liste. Wenn jedoch nur ein Hashcode auf einen Array-Index verweist, wird der Wert direkt in diesem Index gespeichert. Dieselbe Logik wird beim Abrufen der Werte angewendet. Dies wird in Java HashMap / Hashtable verwendet, um Kollisionen zu vermeiden.

Lineare Prüfung: Diese Technik wird verwendet, wenn die Tabelle mehr Index enthält als die zu speichernden Werte. Die lineare Sondiertechnik arbeitet mit dem Konzept, so lange zu erhöhen, bis Sie einen leeren Steckplatz finden. Der Pseudocode sieht folgendermaßen aus:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Double-Hashing-Technik: In dieser Technik verwenden wir zwei Hashing-Funktionen h1 (k) und h2 (k). Wenn der Schlitz bei h1 (k) belegt ist, wird die zweite Hashing-Funktion h2 (k) verwendet, um den Index zu erhöhen. Der Pseudocode sieht folgendermaßen aus:

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

Lineare Abtast- und Doppel-Hashing-Techniken sind Teil der offenen Adressierungstechnik und können nur verwendet werden, wenn die verfügbaren Slots mehr als die Anzahl der hinzuzufügenden Elemente sind. Es benötigt weniger Speicher als Verkettung, da hier keine zusätzliche Struktur verwendet wird, aber es ist langsam, weil viel Bewegung stattfindet, bis wir einen leeren Steckplatz finden. Auch in der offenen Adressierungstechnik setzen wir einen Grabstein, wenn ein Element aus einem Steckplatz entfernt wird, um anzuzeigen, dass das Element von hier entfernt wurde, weshalb es leer ist.

Weitere Informationen finden Sie auf dieser Website .

Jatinder Pal
quelle
18

Ich empfehle Ihnen dringend, diesen Blog-Beitrag zu lesen, der kürzlich auf HackerNews veröffentlicht wurde: Wie HashMap in Java funktioniert

Kurz gesagt, die Antwort lautet

Was passiert, wenn zwei verschiedene HashMap-Schlüsselobjekte denselben Hashcode haben?

Sie werden im selben Bucket gespeichert, aber kein nächster Knoten der verknüpften Liste. Die Methode keys equals () wird verwendet, um das richtige Schlüsselwertpaar in HashMap zu identifizieren.

zengr
quelle
3
HashMaps sind sehr interessant und gehen tief! :)
Alex
1
Ich denke, die Frage bezieht sich auf HashTables, nicht auf HashMap
Prashant Shubham,
10

Ich habe in meinen Abschlussklassen gehört, dass eine HashTable einen neuen Eintrag in den "nächsten verfügbaren" Bucket legt, wenn der neue Schlüsseleintrag mit einem anderen kollidiert.

Dies gilt zumindest für das Oracle JDK nicht (es handelt sich um ein Implementierungsdetail, das zwischen verschiedenen Implementierungen der API variieren kann). Stattdessen enthält jeder Bucket eine verknüpfte Liste von Einträgen vor Java 8 und einen ausgeglichenen Baum in Java 8 oder höher.

Wie würde dann die HashTable immer noch den korrekten Wert zurückgeben, wenn diese Kollision auftritt, wenn mit dem Kollisionsschlüssel eine zurückgerufen wird?

Es verwendet das equals(), um den tatsächlich passenden Eintrag zu finden.

Welche Strategien gibt es für den Umgang mit Kollisionen, wenn ich meine eigene Hashing-Funktion implementiere und sie als Teil einer Nachschlagetabelle (dh einer HashMap oder eines Wörterbuchs) verwende?

Es gibt verschiedene Kollisionsbehandlungsstrategien mit unterschiedlichen Vor- und Nachteilen. Der Eintrag von Wikipedia in Hash-Tabellen gibt einen guten Überblick.

Michael Borgwardt
quelle
Dies gilt für beide Hashtableund HashMapin jdk 1.6.0_22 von Sun / Oracle.
Nikita Rybak
@Nikita: Ich bin mir bei Hashtable nicht sicher und habe momentan keinen Zugriff auf die Quellen, aber ich bin zu 100% sicher, dass HashMap in jeder einzelnen Version, die ich jemals in meinem Debugger gesehen habe, Verkettung und nicht lineare Prüfung verwendet.
Michael Borgwardt
@ Michael Nun, ich schaue mir gerade die Quelle von HashMap an public V get(Object key)(gleiche Version wie oben). Wenn Sie eine genaue Version finden, in der diese verknüpften Listen angezeigt werden, würde mich das interessieren.
Nikita Rybak
@Niki: Ich schaue jetzt auf die gleiche Methode, und ich sehe es mit einer for-Schleife, um durch eine verknüpfte Liste von EntryObjekten zu iterieren :localEntry = localEntry.next
Michael Borgwardt
@ Michael Entschuldigung, es ist mein Fehler. Ich habe Code falsch interpretiert. natürlich e = e.nextnicht ++index. +1
Nikita Rybak
7

Update seit Java 8: Java 8 verwendet einen selbstausgeglichenen Baum für die Kollisionsbehandlung, wodurch der Worst-Case für die Suche von O (n) auf O (log n) verbessert wird. Die Verwendung eines selbstausgeglichenen Baums wurde in Java 8 als Verbesserung gegenüber der Verkettung (verwendet bis Java 7) eingeführt, die eine verknüpfte Liste verwendet und einen Worst-Case von O (n) für die Suche aufweist (da diese durchlaufen werden muss) Die Liste)

Um den zweiten Teil Ihrer Frage zu beantworten, erfolgt das Einfügen durch Zuordnen eines bestimmten Elements zu einem bestimmten Index im zugrunde liegenden Array der Hashmap. Wenn jedoch eine Kollision auftritt, müssen alle Elemente weiterhin beibehalten (in einer sekundären Datenstruktur gespeichert) werden und nicht nur im zugrunde liegenden Array ersetzt). Dies erfolgt normalerweise, indem jede Array-Komponente (Slot) zu einer sekundären Datenstruktur (auch bekannt als Bucket) gemacht wird und das Element dem Bucket hinzugefügt wird, das sich auf dem angegebenen Array-Index befindet (falls der Schlüssel noch nicht im Bucket vorhanden ist, in in diesem Fall wird es ersetzt).

Während der Suche wird der Schlüssel auf den entsprechenden Array-Index gehasht und nach einem Element gesucht, das mit dem (genauen) Schlüssel im angegebenen Bucket übereinstimmt. Da der Bucket keine Kollisionen verarbeiten muss (Schlüssel direkt vergleicht), wird das Problem der Kollisionen gelöst, jedoch auf Kosten der Einfügung und Suche in der sekundären Datenstruktur. Der entscheidende Punkt ist, dass in einer Hashmap sowohl der Schlüssel als auch der Wert gespeichert werden. Selbst wenn der Hash kollidiert, werden die Schlüssel direkt auf Gleichheit (im Bucket) verglichen und können somit im Bucket eindeutig identifiziert werden.

Die Kollisionsbehandlung bringt die schlechteste Leistung beim Einfügen und Nachschlagen von O (1), wenn keine Kollisionsbehandlung erfolgt, zu O (n) zur Verkettung (eine verknüpfte Liste wird als sekundäre Datenstruktur verwendet) und O (log n). für selbstausgeglichenen Baum.

Verweise:

Java 8 wurde mit den folgenden Verbesserungen / Änderungen von HashMap-Objekten für den Fall hoher Kollisionen geliefert.

  • Die in Java 7 hinzugefügte alternative String-Hash-Funktion wurde entfernt.

  • Buckets mit einer großen Anzahl kollidierender Schlüssel speichern ihre Einträge nach Erreichen eines bestimmten Schwellenwerts in einem ausgeglichenen Baum anstelle einer verknüpften Liste.

Die obigen Änderungen stellen die Leistung von O (log (n)) im schlimmsten Fall sicher ( https://www.nagarro.com/de/blog/post/24/performance-improvement-for-hashmap-in-java-8 ).

Daniel Valland
quelle
Können Sie erklären, wie das Einfügen im ungünstigsten Fall für eine HashMap mit verknüpfter Liste nur O (1) und nicht O (N) ist? Mir scheint, wenn Sie eine Kollisionsrate von 100% für nicht doppelte Schlüssel haben, müssen Sie am Ende jedes Objekt in der HashMap durchlaufen, um das Ende der verknüpften Liste zu finden, oder? Was vermisse ich?
mbm29414
Im speziellen Fall der Hashmap-Implementierung haben Sie tatsächlich Recht, aber nicht, weil Sie das Ende der Liste finden müssen. In einer allgemeinen Implementierung einer verknüpften Liste wird ein Zeiger sowohl auf Kopf als auch auf Ende gespeichert, und daher kann das Einfügen in O (1) erfolgen, indem der nächste Knoten direkt an das Ende angehängt wird, im Fall von Hashmap jedoch die Einfügemethode muss sicherstellen, dass keine Duplikate vorhanden sind, und muss daher die Liste durchsuchen, um zu überprüfen, ob das Element bereits vorhanden ist, und daher erhalten wir O (n). Und so ist es die set-Eigenschaft, die einer verknüpften Liste auferlegt wird, die O (N) verursacht. Ich werde meine Antwort korrigieren :)
Daniel Valland
4

Mit der Methode equals wird überprüft, ob der Schlüssel gerade vorhanden ist, insbesondere, wenn sich mehr als ein Element im selben Bucket befindet.

Luftkissenfahrzeug voller Aale
quelle
4

Da es einige Unklarheiten darüber gibt, welchen Algorithmus Javas HashMap verwendet (in der Sun / Oracle / OpenJDK-Implementierung), hier die relevanten Quellcode-Schnipsel (aus OpenJDK, 1.6.0_20, unter Ubuntu):

/**
 * Returns the entry associated with the specified key in the
 * HashMap.  Returns null if the HashMap contains no mapping
 * for the key.
 */
final Entry<K,V> getEntry(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

Diese Methode (zitieren ist von Linien 355-371) aufgerufen wird , wenn ein Eintrag in der Tabelle nach oben, zum Beispiel aus get(), containsKey()und einige andere. Die for-Schleife durchläuft hier die verknüpfte Liste, die von den Eingabeobjekten gebildet wird.

Hier der Code für die Eingabeobjekte (Zeilen 691-705 + 759):

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    final int hash;

    /**
     * Creates new entry.
     */
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }

  // (methods left away, they are straight-forward implementations of Map.Entry)

}

Gleich danach kommt die addEntry()Methode:

/**
 * Adds a new entry with the specified key, value and hash code to
 * the specified bucket.  It is the responsibility of this
 * method to resize the table if appropriate.
 *
 * Subclass overrides this to alter the behavior of put method.
 */
void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

Dadurch wird der neue Eintrag auf der Vorderseite des Buckets mit einem Link zum alten ersten Eintrag hinzugefügt (oder null, falls kein solcher vorhanden ist). In ähnlicher removeEntryForKey()Weise geht die Methode die Liste durch und sorgt dafür, dass nur ein Eintrag gelöscht wird, wobei der Rest der Liste intakt bleibt.

Hier ist also eine verknüpfte Eintragsliste für jeden Bucket, und ich bezweifle sehr, dass sich dies von _20zu geändert hat _22, da es ab 1.2 so war.

(Dieser Code ist (c) 1997-2007 Sun Microsystems und unter GPL verfügbar. Verwenden Sie zum besseren Kopieren jedoch die Originaldatei, die in src.zip in jedem JDK von Sun / Oracle und auch in OpenJDK enthalten ist.)

Paŭlo Ebermann
quelle
1
Ich habe dies als Community-Wiki markiert , da es nicht wirklich eine Antwort ist, sondern eher eine Diskussion über die anderen Antworten. In Kommentaren ist einfach nicht genug Platz für solche Codezitate.
Paŭlo Ebermann
3

Hier ist eine sehr einfache Implementierung der Hash-Tabelle in Java. in nur implementiert put()und get(), aber Sie können einfach hinzufügen, was Sie möchten. Es basiert auf der Java- hashCode()Methode, die von allen Objekten implementiert wird. Sie könnten leicht Ihre eigene Schnittstelle erstellen,

interface Hashable {
  int getHash();
}

und erzwingen Sie die Implementierung durch die Schlüssel, wenn Sie möchten.

public class Hashtable<K, V> {
    private static class Entry<K,V> {
        private final K key;
        private final V val;

        Entry(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    private static int BUCKET_COUNT = 13;

    @SuppressWarnings("unchecked")
    private List<Entry>[] buckets = new List[BUCKET_COUNT];

    public Hashtable() {
        for (int i = 0, l = buckets.length; i < l; i++) {
            buckets[i] = new ArrayList<Entry<K,V>>();
        }
    }

    public V get(K key) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        for (Entry e: entries) {
            if (e.key.equals(key)) {
                return e.val;
            }
        }
        return null;
    }

    public void put(K key, V val) {
        int b = key.hashCode() % BUCKET_COUNT;
        List<Entry> entries = buckets[b];
        entries.add(new Entry<K,V>(key, val));
    }
}
Jeffrey Blattman
quelle
2

Es gibt verschiedene Methoden zur Kollisionsauflösung. Einige davon sind separate Verkettung, offene Adressierung, Robin Hood-Hashing, Kuckuck-Hashing usw.

Java verwendet die separate Verkettung zum Auflösen von Kollisionen in Hash-Tabellen. Hier finden Sie einen guten Link dazu: http://javapapers.com/core-java/java-hashtable/

Infusion von Wermut n Asfodel
quelle