Jak HashTables radzą sobie z kolizjami?


98

Słyszałem na moich zajęciach na studiach, że HashTablenowy wpis zostanie umieszczony w kategorii „następny dostępny”, jeśli nowy wpis klucza koliduje z innym.

W jaki sposób HashTablenadal zwracałby poprawną wartość, gdyby ta kolizja wystąpiła podczas wywołania z powrotem za pomocą klucza kolizji?

Zakładam, że KeysStringtypu i hashCode()zwraca wartość domyślną wygenerowaną przez, powiedzmy, Javę.

Jeśli zaimplementuję własną funkcję haszującą i użyję jej jako części tabeli przeglądowej (tj. A HashMaplub Dictionary), jakie istnieją strategie radzenia sobie z kolizjami?

Widziałem nawet notatki dotyczące liczb pierwszych! Informacje nie są tak jasne z wyszukiwarki Google.

Odpowiedzi:


93

Tabele skrótów radzą sobie z kolizjami na jeden z dwóch sposobów.

Opcja 1: Każdy zasobnik zawiera połączoną listę elementów, które są zaszyfrowane w tym zasobniku. Dlatego zła funkcja skrótu może bardzo spowolnić wyszukiwanie w tablicach skrótów.

Opcja 2: Jeśli wszystkie wpisy tabeli skrótów są pełne, tabela skrótów może zwiększyć liczbę segmentów, które ma, a następnie ponownie rozdzielić wszystkie elementy w tabeli. Funkcja haszująca zwraca liczbę całkowitą, a tablica haszująca musi pobrać wynik funkcji haszującej i dopasować go do rozmiaru tabeli, aby mieć pewność, że trafi do zasobnika. Więc zwiększając rozmiar, powtórzy i uruchomi obliczenia modulo, które przy odrobinie szczęścia mogą wysłać obiekty do różnych wiader.

Java używa zarówno opcji 1, jak i 2 w swoich implementacjach tablicy skrótów.


1
W przypadku pierwszej opcji, czy istnieje jakiś powód, dla którego lista połączona jest używana zamiast tablicy lub nawet binarnego drzewa wyszukiwania?

1
powyższe wyjaśnienie jest na wysokim poziomie, nie sądzę, aby miało to duże znaczenie w przypadku listy połączonej z tablicą. Myślę, że binarne drzewo wyszukiwania byłoby przesadą. Myślę też, że jeśli zagłębisz się w rzeczy takie jak ConcurrentHashMap i inne, istnieje wiele szczegółów dotyczących implementacji niskiego poziomu, które mogą mieć wpływ na wydajność, których powyższe wyjaśnienie wysokiego poziomu nie uwzględnia.
AMS

2
Jeśli używane jest łańcuchowanie, po otrzymaniu klucza, skąd mamy wiedzieć, który przedmiot odzyskać?
ChaoSXDemon

1
@ChaoSXDemon możesz przechodzić przez listę w łańcuchu po kluczu, zduplikowane klucze nie są problemem, problemem są dwa różne klucze mające ten sam hashcode.
rano

1
@ams: Który z nich jest preferowany? czy istnieje limit kolizji skrótu, po którym drugi punkt jest wykonywany przez JAVA?
Shashank Vivek

78

Kiedy mówiłeś o „Hash Table” umieści nowy wpis w „następnym dostępnym” segmencie, jeśli nowy klucz zderzy się z innym. ”, To mówisz o otwartej strategii adresowania dotyczącej rozwiązywania kolizji w tablicy haszującej.


Istnieje kilka strategii rozwiązywania kolizji w tabeli skrótów.

Pierwszy rodzaj dużej metody wymaga, aby klucze (lub wskaźniki do nich) były przechowywane w tabeli wraz z przypisanymi do nich wartościami, która obejmuje ponadto:

  • Oddzielne łańcuchy

wprowadź opis obrazu tutaj

  • Otwórz adresowanie

wprowadź opis obrazu tutaj

  • Połączony hasz
  • Haszowanie z kukułką
  • Haszowanie Robin Hooda
  • Haszowanie 2 opcji
  • Gra w klasy

Inną ważną metodą radzenia sobie z kolizjami jest dynamiczna zmiana rozmiaru , która dodatkowo ma kilka sposobów:

  • Zmiana rozmiaru poprzez skopiowanie wszystkich wpisów
  • Przyrostowa zmiana rozmiaru
  • Klawisze monotoniczne

EDYCJA : powyższe są zapożyczone z wiki_hash_table , gdzie powinieneś zajrzeć, aby uzyskać więcej informacji.


3
„[…] wymaga, aby klucze (lub wskaźniki do nich) były przechowywane w tabeli wraz z powiązanymi wartościami”. Dzięki, nie zawsze jest to kwestia, która nie zawsze jest od razu jasna, gdy czyta się o mechanizmach przechowywania wartości.
mtone

27

Istnieje wiele technik radzenia sobie z kolizjami. Wyjaśnię niektóre z nich

Łańcuch: w łańcuchu używamy indeksów tablic do przechowywania wartości. Jeśli kod skrótu drugiej wartości również wskazuje na ten sam indeks, wówczas zastępujemy tę wartość indeksu połączoną listą, a wszystkie wartości wskazujące na ten indeks są przechowywane na połączonej liście, a rzeczywisty indeks tablicy wskazuje na nagłówek połączonej listy. Ale jeśli istnieje tylko jeden kod skrótu wskazujący na indeks tablicy, wartość jest bezpośrednio przechowywana w tym indeksie. Ta sama logika jest stosowana podczas pobierania wartości. Jest to używane w Java HashMap / Hashtable, aby uniknąć kolizji.

Sondowanie liniowe: Technika ta jest używana, gdy w tabeli mamy więcej indeksów niż wartości do zapisania. Technika sondowania liniowego działa na zasadzie ciągłego zwiększania wartości, aż znajdziesz puste miejsce. Pseudo kod wygląda następująco:

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

Technika podwójnego haszowania: W tej technice używamy dwóch funkcji haszujących h1 (k) i h2 (k). Jeśli szczelina w h1 (k) jest zajęta, to druga funkcja haszująca h2 (k) używana do zwiększania indeksu. Pseudokod wygląda następująco:

index = h1(k)

while( val(index) is occupied)

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

Techniki liniowego sondowania i podwójnego haszowania są częścią otwartej techniki adresowania i mogą być używane tylko wtedy, gdy dostępnych gniazd jest więcej niż liczba elementów do dodania. Zajmuje mniej pamięci niż łańcuch, ponieważ nie ma tu żadnej dodatkowej struktury, ale jest powolny z powodu dużego ruchu, dopóki nie znajdziemy pustego gniazda. Również w technice otwartego adresowania, gdy przedmiot jest usuwany ze slotu, umieszczamy nagrobek, aby wskazać, że przedmiot został stąd usunięty, dlatego jest pusty.

Więcej informacji można znaleźć na tej stronie .


18

Gorąco zachęcam do przeczytania tego wpisu na blogu, który pojawił się niedawno w serwisie HackerNews: Jak działa HashMap w Javie

Krótko mówiąc, odpowiedź brzmi

Co się stanie, jeśli dwa różne obiekty kluczy HashMap mają ten sam kod skrótu?

Będą przechowywane w tym samym zasobniku, ale bez kolejnego węzła połączonej listy. Metoda keys equals () zostanie użyta do identyfikacji prawidłowej pary klucz-wartość w HashMap.


3
HashMapy są bardzo interesujące i sięgają głęboko! :)
Alex

1
Myślę, że pytanie dotyczy HashTables, a nie HashMap
Prashant Shubham

10

Słyszałem na moich zajęciach na studiach, że HashTable umieści nowy wpis w segmencie „następny dostępny”, jeśli nowy wpis klucza zderzy się z innym.

W rzeczywistości nie jest to prawdą, przynajmniej w przypadku Oracle JDK ( jest to szczegół implementacji, który może różnić się między różnymi implementacjami interfejsu API). Zamiast tego każdy zasobnik zawiera połączoną listę wpisów starszych niż Java 8 oraz zrównoważone drzewo w wersji Java 8 lub nowszej.

to w jaki sposób HashTable nadal zwracałby poprawną wartość, jeśli ta kolizja wystąpiłaby podczas wywoływania go z powrotem z kluczem kolizji?

Używa znaku, equals()aby znaleźć faktycznie pasujący wpis.

Jeśli zaimplementuję własną funkcję haszującą i użyję jej jako części tabeli przeglądowej (np. HashMap lub Dictionary), jakie istnieją strategie radzenia sobie z kolizjami?

Istnieją różne strategie postępowania w przypadku kolizji, które mają różne zalety i wady. Wpis Wikipedii dotyczący tabel skrótów daje dobry przegląd.


Jest to prawdą w obu przypadkach Hashtableiw HashMapjdk 1.6.0_22 autorstwa Sun / Oracle.
Nikita Rybak,

@Nikita: nie jestem pewien co do Hashtable i nie mam teraz dostępu do źródeł, ale jestem w 100% pewien, że HashMap używa łączenia łańcuchowego, a nie liniowego sondowania w każdej wersji, jaką kiedykolwiek widziałem w moim debugerze.
Michael Borgwardt,

@Michael Cóż, patrzę teraz na źródło HashMap public V get(Object key)(ta sama wersja co powyżej). Jeśli znajdziesz dokładną wersję, w której pojawiają się te połączone listy, byłbym zainteresowany.
Nikita Rybak,

@Niki: Patrzę teraz na tę samą metodę i widzę, że używa pętli for do iteracji przez połączoną listę Entryobiektów:localEntry = localEntry.next
Michael Borgwardt,

@Michael Przepraszam, to mój błąd. Źle zinterpretowałem kod. naturalnie e = e.nextnie jest ++index. +1
Nikita Rybak

7

Aktualizacja od wersji Java 8: Java 8 używa samoczynnie równoważonego drzewa do obsługi kolizji, poprawiając najgorszy przypadek z O (n) do O (log n) na potrzeby wyszukiwania. Użycie samoczynnie równoważonego drzewa zostało wprowadzone w Javie 8 jako ulepszenie w stosunku do łączenia łańcuchowego (używanego do java 7), które używa listy połączonej i ma najgorszy przypadek O (n) do wyszukiwania (ponieważ musi przejść Lista)

Aby odpowiedzieć na drugą część twojego pytania, wstawianie odbywa się poprzez mapowanie danego elementu do podanego indeksu w podstawowej tablicy haszmapy, jednak gdy wystąpi kolizja, wszystkie elementy muszą być nadal zachowane (przechowywane w drugorzędnej strukturze danych , a nie tylko zastąpione w podstawowej tablicy). Zwykle robi się to poprzez uczynienie każdego komponentu tablicy (gniazda) drugorzędną strukturą danych (inaczej zasobnikiem), a element jest dodawany do zasobnika znajdującego się w podanym indeksie tablicy (jeśli klucz nie istnieje jeszcze w zasobniku, w w którym przypadku jest wymieniany).

Podczas wyszukiwania klucz jest haszowany do odpowiedniego indeksu tablicy i wyszukiwane jest element pasujący do (dokładnego) klucza w danym zasobniku. Ponieważ zasobnik nie musi obsługiwać kolizji (bezpośrednio porównuje klucze), rozwiązuje to problem kolizji, ale robi to kosztem konieczności wykonywania wstawiania i wyszukiwania w dodatkowej strukturze danych. Kluczową kwestią jest to, że w haszmie przechowywany jest zarówno klucz, jak i wartość, więc nawet jeśli hasz koliduje, klucze są porównywane bezpośrednio pod kątem równości (w zasobniku), dzięki czemu można je jednoznacznie zidentyfikować w zasobniku.

Obsługa kolizji przenosi najgorszą wydajność wstawiania i wyszukiwania z O (1) w przypadku braku obsługi kolizji do O (n) w celu łączenia (lista połączona jest używana jako dodatkowa struktura danych) i O (log n) dla samozrównoważonego drzewa.

Bibliografia:

Java 8 zawiera następujące ulepszenia / zmiany obiektów HashMap w przypadku dużych kolizji.

  • Alternatywna funkcja skrótu String dodana w Javie 7 została usunięta.

  • Zasobniki zawierające dużą liczbę kolidujących kluczy będą przechowywać swoje wpisy w zrównoważonym drzewie zamiast w połączonej liście po osiągnięciu określonego progu.

Powyższe zmiany zapewniają wydajność O (log (n)) w najgorszych przypadkach ( https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8 )


Czy możesz wyjaśnić, dlaczego najgorszy przypadek wstawienia dla listy połączonej HashMap to tylko O ​​(1), a nie O (N)? Wydaje mi się, że jeśli masz 100% współczynnik kolizji dla kluczy, które nie są zduplikowane, musisz przejść przez każdy obiekt w HashMap, aby znaleźć koniec połączonej listy, prawda? czego mi brakuje?
mbm29414

W konkretnym przypadku implementacji hashmap masz rację, ale nie dlatego, że musisz znaleźć koniec listy. W ogólnej implementacji listy połączonej wskaźnik jest przechowywany zarówno na początku, jak i na końcu, a zatem wstawienie można wykonać w O (1), dołączając następny węzeł bezpośrednio do ogona, ale w przypadku hashmap metoda wstawiania musi upewnić się, że nie ma duplikatów, a zatem musi przeszukać listę, aby sprawdzić, czy element już istnieje, i dlatego otrzymujemy O (n). A więc to właściwość set nałożona na listę połączoną powoduje O (N).
Poprawię


4

Ponieważ istnieje pewne zamieszanie co do tego, którego algorytmu używa Java HashMap (w implementacji Sun / Oracle / OpenJDK), tutaj odpowiednie fragmenty kodu źródłowego (z OpenJDK, 1.6.0_20, na 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;
}

Ta metoda (cite pochodzi z linii od 355 do 371) jest wywoływana podczas wyszukiwania wpisu w tabeli, na przykład z get(), containsKey()i kilku innych. Pętla for przechodzi tutaj przez połączoną listę utworzoną przez obiekty wejściowe.

Tutaj kod obiektów wejściowych (linie 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)

}

Zaraz potem przychodzi addEntry()metoda:

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

Spowoduje to dodanie nowego wpisu z przodu zasobnika, z łączem do starego pierwszego wpisu (lub null, jeśli takiego nie ma). Podobnie removeEntryForKey()metoda przechodzi przez listę i dba o usunięcie tylko jednego wpisu, pozostawiając resztę listy nienaruszoną.

Tak więc tutaj jest powiązana lista wpisów dla każdego segmentu i bardzo wątpię, czy zmieniło się to z _20na _22, ponieważ było tak od 1.2.

(Ten kod to (c) 1997-2007 Sun Microsystems i jest dostępny na GPL, ale do kopiowania lepiej użyj oryginalnego pliku, zawartego w src.zip w każdym JDK firmy Sun / Oracle, a także w OpenJDK.)


1
Oznaczyłem to jako wiki społeczności , ponieważ tak naprawdę nie jest to odpowiedź, a raczej dyskusja na temat innych odpowiedzi. W komentarzach po prostu nie ma miejsca na takie cytaty z kodu.
Paŭlo Ebermann

3

oto bardzo prosta implementacja tablicy skrótów w java. tylko narzędzia put()i get(), ale możesz łatwo dodać, co chcesz. opiera się na hashCode()metodzie Java, która jest implementowana przez wszystkie obiekty. możesz łatwo stworzyć własny interfejs,

interface Hashable {
  int getHash();
}

i jeśli chcesz, wymuś to za pomocą klawiszy.

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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.