Strona główna » Algorytmy » Artykuły » Hashowanie
 

Hashowanie

https://mattomatti.com/a0202

Cel

Hashowanie pozwala na bardzo szybki dostęp do wybranej części danych. Kluczem jest jednak dobór odpowiedniej funkcji hashującej dane. Od tego może zależeć zrównoważenie czasu dostępu i zajętości pamięci. W tym artykule zostanie wyjaśnione jak w prosty sposób można zaimplementować hashowanie.

Przyczyna

Dla użytkownika liczy się szybkość. Z tego powodu algorytmy, które zostały zaimplementowane w programie muszą działać bardzo szybko. Dla małej ilości danych nie zawsze widać różnicę, ale dla coraz większych danych optymalny algorytm bardzo łatwo wskazać. Przypuśćmy, że chcemy zaimplementować książkę telefoniczną w której będzie bardzo dużo numerów telefonów. Możnaby w niej wyszukiwać dane element po elemencie, ale nie będzie to zbyt efektywne. Innym pomysłem jest wykorzystanie drzewa BST. Gwarantuje to wykonywanie operacji w czasie logarytmicznym, ale drzewo nie jest zbyt prostą strukturą do zaimplementowania. Z pomocą przychodzi tutah hashowanie.

Tablica Hashy

Hashowanie polega na przypisaniu elementu jakieś krótkiej wartości - zazwyczaj jest to jakaś liczba. Następnie w tablicy zebrane są wszystkie takie wartości. Pod odpowiednim pole znajduje się lista wszystkich elementów listy, które mają taki sam hash. Kiedy dwa elementy mają ten sam hash to mówimy, że doszło do kolizji. Innymi słowy hashowanie polega na podzieleniu większej bazy danych na mniejsze jej fragmenty w taki sposób, aby można się było do nich szybko dostać. Przygotowana tak tablica jest to tablica Hashy.

Funkcja Hashująca

Istnieje wiele różnych funkcji, które pozwalają na hashowanie obiektów, a w zależności od ich struktury inna funkcja może okazać się skuteczniejsza. Należy pamiętać, że tego typu funkcja powinna wykonywać jak najmniej operacji w celu wyliczenia hashu oraz jak najrówniej rozkładać elementy. Przykładem funkcji hashującej jest modulo, które rozkłada równo elementy, ale może się nie sprawdzić, gdy wszystkie liczby mają tą samą końcówkę.

Implementacja

W celu dokładniejszego zrozumienia funkcji hashującej poniżej zostanie przedstawiony sposób hashowania tablicy telefonów. Wiele języków implementuje gotowe struktury danych do hashowania danych. W tym przykładzie hashowanie zostanie oparte o zwykłą tablicę list. Przypuśćmy, że numery telefonów są najwyżej 4 cyfrowe.

Hashowanie

Najbardziej elastyczną funkcją do hashowania będzie tutaj funkcja modulo, a więc algorytm obliczania jest bardzo prosty:

C++C#
Python
  1. def hashtel(telefon):
  2.   global N
  3.   return telefon % N

Kolejna funkcja wyszukaj() zwraca funkcję logiczną czy dana wartość występuje. W tym celu należy przekazać do funkcji zawiera obiekt klasy telefonicznej oraz szukany numer telefonu.

C++C#
Python
  1. def wyszukaj(ksiazka, telefon):
  2.   lista = ksiazka[hashtel(telefon)]
  3.   return telefon in lista

Przed wyszukiwaniem obliczamy hash telefonu, aby pobrać odpowiednią listę telefonów, które mają ten sam hash. Wśród nich powinien być szukany numer telefonu o ile się tam znajduje.

Podobnie działa funkcja dodaj(), która po upewnieniu się, że dany telefon w książce nie występuje dodaje go do odpowiedniej tablicy.

C++C#
Python
  1. def dodaj(ksiazka, telefon):
  2.   if not wyszukaj(ksiazka, telefon):
  3.     ksiazka[hashtel(telefon)].append(telefon)
  4.   return ksiazka

Testowanie funkcji

Poniższy kod testuje działanie funkcji hashującej poprzez dodanie czterech numerów telefonów, a następnie wyświetleniu ich rozmieszczenia:

C++C#
Python
  1. ksiazka = [[] for i in range(N)]
  3. ksiazka = dodaj(ksiazka, 123)
  4. ksiazka = dodaj(ksiazka, 673)
  5. ksiazka = dodaj(ksiazka, 456)
  6. ksiazka = dodaj(ksiazka, 987)
  8. for i in range(N):
  9.   print("[" + str(i) + "]\t", end ='')
  10.   for el in ksiazka[i]:
  11.     print(el, end =' ')
  12.   print()
  1. [0]
  2. [1]
  3. [2]
  4. [3]   123, 673
  5. [4]
  6. [5]
  7. [6]   456
  8. [7]   987
  9. [8]
  10. [9]

Na powyższym wyniku widać, że tablica hashy jest tworzona poprawnie, więc można przejść do przetestowania wyszukiwania poszczególnych numerów. Oto przykładowy tekst:

C++C#
Python
  1. szukaj = [333, 901, 456]
  2. for el in szukaj:
  3.   wynik = wyszukaj(ksiazka, el)
  4.   print(str(el) + "\t" + ("jest" if wynik else "nie ma"));
  1. 333   nie ma
  2. 901   nie ma
  3. 456   jest

Dane są wyszukiwane poprawnie. To jest najprostszy przykład hashowania danych. Jak można zauważyć nawet jeśli dana lista będzie przeszukiwana element po elemencie to wyszukiwanie będzie szybsze niż wyszukiwanie w całej liście. W niektórych przypadkach wynik można otrzymać od razu, ponieważ lista ma jeden element, albo żadnego.

Złożoność

Zastosowana funkcja hashująca po wpisaniu wszystkich możliwych telefonów do struktury będzie przyśpieszała wyszukiwanie aż dziesięciokrotnie, ponieważ po wyliczeniu hasha lista do przeszukiwania to zaledwie 1/10 pełnej listy. Oczywiście tablicę można podzielić na 10 elementowe listy, aby uzyskać jeszcze większę wydajność, ale wtedy zwiększa się zużycie pamięci. Porównanie różnych funkcji hashujących zostanie przedstawione w kolejnych artykułach.

Zadania

Zadanie 1

Napisz funkcję, która będzie hashować numery telefonów po dwóch ostatnich cyfrach. Wartość hasha nie będzie przechowywana wewnątrz struktury hashującej. Oznacza to, że telefon "1234" ma hash "34", a w tablicy pod indeksem 33 ma być przechowywane jedynie "12". Przetestuj działanie napisanego programu.