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

10

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?

Bar Foo
źródło

Odpowiedzi:

25

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.

David Richerby
źródło
1
Dzięki. :) Mój błąd polegał na myśleniu o funkcji skrótu z mieszaniem, takiej jak MD5 lub SHA. Ale skrót może oczywiście być liczbą całkowitą, o czym nie myślałem. Teraz, gdy wiem, czego szukać, nawet szybko znalazłem dobry przykład: funkcja skrótu PHP: github.com/php/php-src/blob/PHP-5.6.10/Zend/zend_hash.h#L237
Foo Bar
13
@FooBar: MD5 i SHA również obliczają pojedyncze liczby z danych wejściowych, tak często mówi się o skrótach w postaci szesnastkowej. Podobnie jak adresy pamięci rzadko są uwzględniane w systemie dziesiętnym.
nperson325681
4
Plus, MD5 itp. Są zbyt długie, aby można było ich używać bezpośrednio jako indeksu tablicy. Możliwe byłoby użycie pewnej części skrótu, na przykład niższych n bitów.
chirlu
6

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=xmore52

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.nthn(sizeofelement)

Zło
źródło
1
A skąd to wyszukiwanie wie, gdzie w tabeli jest skrót? To nie jest adres uporządkowany ani sprzętowy.
Foo Bar
Dajesz ciąg znaków, np. „Xcnvb”, więc obliczony skrót daje indeks tablicy, „xcnvb” jest twoim elementem do wyszukiwania, 8 to indeks w tabeli. Jest uporządkowany skinieniem głowy, skrót zwraca miejsce do elementu retreive. Ten element został tam umieszczony przez tę samą funkcję. Sprzęt nie ma tu nic do roboty. Podajesz tablicę, funkcję skrótu i ​​obliczasz skrót, aby uzyskać indeks w tablicy, to samo w retreival. Tablica nie jest sortowana, również nie jest pełna. h(xdonvb)=8
Zły
Ale nie każdy indeks zostanie wypełniony. Jeśli mam hash 1, 4, 8, 90 i 223 wypełniony danymi, w jaki sposób wyszukiwanie znajduje właściwe miejsce? W tym przypadku indeks „90” znajduje się na pozycji 4, ponieważ większość innych indeksów nie istnieje. A pusty hashtable nie ma nieskończonej wielkości i ma wszystkie możliwe pozycje !?
Foo Bar
H.zaH.za(h(xdonvb))=H.za[90]
Funkcja skrótu nie zwraca indeksu do tablicy. Zamiast tego zwraca przewidywalną liczbę, którą można zmapować do tablicy. Zwykle odbywa się to za pomocą operatora modułu z liczbą segmentów tabeli mieszającej jako drugiego operandu.
Christopher Schultz
3

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”:

kmkm

h(k)=km

...

mmm=2)ph(k)pk

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

dimo414
źródło