Jak HashTables radzą sobie z kolizjami?

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 Keyssą Stringtypu 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.

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.

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

• Otwórz adresowanie

• 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.

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 .

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.

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.

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 )

Użyje metody equals, aby sprawdzić, czy klucz jest obecny nawet, a zwłaszcza jeśli w tym samym zasobniku jest więcej niż jeden element.

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.)

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

Istnieją różne metody rozwiązywania kolizji, takie jak oddzielne łańcuchowanie, otwarte adresowanie, haszowanie Robin Hooda, haszowanie kukułki itp.

Java używa oddzielnych łańcuchów do rozwiązywania kolizji w tabelach z skrótami. Oto świetne łącze do tego, jak to się dzieje: http://javapapers.com/core-java/java-hashtable/