Ostatnio szukałem dobrego wyjaśnienia, jak działa hashtable – i znalazłem! Naprawdę fajną historyjkę…
Opowieść o bibliotekarzu
Załóżmy, że chcesz zapełnić bibliotekę książkami. Nie chcesz jednak zwyczajnie upychać książek po półkach – chcesz zrobić to tak, by później móc szybko znaleźć konkretny tytuł, gdy zajdzie taka potrzeba.
Stwierdzasz więc, że jeśli czytelnik będzie znał dokładny tytuł książki, to z pomocą bibliotekarza będzie w stanie łatwo i szybko odnaleść książkę w bibliotece.
Ale jak to zrobić? Oczywiście, mógłbyś trzymać listę wszystkich książek i półek, na których je poukładałeś. Na pewno przeszukiwanie listy byłoby szybsze i wygodniejsze, niż przeszukiwanie całej biblioteki… jednak nie chce Ci się za każdym razem przeglądać listy w poszukiwaniu konkretnego tytułu.
Potrzebujesz czegoś lepszego, czegoś, co potrafiłoby wziąść tytuł książki i na jego podstawie podać dokładne miejsce, w którym ta książka się znajduje. Wtedy musiałbyś jedynie podejść do półki i zabrać książkę!
Tylko jak to zrealizować? Trzeba będzie przemyśleć, w jaki sposób rozmieścić książki na półkach…
Zamiast zapełniać bibliotekę od jednego końca do drugiego, wymyślasz pewną sprytną metodę. Bierzesz tytuł książki, przepuszczasz go przez specjalny programik komputerowy, który wypluwa numer półki i przegródki. Tam kładziesz książkę.
Piękno tego programiku polega na tym, że kiedy ktoś przyjdzie wypożyczyć książkę, a Ty przepuścisz tytuł książki przez program, dostaniesz dokładnie ten sam numer półki i przegródki, co poprzednio. Tam właśnie leży książka!
Ten sprytny programik to tak zwany algorytm hashujący. Bierze on porcję danych, i wylicza z nich pewną unikalną liczbę.
Dla uproszczenia powiedzmy, że po prostu bierze każdą literę tytułu książki, przerabia ją na liczbę, a następnie sumuje wszystkie te liczby. W rzeczywistości jest to dużo bardziej skomplikowane, ale zostawmy to na razie.
Najlepsze w tym algorytmie jest to, że za każdym razem, kiedy podasz mu te same dane wejściowe, on zwróci tę samą liczbę (czyli numer półki) !
To tyle na temat koncepcji. Teraz trochę techniki.
Po pierwsze, rozmiar naszej unikalnej liczby. Zwykle należy ona do bardzo dużego zakresu. Dużo większego, niż rozmiar naszej tablicy. Powiedzmy, że w naszej bibliotece mamy miejsce na milion książek. Nasz algorytm zwraca liczby z zakresu od zera do miliarda. O wiele za duże.
Co więc robimy? Wykonujemy dzielenie modulo! Dzieląc liczbę modulo górny limit naszego zakresu, mamy pewność, że pozostaniemy zawsze wewnątrze tego zakresu. Załóżmy, że mamy mały zakres 0..15, a my dostaliśmy liczbę 22. Dzielimy więc 22 modulo 15, co daje 1 i reszty 7. Kładziemy więc książkę na półce nr 7.
To prowadzi do kolejnego problemu. Kolizje. Ponieważ algorytm nie ma możliwości takiego wyliczania liczb, aby dokładnie zapełnić bibliotekę, w końcu dojdzie do tego, że wyliczy nr półki, która już jest zajęta przez inną książkę…
Istnieją różne sposoby rozwiązywania kolizji, takie jak wykonywanie dodatkowych obliczeń by znaleść inne miejsce w tablicy, lub po prostu znajdowanie wolnego miejsca w pobliżu wyliczonego (np. zaraz obok poprzedniej książki). Będziesz przez to musiał trochę rozejrzeć się po okolicznych przegródkach, jednak jest to znacznie lepsze niż przeszukiwanie całej biblioteki od początku do końca!
W końcu przyjdzie czas, że będziesz chciał umieścić w bibliotece więcej książek, niż może ona pomieści. Będziesz więc potrzebował nowej biblioteki. Ponieważ położenie książek było liczone na podstawie rozmiaru starej biblioteki – będziesz musiał od nowa rozmieścić wszystkie książki w bibliotece, bo sposób obliczeń się zmienił.
Thanks to Lasse V. Karlsen:
http://stackoverflow.com/questions/730620/how-does-a-hash-table-work
