Wie gehen HashTables mit Kollisionen um?

Wenn Sie Sprach über die "Hash-Tabelle wird ein neuer Eintrag in die 'nächste verfügbare' Eimer, wenn Sie den neuen Schlüssel-Eintrag kollidiert mit einem anderen.", Sie sprechen über die Offene Adressierung Strategie der kollisionsauflösung der hash-Tabelle.

Gibt es mehrere Strategien für die hash-Tabelle zu beheben Kollision.

Erste Art von groß-Methode müssen die Tasten (oder Zeiger) werden in der Tabelle gespeichert, zusammen mit den dazugehörigen Werten, die weiter umfasst:

• Separate chaining

• Offene Adressierung

• Ergoss hashing
• Cuckoo hashing
• Robin-Hood-hashing
• 2-Wahl-hashing
• Himmel-und-Hölle-hashing

Eine weitere wichtige Methode, mit der Kollision von Dynamische Größenanpassung, welche weiteren hat mehrere Möglichkeiten:

• Größenänderung durch kopieren aller Einträge
• Inkrementelle Größenanpassung
• Monotone-Schlüssel

BEARBEITEN: die oben genannten entlehnt sind wiki_hash_table, wo Sie gehen sollten, um zu schauen um mehr Infos zu bekommen.

InformationsquelleAutor der Antwort herohuyongtao

Gibt es mehrere Techniken zur Verfügung, damit Kollision. Ich werde erklären, einige von Ihnen

Verkettung:
In Verkettung verwenden wir die array-Indizes, um die Werte zu speichern. Wenn der hash-code der zweite Wert auch die Punkte an den gleichen index, dann ersetzen wir das index-Wert mit einer verknüpften Liste und alle Werte zeigen auf, dass der index gespeichert werden, die in der verknüpften Liste und der tatsächlichen array-index-Punkte auf den Kopf der verketteten Liste.
Aber wenn es nur einen hash-code verweist auf einen index des Arrays wird der Wert direkt gespeichert, index. Dieselbe Logik wird angewendet, während das abrufen von Werten. Dies wird in Java HashMap/Hashtable Kollisionen sind zu vermeiden.

Linear probing: Diese Technik wird verwendet, wenn wir mehr index in der Tabelle dann die Werte gespeichert werden. Linear probing-Technik die Arbeit an das Konzept halten, Inkrementieren, bis Sie den leeren Steckplatz ein. Der pseudo-code sieht wie folgt aus..

index = h(k)

while( val(index) belegt ist)

index = (index+1) mod n

Double-hashing-Technik: In dieser Technik, die wir benutzen zwei Hashfunktionen h1(k) und h2(k). Wenn der Schlitz bei h1(k) besetzt ist, dann wird der zweite Hash-Funktion h2(k) zum Inkrementieren der index. Der pseudo-code sieht wie folgt aus..

index = h1(k)

while( val(index) belegt ist)

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

Linear probing und double hashing-Techniken sind Teil der offenen Adressierung Technik, und es kann nur verwendet werden, wenn die verfügbaren Steckplätze sind mehr als die Anzahl der Elemente Hinzugefügt werden. Es dauert weniger Speicher, dann chaining, weil es keine zusätzliche Struktur verwendet, die hier aber seine langsam, weil viel Bewegung passieren, bis wir finden einen leeren slot. Auch in der offenen Adressierung die Verfahren, wenn ein Element entfernt wird, ein Ablagefach legen wir den Grabstein, um anzuzeigen, dass das Objekt entfernt ist von hier, dass ist der Grund, warum seine leere.

Entnommen http://coder2design.com/hashing/

InformationsquelleAutor der Antwort Jatinder Pal

Da es einige Verwirrung darüber, welcher Algorithmus der Java-HashMap ist (in der Sun/Oracle/OpenJDK-Implementierung), hier der relevante Quellcode-Schnipsel (von OpenJDK, 1.6.0_20, auf 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 aus Linien, 355 bis 371) wird aufgerufen, wenn nach einem Eintrag in der Tabelle, zum Beispiel von get(), containsKey() und einige andere. Die for-Schleife geht hier über die verlinkten Liste gebildet, die durch die Eingabe-Objekte.

Hier der code für den Eintrag Objekte (Linien 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)

}

Direkt danach kommt der 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);
}

Diese fügt den neuen Eintrag auf der Vorderseite des Eimers, mit einem link zu der alten ersten Eintrag (oder null, wenn kein solches). In ähnlicher Weise werden die removeEntryForKey() - Methode durchläuft die Liste und kümmert sich um das löschen nur eines Eintrags, so dass der rest der Liste intakt.

So, hier ist eine verknüpfte Liste für jeden Eimer, und ich sehr bezweifle, dass dies geändert _20 zu _22, da war es so von 1,2 auf.

(Dieser code ist (c) 1997-2007 Sun Microsystems, und unter GPL verfügbar, aber für das kopieren besser, die original-Datei, enthalten in src.zip in jedem JDK von Sun/Oracle, und auch in OpenJDK.)

InformationsquelleAutor der Antwort

Gibt es verschiedene Methoden für die kollisionsauflösung.Einige von Ihnen sind Separate Chaining,Offene Adressierung,Robin-Hood-hashing,Cuckoo Hashing etc.

Java verwendet Separate Chaining für die Auflösung von Kollisionen in Hash-Tabellen.Hier ist ein toller link, wie es passiert:
http://javapapers.com/core-java/java-hashtable/

InformationsquelleAutor der Antwort Infusion of Wormwood n Asfodel