Dlaczego wyszukiwanie (bezkolizyjne) hashtable rzeczywiście O (1)?

Uwaga: Wiem, że podobne pytania brzmią już tutaj i na Stackoverflow. Ale wszystkie dotyczą kolizji, o co nie proszę.

Moje pytanie brzmi: dlaczego collision- mniej odnośnika O(1)w pierwszej kolejności?

Załóżmy, że mam tę tabelę skrótów:

Hash  Content
-------------
ghdjg Data1
hgdzs Data2
eruit Data3
xcnvb Data4
mkwer Data5
rtzww Data6

Teraz szukam klucza, kktóry h(k)daje funkcja skrótu h(k) = mkwer. Ale w jaki sposób wyszukiwanie „wie”, że skrót mkwerznajduje się na pozycji 5? Dlaczego nie musi przewijać wszystkich klawiszy, O(n)aby go znaleźć? Skróty nie mogą być jakimś prawdziwym adresem sprzętowym, ponieważ straciłbym możliwość przenoszenia danych. I o ile mi wiadomo, tablica skrótów nie jest sortowana według skrótów (nawet gdyby tak było, wyszukiwanie też by się odbyło O(log n))?

W jaki sposób znajomość skrótu pomaga znaleźć właściwe miejsce w tabeli?

Funkcja skrótu nie zwraca niektórych ciągów znaków, takich jak mkwer. Bezpośrednio zwraca pozycję elementu w tablicy. Jeśli na przykład tabela skrótów zawiera dziesięć wpisów, funkcja skrótu zwróci liczbę całkowitą z zakresu 0–9.

Funkcja skrótu oblicza pozycję tablicy na podstawie podanego ciągu . Jeśli jest to idealny skrót, oznacza to, że na pewno nie ma kolizji, najprawdopodobniej tablica jest co najmniej dwa razy większa niż liczba elementów.

Na przykład dam bardzo słaby skrót dla liter, tylko dla zilustrowania mechanizmu:
0) 1) dla każdego znaku w ciągu należy przyjąć wartość ascii, odjąć „a”, jeśli jest to mała litera, odjąć „A”, jeśli jest wielka, dodać wartość do x. x = x m o d 52 2) wynikowa liczba, np. 15, jest indeksem tablicy. $x = 0;$
$x = x mod 52$

Ten bardzo prosty skrót (ograniczony i podatny na kolizje) różni się od innych skrótów mechanizmem mieszania, nie uwzględnia danych wejściowych. W bardziej zaawansowanym schemacie skrót ma większą liczbę, dostosowaną do liczby elementów. Dla wszystkich danych wejściowych generowany jest idealny skrót, aby zagwarantować brak kolizji.

Jest to ponieważ obliczanie wartości skrótu na podstawie łańcucha zależy od tego, jak wyrafinowana jest funkcja obliczana, ale nie zależy od liczby elementów.$O(1)$

W przypadku idealnego skrótu, gdy dodawane są elementy, jest ponownie obliczane, prostszy przypadek z kolizjami, gdy obciążenie tablicy jest duże, zwiększa się rozmiar tablicy, funkcja przyjmuje większy moduł wyjściowy, a elementy są przenoszone do nowych miejsc.$h(k)$

Tablica jest ciągłym fragmentem pamięci, aby uzyskać element , należy wziąć adres pierwszego elementu (początek tablicy), a następnie dodać do tego adresu n ∗ ( s i z e o f e l e m e n t ), aby uzyskać jawna komórka pamięci.$n-th$$n * (size of element)$

Aby rozwinąć odpowiedź Davida Richerby'ego, termin „ funkcja skrótu ” jest nieco przeciążony. Często, gdy mówimy o funkcji skrótu, mamy na myśli MD5, SHA-1 lub coś w rodzaju .hashCode()metody Javy , która zamienia niektóre dane wejściowe w jedną liczbę. Jednak domena tego numeru (tj. Jest wartością maksymalną) jest bardzo mało prawdopodobne, aby mieć taki sam rozmiar jak tablica mieszająca, w której próbujesz przechowywać dane. (MD5 to 16 bajtów, SHA-1 to 20 bajtów i .hashCode()to int- 4 bajty).

Twoje pytanie dotyczy zatem następnego kroku - kiedy mamy funkcję skrótu, która może zamapować dowolne dane wejściowe na liczby, jak umieścić je w strukturze danych o określonym rozmiarze? Z inną funkcją, zwaną także „funkcją skrótu”!

Trywialnym przykładem takiej funkcji jest modulo ; możesz łatwo odwzorować liczbę dowolnych rozmiarów na określony indeks w tablicy za pomocą modulo. Zostało to wprowadzone w CLRS jako „metoda podziału”:

$k$$m$$k$$m$

$h(k) = k$$m$

...

$m$$m$$m = 2^p$$h(k)$$p$$k$

~ Wprowadzenie do algorytmów, § 11.3.1 - CLRS

$m$

Java HashMapużywa zmodyfikowanej wersji metody podziału, która wykonuje krok wstępnego przetwarzania w celu uwzględnienia słabych .hashCode()implementacji, dzięki czemu może korzystać z tablic potęgi dwóch rozmiarów. Możesz dokładnie zobaczyć, co dzieje się w .getEntry()metodzie (komentarze są moje):

 // hash() transforms key.hashCode() to protect against bad hash functions
 int hash = (key == null) ? 0 : hash(key.hashCode());
 // indexOf() converts the resulting hash to a value between 0 and table.length-1
 for (Entry<K,V> e = table[indexFor(hash, table.length)];
     ...

_{Java 8 przyniosła przepisanie, HashMapktórego jest jeszcze szybsze, ale trochę trudniejsze do odczytania. Jednak używa tej samej ogólnej zasady do wyszukiwania indeksu.}