Prosty przegląd tabeli mieszania
Jako odświeżacz, tablica skrótów jest sposobem na przechowywanie wartości pod określonym kluczem w strukturze danych. Na przykład mogę zapisać wartość "a"pod kluczem 1, a następnie odzyskać ją, wyszukując klucz 1w tabeli skrótów.
Najprostszym przykładem tabeli skrótów, którą mogę wymyślić z góry mojej głowy, jest tabela skrótów, która może przechowywać tylko liczby całkowite, gdzie kluczem do wpisu tablicy skrótów jest również przechowywana wartość. Powiedzmy, że twoja tabela ma rozmiar 8 i jest to w zasadzie tablica w pamięci:
---------------------------------
| | | | | | | | |
---------------------------------
0 1 2 3 4 5 6 7
Funkcja skrótu
Funkcje mieszania dają indeks miejsca przechowywania wartości. Dość prostą funkcją skrótu dla tej tabeli byłoby dodanie 1 do wartości, którą chcesz zapisać, a następnie zmodyfikowanie jej o 8 (rozmiar tabeli). Innymi słowy, twoją funkcją skrótu jest (n+1)%8, gdzie njest liczbą całkowitą, którą chcesz zapisać.
Wkładki
Jeśli chcesz wstawić wartość do tej tabeli skrótów, wywołujesz funkcję skrótu (w tym przypadku (n+1)%8) na wartości, którą chcesz wstawić, aby dać ci indeks. Na przykład, jeśli chcemy wstawić 14, wywołalibyśmy (14 + 1) % 8i pobrali indeks 7, więc wstawilibyśmy wartość indeksu 7.
---------------------------------
| | | | | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Podobnie możemy wstawić 33, 82 i 191 w ten sposób:
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Kolizje
Ale co się stanie, jeśli spróbujemy wstawić coś, co koliduje z wpisem? 2 powinien przejść do indeksu 3, ale jest zajęty przez 82. Istnieje wiele sposobów rozwiązania tego problemu, najprostszym jest wielokrotne wywoływanie naszej funkcji skrótu, aż znajdziemy puste miejsce.
Logika jest więc następująca:
- (2 + 1)% 8 = 3
- Indeks 3 jest pełny
- Podłącz 3 z powrotem do naszej funkcji skrótu. ( 3 + 1)% 8 = 4 , który jest pusty.
- Umieść naszą wartość w indeksie 4 .
Teraz tabela skrótów wygląda następująco, a wartość 2 jest przechowywana w indeksie 4.
---------------------------------
|191| |33 |82 |2 | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Minusem tego rozwiązania jest to, że już niedługo nasz stół się zapełni! Jeśli wiesz, że rozmiar danych jest ograniczony, nie powinno to stanowić problemu, o ile tabela jest wystarczająco duża, aby pomieścić wszystkie możliwe wartości. Jeśli chcesz mieć więcej miejsca, możesz obsługiwać kolizje w różny sposób. Wróćmy do miejsca, w którym byliśmy przed wstawieniem 2.
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Jeśli pamiętasz, (2+1)%8daje nam indeks 3, który jest brany. Jeśli nie chcesz, aby tabela skrótów się zapełniła, możesz użyć każdego indeksu tabeli jako listy połączonej i dołączyć do listy pod tym indeksem. Zamiast więc ponownie wywoływać funkcję skrótu, po prostu dodamy do listy w indeksie 3:
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Ta lista może następnie wzrosnąć tak dużo, jak pozwala na to pamięć. Mogę wstawić 18, a będzie to po prostu dołączone do 2:
-----
|18 |
-----
| 2 |
---------------------------------
|191| |33 |82 | | | |14 |
---------------------------------
0 1 2 3 4 5 6 7
Wyszukiwania
Wyszukiwanie wartości w tabeli skrótów jest szybkie, biorąc pod uwagę, że tabela skrótów ma dość duży rozmiar. Wystarczy wywołać funkcję skrótu i uzyskać indeks. Powiedzmy, że chcesz sprawdzić, czy 82 jest w twojej tabeli. Funkcja wyszukiwania wywołałaby (82+1)%8= 3i spojrzałaby na element w indeksie 3i zwróciła go za ciebie. Jeśli spojrzałeś na 16, funkcja wyszukiwania zajrzałaby do indeksu 1i zobaczyłaby, że nie istnieje.
Wyszukiwania również muszą radzić sobie z kolizjami!
Jeśli spróbujesz wyszukać wartość 2, twoja tablica skrótów będzie musiała użyć tej samej logiki kolizji, której użyto do przechowywania danych, jak przy pobieraniu danych. W zależności od sposobu działania tabeli skrótów, albo haszowałeś klucz w kółko, aż znajdziesz szukany wpis (lub znajdowałeś puste miejsce), albo iterowałeś przez połączoną listę, aż znajdziesz element (lub dotarł na koniec listy)
Podsumowanie
Tak więc tabele skrótów są dobrym sposobem na szybkie przechowywanie i dostęp do par klucz-wartość. W tym przykładzie użyliśmy tego samego klucza co wartość, ale w rzeczywistych tabelach skrótów klucze nie są tak ograniczone. Funkcje skrótu będą działać na klawiszach w celu wygenerowania indeksu, a następnie klucz / wartość można zapisać pod tym indeksem. Tabele skrótów nie są tak naprawdę przeznaczone do iteracji, chociaż jest to możliwe. Jak widać, tabele skrótów mogą zawierać wiele pustych miejsc, a ich powtarzanie byłoby stratą czasu. Nawet jeśli tabela skrótów ma logikę pomijania wyszukiwań pustych przestrzeni w swoim iteratorze, lepiej byłoby użyć struktury danych zaprojektowanej dla iteratorów, np. List połączonych.
Wyobraź sobie bibliotekę z tysiącami książek. Musisz uporządkować książki, aby móc znaleźć je według tytułu tak szybko, jak to możliwe.
Jednym (powszechnym) sposobem na to jest sortowanie książek alfabetycznie. Jeśli tytuł zaczyna się od powiedzenia „G”, znajdujesz obszar „G”, a następnie poszukaj drugiej litery, powiedz „ö”, a następnie „d”, „e”, „l”, zawężając wyszukiwanie i tak dalej , dopóki nie znajdziesz książki. Może to jednak potrwać długo, a poza tym, kiedy pojawiają się nowe książki, czasami trzeba zmienić układ, aby zrobić miejsce dla nowych osób.
To wyszukiwanie binarne. To jest dobre.
Jest jednak szybszy sposób na zrobienie tego. Załóżmy, że wyliczasz wszystkie regały i półki, a następnie dla każdej książki obliczasz specjalną, miejmy nadzieję, unikalną liczbę, która mapuje na regał / półkę, na której powinna znajdować się książka. Sposób obliczania „klucza” nie ma większego znaczenia, o ile daje losowo wyglądającą liczbę. Na przykład możesz dodać kody znaków wszystkich liter w tytule, a następnie podzielić je przez pewną liczbę pierwszą (być może nie najlepszą metodę, ale i tak działa).
To jest mieszanie. Jest to znacznie szybsze, ponieważ nie musisz przeglądać całych regałów i półek, szukając następnej litery w tytule. Hashowanie jest zwykle operacją jednorazową, chyba że masz „kolizję”, gdy dwie lub więcej książek rozwiązuje ten sam klucz. Ale to dobrze, wiesz, że leżą obok siebie i, w zależności od jakości funkcji skrótu, nie powinno być zbyt wielu pod tym samym kluczem.
Tabele skrótów mają pewne ograniczenia i kaprysy (ponowne zapisywanie / zmiana rozmiaru), które utrzymują binarne wyszukiwanie jako realnego konkurenta. Nie wszystko jest czarno-białe w odniesieniu do tego, która metoda jest lepsza. Ale to inna historia.
PS Przepraszam, że nie odpowiedziałem bezpośrednio na twoje pytanie (napisz tabelę skrótów w PHP), ale to są szczegóły i nazywa się to „programowaniem”;)
źródło
O ile wiem, tabela haszująca w PHP jest po prostu zaimplementowana poprzez:
Następnie uzyskujesz dostęp do danych za pośrednictwem połączeń, takich jak:
Za pomocą funkcji foreach () można iterować zawartość tablicy.
Najlepszym sposobem na zrozumienie tabel skrótów jest przeczytanie czegoś takiego jak http://en.wikipedia.org/wiki/Hash_table , ale z grubsza sprowadza się do tego: lewa strona każdej linii w wywołaniu array () to klucze . Te klucze zostaną poddane obliczeniu wartości skrótu, a wynikiem będzie skrót. Prawdopodobnie widziałeś już skróty MD5 lub SHA, wygląda to dość podobnie do tego. Określona część tego skrótu, zazwyczaj pierwsze znaki X, ale czasami pełny skrót, zostanie wykorzystana do zidentyfikowania tak zwanych „segmentów”, które są obszarami przechowywania wartości (prawa strona).
Następnie za każdym razem, gdy uzyskujesz dostęp do swojego hashtable, używasz klawisza, aby dostać się do wartości. Klucz zostaje ponownie obliczony na wartość skrótu, a skrót służy do szybkiego wyszukiwania powiązanej wartości. Tak więc tabele skrótów pozwalają na szybsze wyszukiwanie niż wyszukiwanie liniowe, jeśli wszystko zostało właśnie zapisane. Jedynym minusem jest to, że niektóre implementacje skrótu cierpią z powodu kolizji, co jest tym samym obliczonym skrótem dla dwóch różnych kluczy. Ogólnie rzecz biorąc, nie jest to coś, o co musisz się bardzo martwić.
Mam nadzieję, że stanowi to tło, ale jeśli chcesz się tym zainteresować, spróbuj przeczytać więcej na ten temat. Moje wyjaśnienie jest bardzo podstawowe i jestem pewien, że jest w nim wystarczająco dużo dziur, ale powinno wystarczyć do szybkiego wyjaśnienia.
źródło