Jest szybka (O(1)), rozsądnie zarządza pamięcią (O(N)), a do tego jest przebiegła i chytra ;-)
Tutaj krótki* opis dla niekomputerowych ludzi co to jest i po co ;-)
Zacznijmy od nazwy.
Nasza struktura znana jest pod nazwą HashMap lub HashTable, czyli mapy lub tablicy hashującej.
Jest ona implementacją abstrakcyjnej struktury zwanej tablicą asocjacyjną.
Teraz po ludzku ;-)
HashMap zwana również HashTable to tablica hashująca.
Oba słowa są ważne.
Najpierw co to jest tablica.
To bardzo prosta, najprostsza chyba struktura danych.
Czyli najprostszy sposób na przechowywanie danych w pamięci komputera.
Po prostu układamy dane jedna za drugą. Mamy "przegródki" które mają identyczne rozmiary i znając rozmiar przegródki i pozycję tego co nas interesuje możemy tam od razu pójść.
Komputerowi do dotarcia do jakiegoś miejsca w pamięci potrzebny jest tylko adres tego miejsca.
A tablica pozwala na proste policzenie tego adresu.
Do tego komputer potrzebuje praktycznie tyle samo czasu na dotarcie do dowolnego miejsca w pamięci.
Z tablicą wystarczy znać numer "przegródki" i rozmiar przegródek. Do tego jeszcze adres pierwszej przegródki i umiemy dotrzeć do każdego elementu tablicy.
Adres możemy policzyć tak:
adres = numer_przegródki * rozmiar_pojedynczej_przegródki + adres_pierwszej_przegródki
Znając adres od razu trafiamy w odpowiednie miejsc.
To "od razu tam trafiamy" oznacza, że mamy "stały czas dostępu", czyli O(1) ;-)
Nie ważne czy chcemy się dostać do czegoś w tablicy co jest na początku, końcu czy w środku, zawsze trwa to tyle samo.
Sęk w tym, że choć tablica jest wspaniała to nie do wszystkiego się da jej użyć.
Jak mamy policzyć sumę jakichś liczb, to tablica działa świetnie. Przechodzimy element po elemencie i sumujemy.
Gdy mamy skopiować pliki to możemy sobie ich nazwy trzymać w tablicy i przesuwać się o jedne po tym jak skopiujemy poprzedni.
Tablicą jest też piętro w hotelu gdzie każdy pokój ma kolejny numer i ktoś na recepcji może łatwo powiedzieć, że w pokoju 300 mieszka X, a w 301 nikt.
Tablice działają ogólnie świetnie gdy mamy listę rzeczy i interesuje nas tylko ich kolejność, albo gdy kolejny numer dokładnie opisuje o co nam chodzi.
To drugie to przypadek z hotelem, albo lista zwycięzców biegu.
<Dygresja>
Żeby było zabawnie niektóre języki programowania zaczynają numerowanie elementów w tablicy zawsze od 0, niektóre zawsze od 1, a są jeszcze takie gdzie można samemu wyznaczyć zakresy.
Ale głównie zaczynają się od 0 albo 1.
Była propozycja by pogodzić te języki i wprowadzić kompromisowe rozwiązywanie i startować od 0.5, ale jakoś nie przeszła ;-)
</Dygresja>
Jednak nie wszystko da się opisać przez liczbę w prosty sposób.
Jak mamy listę imion i telefonów i chcemy móc znaleźć telefon którejś osoby bazując na imieniu to tablica się zbytnio nie nadaje.
Moglibyśmy w jednym miejscu trzymać tablicę z imionami i używać indeksu z tej tablicy by znaleźć numer.
Ale to by było wolne, w najgorszym przypadku musielibyśmy przeszukać całą tablicę imion by poznać indeks numeru ostatniej osoby w tablicy.
Moglibyśmy co prawda posortować imiona i wtedy moglibyśmy znaleźć imię o wiele szybciej, bo potrzebowalibyśmy mniej więcej log2(ilość_imion) prób stosując bisekcję**.
Ale da się szybciej.
Bo w końcu imię to tylko zbiór liter, a litery w komputerze są niczym innym jak liczbą***...
I gdyby tak użyć tej liczby jako indeksu w tablicy? Moglibyśmy od razu dotrzeć do odpowiedniego numeru...
Problem w tym, że te liczby byłyby bardzo duże. Ala to 6384705, Przemek to 30229343036404304....
Nie ma tak dużych komputerów by móc zmieścić w nich tak dużą tablicę.
Ale pomysł sam w sobie nie jest zły. By zmienić to po czym szukamy, czyli klucz w liczbę.
Ale nadal te liczby są za duże...
A gdyby tak przyjąć, że niezależnie jak wielka liczba nam wyjdzie to dzielimy ją zawsze przez liczbę opisującą rozmiar tablicy jaką mamy i używać przegródki, która będzie wyrażona jako reszta z tego dzielenia?
Czyli co by się stało gdyby wziąć mniejszą tablicę, powiedzmy z 100 elementami, później wziąć zmienić imię na liczbę, podzielić tę liczbę przez 100 i użyć reszty z tego dzielenia jako numeru przegródki?
Ala, czyli 6384705 zmieniłaby się w numer przegródki 5, a Przemek 30229343036404304 w przegródkę 4...
Niby działa, mamy wspaniałą strukturę danych, która zmienia imiona w numerki i od razu pozwala nam dotrzeć do numerów :-)
Ale są problemy....
Np. numery Alicji i Ewy byłby oba w przegródce 25. Bo Alicja z 107109562281025 zmieniłaby się w 25, Ewa z 6387525 też zmieniłaby się w 25.
To dość logiczne, bo jednak chcemy zmienić większe liczby w mniejsze i siłą rzeczy co jakiś czas się zdarzą konflikty.
W takim przypadku mamy 2 rozwiązania.
Rozwiązanie 1 to sam sposób na rozwiązanie konfliktu.
Jest ich kilka, ja opiszę w miarę najprostszy, czyli metodę łańcuchową.
W momencie konfliktu zamiast zapisać w danym miejscu numer telefonu zapisujemy imię i numer telefonu, jeśli już tam jakieś imię i numer telefonu są to dopisujemy je za pierwszym.... Czyli w tablicy trzymamy drugą tablicę (tak naprawdę w tablicy wtedy trzymamy adresy do innych tablic...).
Czyli jak szukamy numery Ewy to idziemy do przegródki 25, a później idziemy przez tablicę numerów w tej przegródce aż znajdziemy Ewę.
Niby fajne, ale jak zbyt często się nam będą te konflikty zdarzały to cała nasza ciężka praca była niewiele warto bo nadal będzie wolno...
Moglibyśmy zwiększyć rozmiar tablicy której używamy, ale wtedy zużyjemy więcej pamięci...
Trzeba więc postarać się by ta liczba, którą produkujemy z imienia była bardziej "szalona" tak by istniała jak najmniejsza szansa konfliktu.
Bo jednak biorąc resztę z dzielenia z liczby bierzemy de facto tylko część jej "dołu".****
Tu pojawia się druga część nazwy naszej struktury, czyli tablicy haszującej. Funkcja haszująca ;-)
Po angielsku hash to między innymi siekanka ;-) Funkcja hashująca to funkcja która na wejściu dostaje coś, np. imię, a na wyjściu wypluwa siekankę. Wypluwa liczbę wyprodukowaną z tego co na wejściu, ale jak najbardziej posiekaną.
Fachowo to się nazywa, że funkcja hashująca powinna klucze ze swojej dziedziny równomiernie dystrybuować w swojej przeciwdziedzinie ;-) [i jak ktoś tego nie rozumie, to sorry w LO to było ;-)]
Dodatkowy wymóg jest taki by hash z tego samego wejścia był ZAWSZE taki sam.
Same funkcje hashujące są dość złożone i mają różne ciekawe właściwości. Używa się ich też WSZĘDZIE.
Bitcoin i cały blockchain bazują na funkcjach hashujących, sumy kontrolne też, sprawdzania poprawności plików, antywirusy i tak dalej.
Zwykle funkcja hashująca bierze bity tego czego liczymy hash i próbuje wprowadzić do nich w jakiś sposób coś co dobrze będzie udawało chaos.
W przypadku imienia może zmienić wszystkie literki w liczby, a następnie do pierwszej literki dodać drugą pomnożoną przez jakąś liczbę (najlepiej pierwszą), później pomnożyć to znów przez tą liczbę i dodać trzecią, pomnożyć i dodać czwartą i tak dalej... (tak to działa w Java'ie)
Mamy wtedy liczbę, która jest dość przypadkowa. Teraz dzieląc ją przez liczbę przegródek w naszej tablicy zmniejszamy szanse na konflikt. Nadal może się zdarzyć, ale rzadziej.
Tu oczywiście jest haczyk, ilość kombinacji silnie zależy od rozmiaru tablicy w której będziemy trzymali nasze dane.
Przy dobrych funkcjach hashujących okazuje się, że zwykle wystarczy niewielki "zapas" w tablicy by uniknąć nadmiaru konfliktów. 20-25% więcej miejsca w tablicy niż chcemy w niej przechowywać elementów zwykle zapewnia praktycznie zerową liczbę konfliktów.
I to są mniej więcej tablice hashujące ;-)
Czyli tablica + hash. Bierzemy nasz klucz, robimy na nim hash i tak znajdujemy miejsce gdzie schować wartość, albo gdzie jest nasza wartość...
OK, tu jest jeszcze jedna rzecz. Bo w przecież mamy konflikty. Konflikt wtedy gdy mamy więcej niż 1 rzecz w danym kawałku naszej tablicy, albo gdy mamy 1 rzecz, ale szukamy innej która akurat też wskazuje na ten sam kawałek tablicy...
Potrzebujemy jeszcze czegoś co sprawdzi czy to po co sięgamy do naszej tablicy hashującej jest tym czego szukamy.
Czyli potrzebujemy czegoś co stwierdzi równość ;-)
Tu wychodzi ciekawa sprawa, czyli to, że tablica hashująca do działania potrzebuje "kontraktu".
Kontrakt mówi, że jeśli 2 rzeczy są równe to ich hashe muszą być takie same.
Dodatkowo, choć o tym się już tak głośno nie mówi ;-) hash powinno się liczyć tylko z tych elementów klucza, które są niezmienne.
... miało być krótko ;-)
* - miał być krótki...
** - i moglibyśmy użyć tablicy, albo drzewa ;-)
*** - liczby w komputerze zapisane są w kolejnych bajtach, 1 w jednym bajcie, 257 już w 2, 2 miliony potrzebują już 3 bajtów.. literki też są liczbami, można więc Ala, czyli liczby 65, 108 i 97 potraktować jako kawałki większej liczby.... akurat tutaj tą liczbą by było 65+108*256+97*2562 czyli 6384705.
**** - OK, to jest trochę trudniejsze i nie umiem tego dobrze wytłumaczyć. Załóżmy, że nie mamy 100 elementów w naszej tablicy, a dokładnie 256 sztuk. Czyli liczbę która nam wyjdzie z przeliczenia imienia dzielimy przez 256 i bierzemy resztę.
Wtedy Ala to 6384705, a reszta z dzielenia przez 256 to 65. Anna to 1634627137, ale reszta z dzielenia przez 256 to też 65.
W końcu nasza liczba to litera[0]+litera[1]*256+...+litera[długość_imienia-1]*256długość_imienia-1, a to podzielone z resztą daje resztę równą litera[0].... czyli nasz indeks jest w takim przypadku równy zawsze pierwszej literze... Szanse na konflikt mamy dość duże, szczególnie że mamy tylko 26 liter w alfabecie ;-)
Dzieląc przez 100 trochę się przed tym zabezpieczamy, ale nadal mało, bo nadal ignorujemy dużą część informacji zapisanej w imieniu.
Podobne postybeta
Jak czytać kod...
Moc wykresu.... Czyli jak wieść szczęśliwsze życie ;-)
Referencje w Java'ie
Wybory i ordynacje
Lubię bity, czyli jak dodawać, odejmować, mnożyć i dzielić na bitach ;-)
Brak komentarzy:
Prześlij komentarz