Haszowanie
Hashing
Hash: siekać, szatkować, mieszać, rozpraszać, haszować galimatias, zamęt.
Słownik
Abstrakcyjny Typ Danych, oparty na matematycznym modelu zbioru i wyposażony
w operacje SEARCH (LOOKUP), INSERT, DELATE, nazywamy słownikiem (dictionary).
ADT reprezentuje zbiór S elementów dowolnej natury (np. słów), na którym
określone są następujące operacje :
SEARCH(v,S) - wyszukiwanie elementu v lub jego miejsca w zbiorze S.
INSERT(v,S) - wstawianie elementu v do zbioru S, (S=S*"{v}), jeśli v "S ,
DELATE(v,S)  usunięcie elementu v ze zbioru S, (S=S-{v}), jeśli v "S ,
ASD LJ S
1
Słownik
Wartości elementów zbioru S należy traktować jako wartości pewnego klucza,
względem którego jest organizowany słownik, same zaś elementy zwykle zawierają
znacznie więcej informacji.
Dodatkowo przyjmuje się, że dla wartości kluczy istnieje  relacja większości
pozwalająca na porównanie elementów względem klucza. Umożliwia to przyjęcie
takich struktur danych, w ktorych efektywnie wykonywane są operacje słownika na
podstawie tej relacji.
Operacja wyszukiwania SEARCH ma szczególne znaczenie dla zadania słownika.
Wynika ono z konieczności sprawdzenia istnienia elementu w zbiorze również w
operacjach wstawiania (INSERT) i usuwania (DELATE).
W wielu zastosowaniach operacja wyszukiwania jest wykonywana znacznie częściej
niż pozostałe operacje interfejsu.
ASD LJ S
Haszowanie
Haszowanie (hashing), rozpraszanie, mieszanie - strategia wyszukiwania elementów
w słowniku. Strukturę danych związaną z haszowaniem nazywamy tablicą
haszowaną (hash table) zw. też tablicą rozproszoną, pomieszaną, asocjacyjną.
Podstawową operacją w metodach wyszukiwania w dotychczasowych
implementacjach zarówno tablicowych jak i dowiązaniowych było porównywanie
kluczy a wynik porównania określał, czy element został znaleziony.
W wyszukiwaniach sekwencyjnych było to przeglądane kolejnych elementów, można
było użyć wartownika.
W wyszukiwaniu binarnym następne elementy do sprawdzenia były wyznaczane
poprzez sukcesywne połowienie, a to czy znaleziony został szukany element
zależało od wyniku porównania kluczy.
Podobnie było w drzewach BST i w drzewach AVL, w których decyzję o kierunku
dalszego wyszukiwania także podejmowało się na podstawie porównania kluczy.
ASD LJ S
2
Haszowanie
Zupełnie inne podejście do problemu wyszukiwania polega na wyliczeniu pozycji
klucza w tablicy na podstawie jego wartości.
Wartość klucza jest jedyną wskazowką co do polożenia elementu. Jeżeli znamy
klucz, to do odpowiedniego miejsca w tablicy możemy sięgnąć bezpośrednio, bez
żadnych wcześniejszych sprawdzeń, potrzebnych w wyszukiwaniu binarnym czy też
przy przeszukiwaniu drzewa.
Oznacza to, że czas wyszukiwania zmniejsza się z O(n) dla wyszukiwania
sekwencyjnego lub O(lg n) dla wyszukiwania binarnego do O(1), niezależnie od
liczby elementów w przeszukiwanej tablicy.
ASD LJ S
Haszowanie
Zadanie słownika może być rozwiązane przez przechowywanie elementów w tablicy.
Efektywne algorytmy można uzyskać, jeśli uda się zrealizować wyszukiwanie przez
wyznaczenie położenia elementu w tablicy na podstawie jego wartości.
Potrzebna jest funkcja, za pomocą ktorej można przeksztalcić dany klucz K, który
może być napisem, liczbą, rekordem itp. na indeks w tablicy przechowującej w tablicy
przechowującej elementy tego samego typu co klucz K.
Taką funkcję h nazywamy funkcją mieszającą (hash function). Jeśli h przekształca
rożne klucze w rożne liczby, to nazywamy ją doskonałą funkcją haszującą.
Najprostszym sposobem rozwiązania zadania słownika jest założenie, że wartości
elementów (kluczy) są z ograniczonego zbioru np. z zakresu [0, m-1]. Wówczas
wartości te być jednocześnie jego indeksem w haszowanej tablicy H[0..m-1].
ASD LJ S
3
Reprezentacje słownika
Implementacja ADT jako słownika zależy od:
Wielkości zbioru reprezentowanego przez ADT (przede wszystkim).
Zestawu operacji, które na tym zbiorze będą wykonywane.
Elementarne reprezentacje słowników:
1. Tablica lub lista nieposortowana.
2. Tablica lub lista posortowana.
3. Drzewa: BST, AVL, RB, RST, TRIE, Splay, B-drzewa.
4. Tablica haszowana.
ASD LJ S
Zadanie słownika
Sformułowanie problemu.
Dany jest zbiór rekordów słownika, z których każdy jest identyfikowany przez
unikatowy klucz z m-elementowej przestrzeni U={0, 1, .., m-1} oraz zbiór adresów
w pamięci H. Znalez
ć odwzorowanie h: UH takie, że nakład pracy związany z
odnalezieniem rekordu o danym kluczu jest minimalny.
Odwzorowanie h zwane jest funkcją mieszającą natomiast przestrzeń U uniwersum
(universe) kluczy.
Technika dostępu do tablic zwana organizacją rozproszoną (hashing) polega na
obliczeniu adresu rekordu w tablicy na podstawie jego klucza. Umożliwia to
(przynajmniej teoretycznie) odnalezienie szukanego rekordu w jednej próbie.
Mimo, że wyszukiwanie elementu w tablicy z haszowaniem może trwać w
najgorszym przypadku tyle, ile wyszukiwanie elementu na liście z dowiązaniami O(n)
to w praktyce haszowanie daje znakomite wyniki, oczekiwany czas wynosi O(1).
ASD LJ S
4
Adresowanie bezpośrednie
Adresowanie bezpośrednie jest prostą metodą wyszukiwania, która jest bardzo
skuteczna, jeśli uniwersum kluczy U jest rozsądnie małe.
Załóżmy słownik, ktory zawiera klucze należące do uniwersum U={0, 1, ..,m-1},
gdzie m nie jest zbyt duże. Przyjmujemy przy tym, że żadne dwa elementy nie mają
identycznych kluczy.
Przy powyższych założeniach słownik można reprezentować za pomocą tablicy z
adresowaniem bezpośrednim H[0 .. m-1], w której każdej pozycji odpowiada klucz
należący do uniwersum U.
ASD LJ S
Adresowanie bezpośrednie
Reprezentacja słownika za pomoca tablicy z adresowaniem bezpośrednim.
H
U={0, 1, & .., m-1}
null dodatkowe
0
U
K ą" U
klucz informacje
k0 k1
H[k]=null, dla k "K
k4 1 null
k2
k7 K k2 2
k3
k5
k3 3
k6 null
null
km-1
6 k6
null
m-2 . . . .
null
m-1
ASD LJ S
5
Implementacja operacji słownikowych
Złożoność operacji słownikowych (adresowanie bezpośrednie) wynosi O(1).
Search direct (H,k)
{
return H[k];
}
Insert direct (H,k)
{
return H[key[k]]=k;
}
Delete direct (H,k)
{
return H[key[k]]=null;
}
ASD LJ S
Adresowanie pośrednie
Jeśli uniwersum kluczy U jest duże to przechowywanie w pamięci tablicy H o
rozmiarze ćłUćłjest nierealne.
Ponadto, jeżeli używa się niewielkiego podzbioru kluczy, znaczna część tablicy H
pozostaje niewykorzystana, mimo że zajmuje pamięć.
Jest to rozwiązanie bardzo niekorzystne. Użyteczne będzie dopiero przy
zastosowaniu pewnej modyfikacji sposobu indeksowania zwanej metodą z
hazsowaniem. Adresowanie takie jest adresowaniem pośrednim.
Wyszukiwanie elementu na podstawie klucza wymaga wprowadzenia funkcji, która
na podstawie wartości elementu określi jego położenie (indeks) w tablicy.
ASD LJ S
6
Adresowanie pośrednie
Rozpraszanie zbioru kluczy na zbior adresów (ćłUćł>>ćłKćł).
Odwzorowanie h jest odwzorowaniem typu  wiele do wielu .
H
U
. . .
ASD LJ S
Adresowanie pośrednie
Funkcja haszującą h(x) odwzorowuje cały przedział możliwych wartości elementów
na mniej liczny zakres indeksów w tablicy.
W tablicy haszowanej element k ze zbioru K jest zapisywany na pozycję h(k)
wyznaczonej za pomocą funkcji haszującej h.
Funkcja haszująca odwzorowuje uniwersum U w zbiór indeksów tablicy H[0, 1, ...,
m-1], zwanej tablicą haszowaną.
H
h: U {0, 1, , m-1}
k"U
0
ćłUćł>m
1
h
k
k h(k)
0 d"h(k) d"m  1
m-1
ASD LJ S
7
Tablica haszowana
Wyznaczona przez funkcję h wartość jest indeksem w tablicy pod którym możemy
znalez
ć poszukiwany element.
H
0
U
1
h(k1)= h(k2)
k1
k2
ki
h(ki)
kj
h(kj)
. . .
m-1
ASD LJ S
Rozwiązywanie kolizji
Liczba możliwych wartości elementów słownika jest dużo większa od rozmiaru
tablicy, może się więc zdarzyć, że dla dwóch elementów o różnych kluczach funkcja
mieszająca będzie miała jednakowe wartości. Powstanie wówczas kolizja (co
najmniej dwa elementy powinny zajmować to samo miejsce w tablicy).
Metody usuwania kolizji:
A
ańcuchowa (chaining).
Haszowanie otwarte (open addressing).
ASD LJ S
8
Rozwiązywanie kolizji
Metoda łańcuchowa.
Metoda łańcuchowa polega na utrzymywaniu dla każdego indeksu i"[0..m-1] tablicy
haszowanej listy elementów, które maja tę samą wartość funkcji haszującej. Tablica
haszowana H zawiera wskaz
niki do tych list.
Każda komórka tablicy haszowanej zawiera wskaz
nik do listy jednokierunkowej, w
której przechowujemy wszystkie elementy zbioru wysłanego do tej komórki przez
funkcję haszującą. Aby odnalez
ć element k obliczamy wartość h(k), która wskazuje
numer komórki.
ASD LJ S
Metoda łańcuchowa
Rozwiązywanie kolizji metoda łańcuchową.
H
null
U
null
K k1
k1 k2 /
k2
k4
k3 k4 k6 /
k3
k5 k6
null
k7
null
k5 /
k7 /
. . . .
null
ASD LJ S
9
Metoda łańcuchowa
Współczynnik zapełnienia ą = n/m,
Pesymistyczny czas wyszukiwania wynosi więc O(n) + czas potrzebny na
obliczenie wartości funkcji haszującej,
Średnie zachowanie haszowania zależy od tego, na ile równomiernie (w
średnim przypadku) funkcja haszująca h rozmieszcza zbiór
przechowywanych kluczy na m pozycjach tablicy H.
ASD LJ S
Metoda łańcuchowa
Przykład.
Anyone lived in a pretty how town
h(Anyone) = 97+110+121+111+110+101= 650 mod 5 = 0
Sł
łowo Kod Indeks
ł
ł
anyone 650 0
lived 532 2
Komórka Komórka Komórka
in 215 0
a 97 2
pretty 680 0
how 334 4
town 456 1
ASD LJ S
10
Metoda łańcuchowa
Struktura danych dla tablicy haszowanej.
H
Słowo Kod Indeks
0
pretty /
anyone
in
anyone 650 0
town /
lived 532 2 1
Komórka Komórka Komórka
in 215 0
2 lived
a /
a 97 2
3
/
pretty 680 0
4 how /
how 334 4
town 456 1
ASD LJ S
Funkcje haszujące
Wybór funkcji haszującej.
Cechy funkcji haszującej:
A
atwo obliczalna,
Zapewniająca równomierne haszowanie, (każdy indeks [0, 1, ..., m-1]
winien być jednakowo prawdopodobny jako wartość funkcji haszującej).
Warunek równomiernego haszowania:
Łx:h(x)=k p(x) = 1/m dla k=0,1, ...m-1
p(x)  prawdopodobieństwo wyboru klucza o wartości x.
W przedziale 0 d" x < 1, przy założeniu, że zmienna losowa x mają rozkład
równomierny, funkcja haszująca postaci:
h(x) = �ł m x �ł
�ł �ł
�ł �ł
�ł �ł
spełnia warunek równomiernego haszowania.
ASD LJ S
11
Funkcje haszujące
Funkcja haszująca musi gwarantować, że zwracana przez nią wartość jest
poprawnym indeksem komórki tablicy haszowanej.
Haszowanie modularne:
h(x) = x mod m
W metodzie modularnej należy unikać pewnych wartości x będących potęgami
dwójki, gdyż jeśli m=2p, to wartością h(x) stają się najmniej znaczące bity liczby.
Podobnie należy unikać potęg 10 jeśli kluczami są liczby dziesiętne, ponieważ
wartość funkcji haszującej nie zależy wtedy od wszystkich cyfr dziesiętnych x.
Jeśli w tablicy haszowanej będzie około n=4500 elementów, to wybierając liczbę
pierwszą pomiędzy 210 a 211 tj. m=1699 uzyskamy współczynnik załadowania
ą = n/m = 4500/1699 H" 2,6 co oznacza, że w jednej liście możemy spodziewać się
średnio od dwóch do trzech elementów.
ASD LJ S
Funkcje haszujące
Inną możliwością haszowania jest mnożenie wartości klucza przez pewną stałą.
Obliczenia przeprowadza się w dwóch krokach.
Haszowanie przez mnnożenie :
1. Mnożymy klucz x przez � a następnie wyznaczamy część ułamkową x�.
2. Mnożymy otrzymaną wartość przez m i wyznaczamy funkcję podłogi.
h(x) = �ł m(x� mod 1) �ł
gdzie x� mod 1 oznacza ułamkową część x � tj. x � - �ł x��ł.
� (0<�<1) H" ("5  1)/2 H" 0,618
ASD LJ S
12
Haszowanie otwarte
W metodzie haszowania otwartego, konflikt rozstrzyga się, znajdując wolne
miejsce w tablicy, inne niż pierwotnie przypisano.
Funkcja haszująca:
h(x, i) = y
gdzie: x  klucz,
i  liczba dotychczasowych próbkowań,
y  uzyskana wartość haszowania.
Własność funkcji h: w miarę wzrostu wartości indeksu i (od 0 do m-1), przed
ponownym odwiedzeniem tej samej pozycji konieczne jest odwiedzenie wszystkich
innych pozycji.
ASD LJ S
Haszowanie otwarte
Funkcja haszująca z adresowaniem (próbkowaniem) liniowym:
h(x, i)=(h (x) +i) mod m, dla i=0, 1, 2, ..., m-1
h (x) - pomocnicza funkcja haszująca
h (x) =x mod m
Dla każdego klucza x, jego ciąg próbkowania zaczyna się od pozycji:
H[h (x)], H[h (x)+1],..., H[m-1],
następnie występują pozycje:
H[0], H[1], ..., H[h (x) -1].
Generowanych jest m rożnych ciągów kontrolnych.
Występuje tendencja do grupowania (primary clustering) zajętych pozycji.
ASD LJ S
13
Haszowanie otwarte
Adresowanie liniowe h(x, i) = (x mod 11 +i) mod 11.
X= 37, 83, 97, 14
0 10
78 14 37 83 97
x = 59, i=0, 1
59
78 14 37 59 83 97
x = 25, i=0, 1, 2, 3, 4
25
78 14 37 59 83 25 97
x = 72, i=0, 1, 2 72
78 14 37 59 83 25 72 97
ASD LJ S
Haszowanie otwarte
Adresowanie dwukrotne:
h(x, i)=(h1(x) +i h2(x)) mod m, dla i=0, 1, 2, ..., m-1
h1, h2 - pomocnicze funkcje haszujące.
Aby zapewnić, żeby wszystkie pozycje tablicy były odwiedzane zanim
którakolwiek pozycja zostanie powtórnie wybrana, trzeba spełnić jeden
z warunków:
1. m - potęga dwójki i h2 - zwraca tylko wartości nieparzyste,
2. m - liczba pierwsza i h2 - zwraca liczby mniejsze od m (np. m-1, m-2).
Przykładowe funkcje haszujące:
h1(x) = x mod m
h2(x) = 1 + (x mod m )
ASD LJ S
14
Adresowanie dwukrotne
h(x, i)=(x mod 11 +i (1+x mod 9)) mod 11.
x= 37, 83, 97, 14
0 10
78 14 37 83 97
x=59, i=0, 1
59
78 14 37 59 83 97 59
x=25, i=0, 1
25
25 78 14 37 59 83 25 97 59
x=72, i=0, 1, 2 72
78 14 37 59 83 72 97
ASD LJ S
15