Szukam wyjaśnienia, jak działa tabela skrótów - w prostym języku angielskim dla takiego prostaka jak ja!

Na przykład wiem, że wymaga klucza, oblicza skrót (szukam wyjaśnienia, w jaki sposób), a następnie wykonuje jakieś modulo, aby ustalić, gdzie leży w tablicy, w której przechowywana jest wartość, ale tam kończy się moja wiedza .

Czy ktoś może wyjaśnić proces?

Edycja: Nie pytam konkretnie o sposób obliczania kodów skrótu, ale ogólny przegląd działania tabeli skrótów.

Oto wyjaśnienie w kategoriach laika.

Załóżmy, że chcesz wypełnić bibliotekę książkami, a nie tylko je tam umieścić, ale chcesz łatwo znaleźć je ponownie, gdy będziesz ich potrzebować.

Więc decydujesz, że jeśli osoba, która chce przeczytać książkę, zna tytuł książki i dokładny tytuł do uruchomienia, to wszystko, co powinien wziąć. Dzięki tytułowi osoba z pomocą bibliotekarza powinna łatwo i szybko znaleźć książkę.

Jak możesz to zrobić? Cóż, oczywiście możesz zachować jakąś listę miejsc, w których umieścisz każdą książkę, ale wtedy masz taki sam problem jak przeszukiwanie biblioteki, musisz przeszukać listę. To prawda, że ​​lista byłaby mniejsza i łatwiejsza do przeszukiwania, ale nadal nie chcesz szukać sekwencyjnie od jednego końca biblioteki (lub listy) do drugiego.

Chcesz czegoś, co z tytułem książki może od razu dać ci właściwe miejsce, więc wystarczy, że przejdziesz na właściwą półkę i podniesiesz książkę.

Ale jak można to zrobić? Cóż, z odrobiną ostrożności, kiedy zapełnisz bibliotekę i dużo pracy, kiedy zapełnisz bibliotekę.

Zamiast po prostu zapełniać bibliotekę od jednego końca do drugiego, wymyślacie sprytną, małą metodę. Ty bierzesz tytuł książki, przeglądasz mały program komputerowy, który wypluwa numer półki i numer miejsca na półce. Tutaj umieścisz książkę.

Piękno tego programu polega na tym, że później, gdy ktoś wraca, aby przeczytać książkę, ponownie podajesz tytuł w programie i odzyskujesz ten sam numer półki i numer miejsca, które pierwotnie podano, a to jest gdzie znajduje się książka.

Program, jak już wspomniano inni, nazywa się algorytmem mieszającym lub obliczeniem skrótu i ​​zwykle działa na podstawie pobranych do niego danych (w tym przypadku tytułu książki) i oblicza z niego liczbę.

Dla uproszczenia załóżmy, że po prostu konwertuje każdą literę i symbol na liczbę i sumuje je wszystkie. W rzeczywistości jest to o wiele bardziej skomplikowane, ale na razie zostawmy to.

Piękno takiego algorytmu polega na tym, że jeśli wielokrotnie wprowadzasz do niego te same dane wejściowe, za każdym razem będzie wyrzucał tę samą liczbę.

Ok, więc w zasadzie tak działa tabela skrótów.

Następują rzeczy techniczne.

Po pierwsze, jest to liczba. Zwykle dane wyjściowe takiego algorytmu mieszającego mieszczą się w zakresie pewnej dużej liczby, zwykle znacznie większej niż miejsce w tabeli. Powiedzmy na przykład, że mamy w bibliotece miejsce na dokładnie milion książek. Wynik obliczeń skrótu może mieścić się w zakresie od 0 do miliarda, co jest wartością znacznie wyższą.

Więc co robimy? Używamy czegoś, co nazywa się obliczaniem modułu, co w zasadzie mówi, że jeśli policzyłeś do pożądanej liczby (tj. Miliarda), ale chciałeś pozostać w znacznie mniejszym zakresie, za każdym razem, gdy osiągniesz limit tego mniejszego zakresu, zaczniesz od nowa 0, ale musisz śledzić, jak daleko w dużej sekwencji doszedłeś.

Powiedz, że wynik algorytmu skrótu jest w zakresie od 0 do 20, a wartość 17 pochodzi z określonego tytułu. Jeśli biblioteka ma tylko 7 książek, liczysz 1, 2, 3, 4, 5, 6, a kiedy dojdziesz do 7, zaczynasz od 0. Ponieważ musimy liczyć 17 razy, mamy 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3, a ostateczna liczba to 3.

Oczywiście obliczenia modułu nie są wykonywane w ten sposób, lecz z podziałem i resztą. Pozostała część podzielenia 17 przez 7 wynosi 3 (7 przechodzi 2 razy w 17 przy 14, a różnica między 17 a 14 wynosi 3).

W ten sposób umieścisz książkę w polu nr 3.

To prowadzi do następnego problemu. Kolizje Ponieważ algorytm nie ma sposobu na rozmieszczenie książek w taki sposób, aby dokładnie wypełniały bibliotekę (lub tablicę skrótów, jeśli chcesz), niezmiennie kończy się obliczaniem liczby, która była wcześniej używana. W sensie bibliotecznym, kiedy dojdziesz do półki i numeru miejsca, w którym chcesz umieścić książkę, już tam jest książka.

Istnieją różne metody obsługi kolizji, w tym uruchamianie danych w jeszcze innym obliczeniu, aby uzyskać inne miejsce w tabeli ( podwójne haszowanie ) lub po prostu znaleźć miejsce w pobliżu miejsca, które otrzymałeś (tj. Tuż obok poprzedniej książki, zakładając miejsce było również znane jako sondowanie liniowe ). Oznaczałoby to, że masz trochę do roboty przy próbie znalezienia książki później, ale nadal jest to lepsze niż po prostu rozpoczynanie na jednym końcu biblioteki.

Wreszcie, w pewnym momencie możesz chcieć umieścić w bibliotece więcej książek, niż pozwala biblioteka. Innymi słowy, musisz zbudować większą bibliotekę. Ponieważ dokładne miejsce w bibliotece zostało obliczone na podstawie dokładnego i aktualnego rozmiaru biblioteki, wynika z tego, że jeśli zmienisz rozmiar biblioteki, może być konieczne znalezienie nowych miejsc dla wszystkich książek, ponieważ obliczenia zostały wykonane w celu znalezienia ich miejsc zmienił się.

Mam nadzieję, że to wyjaśnienie było trochę bardziej przyziemne niż wiadra i funkcje :)

Użycie i żargon:

1. Tabele skrótów służą do szybkiego przechowywania i pobierania danych (lub rekordów).
2. Rekordy są przechowywane w wiadrach za pomocą klawiszy skrótu
3. Klucze mieszania są obliczane przez zastosowanie algorytmu mieszającego do wybranej wartości ( wartości klucza ) zawartej w rekordzie. Ta wybrana wartość musi być wspólną wartością dla wszystkich rekordów.
4. Każdy segment może mieć wiele rekordów uporządkowanych w określonej kolejności.

Przykład świata rzeczywistego:

Firma Hash & Co. , założona w 1803 r. I nie posiadająca żadnej technologii komputerowej, dysponowała w sumie 300 szafkami na dokumenty, aby przechowywać szczegółowe informacje (dane) dla swoich około 30 000 klientów. Każdy folder plików został wyraźnie oznaczony numerem klienta, unikalnym numerem od 0 do 29 999.

Urzędnicy zajmujący się archiwizacją w tamtym czasie musieli szybko pobierać i przechowywać dane klientów dla pracujących pracowników. Personel zdecydował, że bardziej efektywne będzie zastosowanie metodologii mieszania do przechowywania i odzyskiwania ich zapisów.

Aby złożyć rekord klienta, pracownicy archiwizacji użyliby unikalnego numeru klienta zapisanego w folderze. Używając tego numeru klienta, modulowaliby klucz skrótu o 300, aby zidentyfikować szafkę, w której się on znajduje. Gdy otworzą szafkę, odkryją, że zawiera wiele folderów uporządkowanych według numeru klienta. Po zidentyfikowaniu właściwej lokalizacji po prostu wślizgną ją.

Aby pobrać rekord klienta, urzędnicy zajmujący się archiwizacją otrzymaliby numer klienta na kartce papieru. Używając tego unikalnego numeru klienta ( klucza skrótu ), modulowaliby go o 300, aby ustalić, która szafka na dokumenty miała folder klientów. Gdy otworzyli szafkę na dokumenty, odkryli, że zawiera ona wiele folderów uporządkowanych według numeru klienta. Przeszukując rekordy, szybko znajdą folder klienta i go odzyskają.

W naszym prawdziwym przykładzie nasze wiadra to szafki na dokumenty, a nasze rekordy to foldery plików .

Ważną rzeczą do zapamiętania jest to, że komputery (i ich algorytmy) radzą sobie z liczbami lepiej niż z łańcuchami. Tak więc dostęp do dużej tablicy za pomocą indeksu jest znacznie szybszy niż dostęp sekwencyjny.

Jak wspomniał Simon, moim zdaniem bardzo ważne jest to, że część haszująca polega na przekształceniu dużej przestrzeni (o dowolnej długości, zwykle łańcuchach itp.) I odwzorowaniu jej na małą przestrzeń (o znanej wielkości, zwykle liczbach) w celu indeksowania. To bardzo ważne, aby pamiętać!

W powyższym przykładzie około 30 000 możliwych klientów jest odwzorowanych na mniejszą przestrzeń.

Główną ideą jest podzielenie całego zestawu danych na segmenty, aby przyspieszyć wyszukiwanie, które zwykle zajmuje dużo czasu. W powyższym przykładzie każda z 300 szafek na dokumenty zawiera (statystycznie) około 100 rekordów. Przeszukiwanie (niezależnie od kolejności) 100 rekordów jest znacznie szybsze niż zajmowanie się 30 000.

Być może zauważyłeś, że niektórzy już to robią. Ale zamiast opracowywać metodologię mieszania w celu wygenerowania klucza skrótu, w większości przypadków po prostu użyją pierwszej litery nazwiska. Więc jeśli masz 26 szafek na dokumenty, z których każda zawiera literę od A do Z, teoretycznie właśnie podzieliłeś swoje dane i usprawniłeś proces archiwizacji i wyszukiwania.

Mam nadzieję że to pomoże,

Jeach!

To okazuje się być dość głębokim obszarem teorii, ale podstawowy zarys jest prosty.

Zasadniczo funkcja skrótu jest po prostu funkcją, która bierze rzeczy z jednej spacji (powiedzmy ciągów o dowolnej długości) i mapuje je na przestrzeń przydatną do indeksowania (powiedzmy liczb całkowitych bez znaku).

Jeśli masz tylko niewielką przestrzeń rzeczy do mieszania, możesz uniknąć interpretacji tych rzeczy jako liczb całkowitych i gotowe (np. Ciągi 4 bajtów)

Zazwyczaj jednak masz znacznie większą przestrzeń. Jeśli przestrzeń rzeczy, na którą zezwalasz jako klucze, jest większa niż przestrzeń rzeczy, których używasz do indeksowania (twój uint32 lub cokolwiek innego), to nie możesz mieć dla nich unikalnej wartości. Gdy dwie lub więcej rzeczy łączy się z tym samym rezultatem, będziesz musiał odpowiednio obsłużyć nadmiarowość (jest to zwykle określane jako kolizja, a sposób, w jaki sobie z tym poradzisz lub nie, będzie zależeć nieco od tego, kim jesteś używając skrótu dla).

Oznacza to, że chcesz, aby raczej nie miał tego samego rezultatu, i prawdopodobnie również naprawdę chciałbyś, aby funkcja skrótu była szybka.

Równoważenie tych dwóch właściwości (i kilku innych) spowodowało, że wiele osób było zajętych!

W praktyce zwykle powinieneś być w stanie znaleźć funkcję, o której wiadomo, że działa dobrze dla twojej aplikacji i z niej korzystać.

Teraz, aby działało to jako skrót: Wyobraź sobie, że nie obchodzi Cię zużycie pamięci. Następnie możesz utworzyć tablicę tak długo, jak zestaw indeksowania (na przykład wszystkie uint32). Gdy dodajesz coś do tabeli, haszujesz jej klucz i patrzysz na tablicę pod tym indeksem. Jeśli nic tam nie ma, stawiasz tam swoją wartość. Jeśli coś już tam jest, dodajesz ten nowy wpis do listy rzeczy pod tym adresem, wraz z wystarczającą ilością informacji (twój oryginalny klucz lub coś sprytnego), aby znaleźć, który wpis należy do którego klucza.

W miarę długiego wpisu każdy wpis w tablicy hasht (tablicy) jest albo pusty, albo zawiera jeden wpis lub listę wpisów. Pobieranie jest proste jak indeksowanie do tablicy i albo zwracanie wartości, albo przeglądanie listy wartości i zwracanie właściwej.

Oczywiście w praktyce zazwyczaj nie możesz tego zrobić, marnuje zbyt dużo pamięci. Więc robisz wszystko w oparciu o rzadką tablicę (gdzie jedynymi wpisami są te, których faktycznie używasz, wszystko inne jest domyślnie zerowe).

Istnieje wiele schematów i sztuczek, które poprawiają to działanie, ale to są podstawy.

Wiele odpowiedzi, ale żadna z nich nie jest bardzo wizualna , a tabele skrótów można łatwo „kliknąć” po wizualizacji.

Tabele skrótów są często implementowane jako tablice połączonych list. Jeśli wyobrażamy sobie tabelę przechowującą nazwiska ludzi, po kilku wstawkach można ją ()ułożyć w pamięci, jak poniżej, gdzie zamknięte liczby są wartościami skrótu tekstu / nazwy.

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

Kilka punktów:

• każdy z wpisów w tablicy (indeksy [0], [1]...) jest znany jako segment i rozpoczyna - być może pustą - połączoną listę wartości ( w tym przykładzie również elementów - nazwisk osób )
• każda wartość (np. "fred"z haszowaniem 42) jest powiązana z segmentu [hash % number_of_buckets]np 42 % 10 == [2].; %to operator modulo - reszta podzielona przez liczbę segmentów
• wiele wartości danych może kolidować w tym samym segmencie i być z nimi połączone, najczęściej dlatego, że ich wartości skrótu kolidują po operacji modulo (np. 42 % 10 == [2]i 9282 % 10 == [2]), ale czasami, ponieważ wartości skrótu są takie same (np. "fred"i "jane"oba są pokazane z skrótem 42powyżej)
  • większość tabel skrótów obsługuje kolizje - z nieznacznie zmniejszoną wydajnością, ale bez pomyłek funkcjonalnych - przez porównanie pełnej wartości (tutaj tekst) poszukiwanej wartości lub wstawianej do każdej wartości już na liście połączonej w segmencie mieszanym

Długości połączonych listów odnoszą się do współczynnika obciążenia, a nie liczby wartości

Jeśli rozmiar tabeli rośnie, tabele skrótów zaimplementowane jak wyżej mają tendencję do zmiany rozmiaru (tj. Tworzenia większej tablicy segmentów, tworzenia nowych / zaktualizowanych powiązanych list, usuwania starej tablicy), aby zachować stosunek wartości do segmentów (inaczej ładowanie współczynnik ) gdzieś w przedziale od 0,5 do 1,0.

Hans podaje faktyczną formułę dla innych współczynników obciążenia w komentarzu poniżej, ale dla wartości orientacyjnych: przy współczynniku obciążenia 1 i funkcji skrótu siły kryptograficznej 1 / e (~ 36,8%) wiader będzie zwykle pusty, kolejne 1 / e (~ 36,8%) ma jeden element, 1 / (2e) lub ~ 18,4% dwa elementy, 1 / (3! E) około 6,1% trzy elementy, 1 / (4! E) lub ~ 1,5% cztery elementy, 1 / (5! E) ~ .3% ma pięć itd. - średnia długość łańcucha z niepustych wiader wynosi ~ 1,58 bez względu na liczbę elementów w tabeli (tj. Czy jest 100 elementów i 100 wiader, czy 100 milionów elementów i 100 milionów segmentów), dlatego mówimy, że wyszukiwanie / wstawianie / usuwanie są operacjami o stałym czasie O (1) .

Jak tabela skrótów może kojarzyć klucze z wartościami

Biorąc pod uwagę implementację tabeli skrótów, jak opisano powyżej, możemy sobie wyobrazić utworzenie typu wartości, takiego jak struct Value { string name; int age; };porównanie funkcji równości i funkcji skrótu, które patrzą tylko na namepole (ignorowanie wieku), a następnie dzieje się coś cudownego: możemy przechowywać Valuerekordy jak {"sue", 63}w tabeli , a następnie wyszukaj „pozwać”, nie znając jej wieku, znaleźć przechowywaną wartość i odzyskać, a nawet zaktualizować jej wiek
- wszystkiego najlepszego, Sue - co ciekawe nie zmienia wartości skrótu, więc nie wymaga przeniesienia rekordu Sue do innego wiadro.

Gdy to robimy, używamy tabeli skrótów jako asocjacyjnego kontenera, czyli mapy , a przechowywane w niej wartości można uznać za składające się z klucza (nazwy) i jednego lub więcej innych pól, które nadal są - myląco - wartościami ( w moim przykładzie tylko wiek). Implementacja tabeli skrótów używana jako mapa jest znana jako mapa skrótów .

Kontrastuje to z przykładem wcześniejszym w tej odpowiedzi, w którym zapisaliśmy dyskretne wartości, takie jak „sue”, które można by uznać za własny klucz: tego rodzaju użycie jest znane jako zestaw skrótów .

Istnieją inne sposoby implementacji tabeli skrótów

Nie wszystkie tabele skrótów używają list połączonych (znanych jako oddzielne tworzenie łańcuchów ), ale większość z nich ma tę funkcję, ponieważ główna alternatywna funkcja mieszania zamkniętego (inaczej adresowanie otwarte ) - szczególnie przy obsługiwanych operacjach usuwania - ma mniej stabilne właściwości wydajnościowe z podatnymi na kolizję kluczami / funkcje skrótu.

Kilka słów o funkcjach skrótu

Silne haszowanie ...

Zadaniem funkcji skrótu, która w najgorszym przypadku minimalizuje kolizje, jest ogólne rozpylanie klawiszy wokół segmentów tabeli skrótów skutecznie losowo, zawsze generując tę ​​samą wartość skrótu dla tego samego klucza. Nawet jeden bit zmieniający się w dowolnym miejscu klucza idealnie - losowo - przerzuciłby około połowy bitów w wynikowej wartości skrótu.

Zwykle jest to zaaranżowane z matematyki zbyt skomplikowanej dla mnie, aby się na niej natknąć. Wspomnę o jednym łatwym do zrozumienia sposobie - nie najbardziej skalowalnym lub przyjaznym dla pamięci podręcznej, ale z natury eleganckim (jak szyfrowanie za pomocą jednorazowego pada!) - ponieważ myślę, że pomaga to osiągnąć pożądane cechy wymienione powyżej. Powiedzmy, że haszowałeś 64-bitowe doubles - możesz utworzyć 8 tabel z 256 losowymi liczbami (kod poniżej), a następnie użyć każdego 8-bitowego / 1-bajtowego wycinka doublereprezentacji pamięci do indeksowania do innej tabeli, XOR losowe liczby, których szukasz. Dzięki takiemu podejściu łatwo zauważyć, że nieco (w sensie cyfr binarnych) zmienia się w dowolnym miejscu w doublewyniku, że inna liczba losowa jest sprawdzana w jednej z tabel, i całkowicie nieskorelowana wartość końcowa.

// note caveats above: cache unfriendly (SLOW) but strong hashing...
size_t random[8][256] = { ...random data... };
const char* p = (const char*)&my_double;
size_t hash = random[0][p[0]] ^ random[1][p[1]] ^ ... ^ random[7][p[7]];

Słabe, ale często szybkie mieszanie ...

Wiele funkcji mieszających bibliotek przekazuje liczby całkowite przez niezmienione (znane jako funkcja trywialna lub funkcja skrótu tożsamości ); jest to druga skrajność silnego hashowania opisanego powyżej. Skrót tożsamości jest wyjątkowopodatne na kolizje w najgorszych przypadkach, ale nadzieja jest taka, że ​​w dość powszechnym przypadku kluczy całkowitych, które mają tendencję do zwiększania (być może z pewnymi lukami), zamieniają się w kolejne segmenty pozostawiając mniej pustych niż losowych liści mieszających (nasze ~ 36,8 % przy wspomnianym wcześniej współczynniku obciążenia 1), tym samym powodując mniej kolizji i mniej dłuższych połączonych list kolidujących elementów, niż osiąga się dzięki przypadkowym mapowaniom. Świetnie jest także zaoszczędzić czas potrzebny do wygenerowania silnego skrótu, a jeśli klucze zostaną wyszukane, aby można je było znaleźć w pobliskich segmentach pamięci, poprawiając trafienia w pamięci podręcznej. Kiedy klucze nie zwiększają się ładnie, mamy nadzieję, że będą na tyle przypadkowe, że nie będą potrzebować silnej funkcji skrótu, aby całkowicie losowo umieścić je w segmencie.

Jesteście bardzo bliscy wyjaśnienia tego w pełni, ale brakuje wam kilku rzeczy. Tablica skrótów jest tylko tablicą. Sama tablica będzie zawierać coś w każdym gnieździe. Co najmniej będziesz przechowywać wartość skrótu lub samą wartość w tym miejscu. Oprócz tego możesz również przechowywać połączoną / powiązaną listę wartości, które kolidowały w tym gnieździe, lub możesz użyć metody otwartego adresowania. Możesz także zapisać wskaźnik lub wskaźniki do innych danych, które chcesz odzyskać z tego gniazda.

Należy zauważyć, że sama wartość skrótu zasadniczo nie wskazuje szczeliny, w której należy umieścić wartość. Na przykład wartość skrótu może być ujemną liczbą całkowitą. Oczywiście liczba ujemna nie może wskazywać na lokalizację tablicy. Ponadto wartości skrótu będą miały wielokrotnie większe wartości niż dostępne gniazda. Dlatego sama tablica mieszająca musi wykonać inne obliczenia, aby dowiedzieć się, w którym szczelinie powinna znajdować się wartość. Odbywa się to za pomocą operacji matematycznej modułu, takiej jak:

uint slotIndex = hashValue % hashTableSize;

Ta wartość jest miejscem, w które wejdzie. W adresowaniu otwartym, jeśli pole jest już wypełnione inną wartością skrótu i ​​/ lub innymi danymi, operacja modułu zostanie uruchomiona ponownie w celu znalezienia następnego pola:

slotIndex = (remainder + 1) % hashTableSize;

Przypuszczam, że mogą istnieć inne bardziej zaawansowane metody określania indeksu szczelin, ale jest to typowa metoda, którą widziałem ... byłby zainteresowany innymi, które działałyby lepiej.

W przypadku metody modułowej, jeśli masz tabelę powiedzmy wielkość 1000, każda wartość skrótu między 1 a 1000 przejdzie do odpowiedniego slotu. Wszelkie wartości ujemne i wartości większe niż 1000 będą potencjalnie kolidować z wartościami szczelin. Szanse na to są zależne zarówno od metody mieszania, jak i od liczby dodanych elementów do tabeli mieszania. Ogólnie rzecz biorąc, najlepszą praktyką jest, aby wielkość tablicy mieszającej była taka, aby całkowita liczba dodanych do niej wartości wynosiła tylko około 70% jej wielkości. Jeśli funkcja haszująca dobrze sobie radzi z równomierną dystrybucją, generalnie napotyka się bardzo mało kolizji lub braków w kolizjach i działa bardzo szybko zarówno w przypadku operacji wyszukiwania, jak i zapisu. Jeśli łączna liczba wartości do dodania nie jest wcześniej znana, dobrze oszacuj, używając dowolnych środków,

Mam nadzieję, że to pomogło.

PS - W C # GetHashCode()metoda jest dość wolna i powoduje kolizje wartości rzeczywistych w wielu testowanych przeze mnie warunkach. Dla prawdziwej zabawy zbuduj własną funkcję skrótu i ​​postaraj się, aby NIGDY nie kolidowała z konkretnymi danymi, które haszujesz, działała szybciej niż GetHashCode i miała dość równomierną dystrybucję. Zrobiłem to używając wartości hashcode zamiast długiego zamiast int i działa całkiem dobrze na 32 milionach wartości hash w wartościach hashable z 0 kolizjami. Niestety nie mogę udostępnić kodu, ponieważ należy on do mojego pracodawcy ... ale mogę ujawnić, że jest to możliwe w przypadku niektórych domen danych. Gdy możesz to osiągnąć, tablica skrótów jest BARDZO szybka. :)

Oto, jak to działa w moim rozumieniu:

Oto przykład: zobrazuj cały stół jako serię wiader. Załóżmy, że masz implementację z alfanumerycznymi kodami skrótu i ​​masz jedno wiadro na każdą literę alfabetu. Ta implementacja umieszcza każdy element, którego kod skrótu zaczyna się od określonej litery w odpowiednim segmencie.

Załóżmy, że masz 200 obiektów, ale tylko 15 z nich ma kody skrótu zaczynające się na literę „B.” Tabela skrótów musiałaby tylko wyszukiwać i przeszukiwać 15 obiektów w wiadrze „B”, a nie wszystkie 200 obiektów.

Jeśli chodzi o obliczanie kodu skrótu, nie ma w nim nic magicznego. Celem jest po prostu, aby różne obiekty zwracały różne kody, a równe obiekty zwracały równe kody. Możesz napisać klasę, która zawsze zwraca tę samą liczbę całkowitą co kod skrótu dla wszystkich instancji, ale zasadniczo zniszczyłbyś użyteczność tabeli skrótów, ponieważ stałaby się tylko jednym wielkim wiadrem.

Krótkie i słodkie:

Tabela skrótów zawija tablicę, nazwijmy ją internalArray. Elementy są wstawiane do tablicy w ten sposób:

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

Czasami dwa klucze mają skrót do tego samego indeksu w tablicy i chcesz zachować obie wartości. Lubię przechowywać obie wartości w tym samym indeksie, który można łatwo kodować, tworząc internalArraytablicę połączonych list:

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

Tak więc, jeśli chciałbym pobrać element ze swojej tabeli skrótów, mógłbym napisać:

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

Operacje usuwania są równie proste do napisania. Jak widać, wstawianie, wyszukiwanie i usuwanie z naszej listy połączonych list to prawie O (1).

Kiedy nasz Array wewnętrzny zapełni się, być może przy pojemności około 85%, możemy zmienić rozmiar tablicy wewnętrznej i przenieść wszystkie elementy ze starej tablicy do nowej.

To jest jeszcze prostsze.

Tablica hashtable to nic innego jak tablica (zwykle rzadka ) wektorów zawierających pary klucz / wartość. Maksymalny rozmiar tej tablicy jest zwykle mniejszy niż liczba elementów w zestawie możliwych wartości dla typu danych przechowywanych w tablicy mieszającej.

Algorytm mieszania służy do generowania indeksu w tej tablicy na podstawie wartości elementu, który będzie przechowywany w tablicy.

W tym miejscu dochodzi do przechowywania wektorów par klucz / wartość w tablicy. Ponieważ zestaw wartości, które mogą być indeksami w tablicy, jest zwykle mniejszy niż liczba wszystkich możliwych wartości, jakie może mieć typ, możliwe, że Twój skrót algorytm wygeneruje tę samą wartość dla dwóch oddzielnych kluczy. Dobry algorytm mieszania uniemożliwi to jak najwięcej (który jest dlaczego to jest spychany do rodzaju zwykle dlatego, że ma konkretne informacje, które ogólny algorytm mieszania nie może wiedzieć), ale nie da się zapobiec.

Z tego powodu możesz mieć wiele kluczy, które wygenerują ten sam kod skrótu. Kiedy tak się dzieje, elementy w wektorze są iterowane i następuje bezpośrednie porównanie między kluczem w wektorze a kluczem, który jest przeglądany. Jeśli zostanie znaleziony, świetny, a wartość związana z kluczem zostanie zwrócona, w przeciwnym razie nic nie zostanie zwrócone.

Bierzesz mnóstwo rzeczy i tablicę.

Dla każdej rzeczy tworzysz dla niej indeks, zwany skrótem. Ważną rzeczą w haszu jest to, że bardzo „rozprasza”; nie chcesz, aby dwie podobne rzeczy miały podobne hasze.

Umieszczasz swoje rzeczy w tablicy w miejscu wskazanym przez skrót. Przy jednym haszu może znajdować się więcej niż jedna rzecz, więc przechowujesz je w tablicach lub w innej odpowiedniej formie, którą zazwyczaj nazywamy wiadrem.

Kiedy szukasz rzeczy w haszu, przechodzisz przez te same kroki, obliczasz wartość skrótu, a następnie widzisz, co jest w wiadrze w tej lokalizacji i sprawdzasz, czy tego właśnie szukasz.

Kiedy twoje hashowanie działa dobrze i twoja tablica jest wystarczająco duża, w danym indeksie tablicy będzie tylko kilka rzeczy, więc nie będziesz musiał za dużo patrzeć.

Aby uzyskać punkty bonusowe, ustaw je tak, aby przy dostępie do tabeli skrótów przenosi znalezioną rzecz (jeśli w ogóle) na początek wiadra, więc następnym razem będzie to sprawdzane.

Wszystkie dotychczasowe odpowiedzi są dobre i dotyczą różnych aspektów działania tablicy mieszającej. Oto prosty przykład, który może być pomocny. Powiedzmy, że chcemy przechowywać niektóre elementy zawierające małe litery alfabetu jako klucze.

Jak wyjaśniono Simon, funkcja skrótu służy do mapowania z dużej przestrzeni na małą przestrzeń. Prosta, naiwna implementacja funkcji skrótu w naszym przykładzie może wziąć pierwszą literę ciągu i odwzorować ją na liczbę całkowitą, więc „aligator” ma kod skrótu 0, „pszczoła” ma kod skrótu 1, „ zebra ”wynosiłaby 25 itd.

Następnie mamy tablicę 26 segmentów (może to być ArrayLists w Javie) i umieszczamy element w segmencie odpowiadającym kodowi skrótu naszego klucza. Jeśli mamy więcej niż jeden element, który ma klucz zaczynający się na tę samą literę, będą mieli ten sam kod skrótu, więc wszyscy przejdą do koszyka dla tego kodu skrótu, więc konieczne będzie przeprowadzenie wyszukiwania liniowego w segmencie, aby znajdź konkretny przedmiot.

W naszym przykładzie, gdybyśmy mieli tylko kilkadziesiąt pozycji z kluczami obejmującymi alfabet, działałoby to bardzo dobrze. Gdybyśmy mieli milion pozycji lub wszystkie klucze zaczęły się od „a” lub „b”, wówczas nasza tabela skrótów nie byłaby idealna. Aby uzyskać lepszą wydajność, potrzebowalibyśmy innej funkcji skrótu i ​​/ lub większej liczby segmentów.

Oto inny sposób na to spojrzeć.

Zakładam, że rozumiesz pojęcie tablicy A. Jest to coś, co obsługuje operację indeksowania, gdzie możesz dostać się do elementu Ith, A [I], w jednym kroku, bez względu na to, jak duże jest A.

Na przykład, jeśli chcesz przechowywać informacje o grupie ludzi, którzy wszyscy mają różny wiek, prostym sposobem byłoby posiadanie wystarczająco dużej tablicy i wykorzystanie wieku każdej osoby jako indeksu w tablicy. W ten sposób możesz mieć dostęp do informacji dowolnej osoby w jednym kroku.

Ale oczywiście może być więcej niż jedna osoba w tym samym wieku, więc to, co umieścisz w tablicy przy każdym wpisie, to lista wszystkich osób w tym wieku. Dzięki temu możesz uzyskać dostęp do informacji o konkretnej osobie w jednym kroku plus trochę wyszukiwania na tej liście (zwanej „wiadrem”). Spowalnia tylko wtedy, gdy jest tak wiele osób, że wiadra stają się duże. Następnie potrzebujesz większej tablicy i innego sposobu uzyskania większej ilości informacji identyfikujących osobę, takich jak kilka pierwszych liter nazwiska, zamiast używania wieku.

To podstawowy pomysł. Zamiast korzystać z wieku, można użyć dowolnej funkcji osoby, która zapewnia dobry rozkład wartości. To jest funkcja skrótu. Jakby można wziąć co trzeci bit reprezentacji ASCII nazwiska osoby, zakodowany w pewnej kolejności. Liczy się tylko to, że nie chcesz, aby zbyt wiele osób hashowało do tego samego wiadra, ponieważ prędkość zależy od pozostawienia małych wiader.

Sposób obliczania skrótu zwykle nie zależy od tablicy skrótów, ale od dodanych do niej elementów. W bibliotekach klasy frameworks / base, takich jak .net i Java, każdy obiekt ma metodę GetHashCode () (lub podobną) zwracającą kod skrótu dla tego obiektu. Idealny algorytm kodu skrótu i ​​dokładna implementacja zależą od danych reprezentowanych przez obiekt.

Tabela skrótów całkowicie działa na tym, że praktyczne obliczenia są zgodne z modelem maszyny o swobodnym dostępie, tj. Wartość pod dowolnym adresem w pamięci może być dostępna w czasie O (1) lub w stałym czasie.

Tak więc, jeśli mam wszechświat kluczy (zestaw wszystkich możliwych kluczy, których mogę użyć w aplikacji, np. Numer rzutu dla studenta, jeśli jest to 4 cyfry, wówczas ten wszechświat jest zbiorem liczb od 1 do 9999) i sposób mapowania ich na skończony zestaw liczb wielkości, które mogę przydzielić pamięci w moim systemie, teoretycznie moja tabela skrótów jest gotowa.

Ogólnie rzecz biorąc, w aplikacjach wielkość wszechświata kluczy jest bardzo duża niż liczba elementów, które chcę dodać do tabeli mieszającej (nie chcę marnować 1 GB pamięci na mieszanie, powiedzmy, 10000 lub 100000 wartości całkowitych, ponieważ są to 32 nieco długo w reprezentacji binarnej). Używamy tego haszowania. Jest to rodzaj mieszanej operacji „matematycznej”, która mapuje mój duży wszechświat na niewielki zestaw wartości, które mogę pomieścić w pamięci. W praktycznych przypadkach często przestrzeń tablicy haszującej jest tego samego „rzędu” (big-O) co (liczba elementów * rozmiar każdego elementu), więc nie marnujemy dużo pamięci.

Teraz duży zestaw odwzorowany na mały zestaw, odwzorowanie musi być wiele do jednego. Tak więc różne klucze będą miały przydzielone to samo miejsce (niesprawiedliwe). Jest na to kilka sposobów, znam tylko dwa popularne:

• Użyj miejsca, które miało zostać przydzielone wartości, jako odwołania do listy połączonej. Na tej połączonej liście będzie przechowywana jedna lub więcej wartości, które będą znajdować się w tym samym gnieździe w wielu mapowaniach do jednego. Połączona lista zawiera także klucze, które mogą pomóc komuś, kto przychodzi poszukać. To jest jak wiele osób w tym samym mieszkaniu, kiedy przychodzi człowiek, idzie do pokoju i pyta o faceta.
• Użyj funkcji podwójnego skrótu w tablicy, która daje tę samą sekwencję wartości za każdym razem, a nie pojedynczą wartość. Kiedy idę do przechowywania wartości, widzę, czy wymagana lokalizacja pamięci jest wolna, czy zajęta. Jeśli jest bezpłatny, mogę tam zapisać swoją wartość, jeśli jest zajęty, pobieram następną wartość z sekwencji i tak dalej, aż znajdę wolne miejsce i tam zapiszę swoją wartość. Podczas przeszukiwania lub pobierania wartości wracam tą samą ścieżką, którą podała sekwencja, i w każdej lokalizacji pytam o wartość, czy jest tam, dopóki jej nie znajdę lub przeszukam wszystkie możliwe lokalizacje w tablicy.

Wprowadzenie do algorytmów CLRS zapewnia bardzo dobry wgląd w ten temat.

Dla wszystkich, którzy szukają języka programowania, oto jak to działa. Wewnętrzna implementacja zaawansowanych tablic skrótów ma wiele zawiłości i optymalizacji dla alokacji / dezalokacji pamięci i wyszukiwania, ale pomysł na najwyższym poziomie pozostanie taki sam.

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

gdzie calculate_bucket_from_val()jest funkcja haszująca, w której musi wystąpić cała magia wyjątkowości.

Zasada jest następująca: aby wstawić daną wartość, segment musi być WYJĄTKOWY I DERYWALNY Z WARTOŚCI, którą ma PRZECHOWYWAĆ.

Wiadro to dowolna przestrzeń, w której przechowywane są wartości - w tym przypadku zachowałem go jako indeks tablicy, ale może to także miejsce w pamięci.