1

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

2

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.

ASD

LJ

S

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.

Haszowanie

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.

ASD

LJ

S

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.

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ą.

3

Haszowanie

ASD

LJ

S

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.

Haszowanie

ASD

LJ

S

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].

4

Reprezentacje słownika

ASD

LJ

S

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.

Zadanie słownika

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.

ASD

LJ

S

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).

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, I.., m-1} oraz zbiór adresów
w pamięci H. Znaleźć odwzorowanie h: U

→H 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.

5

Adresowanie bezpośrednie

Załóżmy słownik, ktory zawiera klucze należące do uniwersum U={0, 1, I..,m-1},
gdzie m nie jest zbyt duże. Przyjmujemy przy tym, że żadne dwa elementy nie mają
identycznych kluczy.

ASD

LJ

S

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.

Adresowanie bezpośrednie jest prostą metodą wyszukiwania, która jest bardzo
skuteczna, jeśli uniwersum kluczy U jest rozsądnie małe.

Adresowanie bezpośrednie

ASD

LJ

S

Reprezentacja słownika za pomoca tablicy z adresowaniem bezpośrednim.

3

6

2

U={0, 1, ….., m-1}
K

⊆ U

H[k]=null, dla k

∉K

k

2

K

null

null

H

null

null

null

. . . .

null

m-1

U

k

4

k

0

k

1

k

7

k

2

k

3

k

6

k

m-1

k

3

k

6

1

0

k

5

klucz

dodatkowe
informacje

m-2

6

Implementacja operacji słownikowych

ASD

LJ

S

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;

}

Adresowanie pośrednie

ASD

LJ

S

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.

7

Adresowanie pośrednie

ASD

LJ

S

Rozpraszanie zbioru kluczy na zbior adresów (

U>>K).

Odwzorowanie h jest odwzorowaniem typu „wiele do wielu”.

U

H

. . .

Adresowanie pośrednie

ASD

LJ

S

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: U

→ {0, 1, I, m-1}

k

∈U

U>m

0

1

m-1

h

h(k)

k

k

H

0 ≤ h(k) ≤ m – 1

8

Tablica haszowana

ASD

LJ

S

Wyznaczona przez funkcję h wartość jest indeksem w tablicy pod którym możemy
znaleźć poszukiwany element.

h(k

1

)= h(k

2

)

k

j

k

i

k

1

k

2

U

H

. . .

0

1

h(k

i

)

h(k

j

)

m-1

Rozwiązywanie kolizji

ASD

LJ

S

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ńcuchowa (

chaining

).

Haszowanie otwarte (

open addressing

).

9

Rozwiązywanie kolizji

ASD

LJ

S

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 wskaźniki do tych list.

Każda komórka tablicy haszowanej zawiera wskaźnik do listy jednokierunkowej, w
której przechowujemy wszystkie elementy zbioru wysłanego do tej komórki przez
funkcję haszującą. Aby odnaleźć element k obliczamy wartość h(k), która wskazuje
numer komórki.

Metoda łańcuchowa

ASD

LJ

S

Rozwiązywanie kolizji metoda łańcuchową.

k

1

K

null

null

H

null

null

. . . .

null

U

k

2

k

3

k

6

k

3

k

5

/

k

1

k

5

k

4

k

7

k

2

/

k

4

k

6

/

k

7

/

10

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

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

Przykład.

11

Metoda łańcuchowa

Struktura danych dla tablicy haszowanej.

H

0

1

2

3

4

anyone

in

pretty

/

town

/

lived

a

/

how

/

/

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

Funkcje haszujące

Wybór funkcji haszującej.

Cechy funkcji haszującej:

Ł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

W przedziale 0

≤ 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.

p(x) – prawdopodobieństwo wyboru klucza o wartości x.

ASD

LJ

S

12

Funkcje haszujące



Haszowanie modularne:

h(x) = x mod m

ASD

LJ

S

Funkcja haszująca musi gwarantować, że zwracana przez nią wartość jest
poprawnym indeksem komórki tablicy haszowanej.

W metodzie modularnej należy unikać pewnych wartości x będących potęgami
dwójki, gdyż jeśli m=2

p

, 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 2

10

a 2

11

tj. m=1699 uzyskamy współczynnik załadowania

α = n/m = 4500/1699 ≈ 2,6 co oznacza, że w jednej liście możemy spodziewać się
średnio od dwóch do trzech elementów.

Funkcje haszujące

ASD

LJ

S

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) ≈ (√5 – 1)/2 ≈ 0,618

13

Haszowanie otwarte

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

W metodzie haszowania otwartego, konflikt rozstrzyga się, znajdując wolne
miejsce w tablicy, inne niż pierwotnie przypisano.

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

14

Haszowanie otwarte

78

14

37

59

83

25

97

25

x = 25, i=0, 1, 2, 3, 4

78

14

37

59

83

97

59

x = 59, i=0, 1

78

14

37

59

83

25

72

97

72

x = 72, i=0, 1, 2

78

14

37

83

97

0

10

X= 37, 83, 97, 14

Adresowanie liniowe h(x, i) = (x mod 11 +i) mod 11.

ASD

LJ

S

Haszowanie otwarte

Adresowanie dwukrotne:

h(x, i)=(h

1

(x) +i h

2

(x)) mod m, dla i=0, 1, 2, ..., m-1

h

1

, h

2

- 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 h

2

- zwraca tylko wartości nieparzyste,

2. m’ - liczba pierwsza i h

2

- zwraca liczby mniejsze od m (np. m-1, m-2).

Przykładowe funkcje haszujące:

h

1

(x) = x mod m

h

2

(x) = 1 + (x mod m’)

ASD

LJ

S

15

Adresowanie dwukrotne

78

14

37

59

83

72

97

72

x=72, i=0, 1, 2

78

14

37

83

97

0

10

x= 37, 83, 97, 14

78

14

37

59

83

97

59

59

x=59, i=0, 1

25

78

14

37

59

83

25

97

59

25

x=25, i=0, 1

h(x, i)=(x mod 11 +i (1+x mod 9)) mod 11.

ASD

LJ

S