Różnice między wybraną wersją a wersją aktualną.
| Nowa wersja | Poprzednia wersja | ||
|
pl:dydaktyka:asd:cwiczenia:2011-hashing [2011/04/21 08:31] kkr utworzono |
pl:dydaktyka:asd:cwiczenia:2011-hashing [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Tablice haszujące ====== | ====== Tablice haszujące ====== | ||
| - | ===== Trochę oznaczeń ===== | + | Termin zajęć: 10/11 maj 2011 |
| - | * **U** - Uniwersum kluczy. Zbiór wszystkich możliwych kluczy //U = {0,1,...,m-1}//. | + | |
| - | * **K** - Zbiór kluczy elementów aktualnie znajdujących się w zbiorze. | + | |
| - | * **T** - Zbiór będący tablicą haszującą. | + | |
| - | * **h(k)** - funkcja haszująca oblicza pozycję w tablicy T elementu o kluczu //k//. | + | |
| - | * **floor(a)** - funkcja zwracająca część całkowitą liczby //a//. | + | |
| - | ===== Rodzaje haszowania ===== | + | **Do przygotowania teoria na temat:** |
| - | * **haszowanie bezpośrednie** | + | - Rodzaje haszowania |
| - | * **haszowanie modularne** | + | * haszowanie bezpośrednie |
| - | * **haszowanie przez mnożenie** | + | * haszowanie modularne |
| - | * **haszowanie uniwersalne** | + | * haszowanie przez mnożenie |
| - | * **haszowanie doskonałe** | + | * haszowanie uniwersalne |
| + | - Problem konfliktów podczas haszowania | ||
| + | - Sposoby rozwiązywania konfliktów | ||
| + | * Metoda łańcuchowa | ||
| + | * Metoda adresowania otwartego | ||
| - | Haszowanie jest wykonywane przy pomocy funkcji haszującej. | + | ===== Przykładowe zadania ===== |
| - | Dobra funkcja haszująca powinna spełniać założenia prostego równomiernego haszownia: losowo wybrany klucz jest z jednakowym prawdopodobieństwem odwzorowywany na każdą z //m// pozycji niezależenie od tego, gdzie zostają odwzrowane inne klucze. \\ | + | Poniżej mają Państwo przykładowe zadania z haszowania. W razie znalezienia błędów, prosimy o informację. |
| - | Niestety rzadko jest znany rozkład prawdopodobieństwa pojawiania się kluczy. Dla przykładu niech kluczę będą losowymi liczbami rzeczywistymi rozłożonymi równomiernie i niezależnie w przedziale //0 <= k < 1//. W tym przypadku można pokazać że funkcja haszująca: //h(k) = floor(km)// spełnia warunki dobrej funkcji haszującej. | + | |
| - | ==== Haszownie bezpośrednie ==== | + | **Zadanie 1** \\ |
| - | Jest to takie haszowanie w którym element o kluczu //k// znajduje się na pozycji //k-tej//: //h(k) = k//. Głównym założeniem tej metody haszowania jest to że żadne dwie różne wartości nie mają tego samego klucza. Główną wadą tego haszowanie jest to że jeżeli |U| jest zbyt duże to przechowywanie całej tablicy w pamięci komputera może być nie realne. Co więcej jeżeli |K| będzie zbyt małe w porównaniu z |U| to większość pamięci zarezerwowanej dla T może się niepotrzebnie marnować. | + | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = x*4''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''5, 3, 7, 10, 2''. \\ |
| - | ==== Haszowanie modularne ==== | + | **Rozwiązanie** \\ |
| - | Funkcja haszująca stosowana w haszowaniu modularnym na kluczu //k// daje wartość będącą resztą z dzielenia //k// przez //m//, gdzie //m// jest liczbą pozycji w tablicy:<code>h(k) = k modulo m</code> | + | * ''h(k,i) = (h'(k)+i)%m'' |
| - | W tej metodzie ważne jest aby dobrać odpowiednio wartość //m//. Tzn. należy unikać wartości //m// będących potęgą 2, ponieważ jeżeli //m = 2<sup>p</sup>// to //h(k)// jest liczbą stanowiącą //p// najmniej znaczących bitów liczy //k//. Należy używać funkcji zależącej od wszystkich bitów wartości //k//. Dobrymi wartościami //m// są liczby pierwsze niezbyt bliskie potęgom 2. \\ Dla przykładu: jeżeli w tablicy zamierzamy przechowywać około 2000 wartości przy czym dopuszczamy średnią długość listy równą 3 wtedy należy stworzyć tablicę //T// o wielkości 701 ponieważ 701 jest liczbą pierwszą leżącą blisko wartości 2000/3 oraz daleko od potęg 2. Wtedy //h(k) = k modulo 701// | + | * ''h'(k) = k%m'' |
| + | * ''TAB = 7, 10, 2, NIL, NIL, 3, 5'' | ||
| - | ==== Haszowanie przez mnożenie ==== | + | **Zadanie 2** \\ |
| - | Haszowanie przez mnożenie przebiega w dwóch krokach: | + | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą liniowego adresowania otwartego. Zakładamy że tablica ma rozmiar ''m=7'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 3x+1''. Napisz wzór pomocniczej funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2, 5, 9, 1, 3''. \\ |
| - | * Mnożymy wartość przez stałą //A// taką że 0 < A < 1 i wyznaczamy część ułamkową iloczynu //kA//. | + | **Rozwiązanie** \\ |
| - | * Otrzymaną wartość mnożymy przez //m//. | + | * ''h(k,i) = (h'(k)+i)%m'' |
| - | Postać funkcji haszującej można zapisać w następujący sposób: //h(k) = floor(m(kA modulo 1))// \\ | + | * ''h'(k) = k%m'' |
| - | gdzie "kA modulo 1" oznacza część ułamkową tj. //kA - floor(kA)// | + | * ''TAB = 2, 9, 5, 3, 1, NIL, NIL'' |
| - | ==== Haszowanie uniwersalne ==== | + | **Zadanie 3** \\ |
| - | Haszowanie uniwersalne rozwiązuje problem "złośliwych" danych, tzn. takich, które przy stałej funkcji haszującej są odwzorowywane na tę samą pozycję w tablicy. | + | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą kwadratowego adresowania otwartego ''h(k,i) = (h'(k) + i² + i)%m''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Pomocnicza funkcja haszująca jest funkcją haszowania modularnego, natomiast funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x) = 2x+1''. Przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''2.5, 2, 9, 5, 1''. \\ |
| - | Funkcja haszująca w metodzie uniwersalnej jest dobierana losowo z rodziny funkcji, o szczególnych właściwościach. | + | **Rozwiązanie** \\ |
| - | Wszystkie funkcje z rodziny funkcji haszujących są **niezależne** od wstawianych do tablicy kluczy. \\ | + | * ''h'(k) = k%m'' |
| - | Niech //H// będzie rodziną funkcji haszujących które odwzorowywują uniwersum kluczy //U// w zbiór //{0,1,...,m-1}//. | + | * ''TAB = NIL, 5, NIL, 9, NIL, 2, 2.5, 1'' |
| - | === Konstruowanie uniwersalnej klasy funkcji haszujących === | + | **Zadanie 4** \\ |
| - | Jest to prosta procedura: | + | Dane jest uniwersum możliwych kluczy: ''U = {2,3,4,5,6,7,8}''. Zaproponuj funkcję ''k(x)'' wyliczającą klucz na podstawie wartości elementu, której przeciwdziedziną jest zbiór ''Y=U''. Następnie wyznacz uniwersalną klasę funkcji haszujących. Dla wybranej funkcji należącej do wyznaczonej rodziny oblicz jej wartości dla każdego klucza należącego do uniwersum. Zakładamy że wartościami elementów mogą być tylko liczby naturalne oraz że rozmiar tablicy haszującej wynosi ''m=8''.\\ |
| - | * Wybieramy dużą liczbę pierwszą //p// tak aby **każdy** klucz //k// wpadał do przedziału //[0...p-1]//. | + | **Przykładowe rozwiązanie** |
| - | * //**Z<sub>p</sub>**// jest zbiorem //{0,1,...,p-1}//. | + | * ''k(x) = (x%7)+2'' |
| - | * //**Z*<sub>p</sub>**// jest zbiorem //{1,...,p-1}//. | + | * ''p = 11'' |
| - | * Wiemy że //p > m// - z założenia że uniwersum kluczy jest większe od liczby miejsc w tablicy. | + | * ''Zp = {0,1,...,10}'' |
| - | * //a ∈ **Z*<sub>p</sub>**// oraz //b ∈ **Z<sub>p</sub>**//. | + | * ''Z*p = {1,2,...,10}'' |
| - | Mając wszystkie parametry możemy wyznaczyć rodzinę funkcji:\\ | + | * Wybieramy np. ''a=3'', ''b=1''. |
| - | //H<sub>p,m</sub> = {h<sub>a,b</sub>: a ∈ **Z*<sub>p</sub>** i b ∈ **Z<sub>p</sub>**}// \\ gdzie: \\ | + | * ''h(k)=[(3*k+1)%11]%8'' |
| - | //h<sub>a,b</sub>(k) = ( (ak + b) modulo p) modulo m// \\ \\ | + | |
| - | Dla przykładu dla //p//=17 i //m//=6 mamy //h<sub>3,4</sub>(8) = 5// | + | |
| - | ==== Haszowanie doskonałe ==== | + | **Zadanie 5** \\ |
| - | // Nie rozwodziłbym się nad tym typem haszowania, a tylko wspomniał, opisał co to jest. Lub jeżeli ktoś prowadzi taką politykę tylko odpytał na czym ono polega. // | + | Tablica ''TAB'' jest tablicą haszującą o rozmiarze ''m=12'' w której konflikty są rozwiązywane metodą łańcuchową. Funkcja haszująca jest modularną funkcją haszującą. Zakładając że indeksowanie tablicy rozpoczyna się od ''1'' oraz że funkcja obliczająca klucz ma postać ''k(x)=2x+4'' podaj przynajmniej ''5'' różnych wartości elementów, które mogą być zapisane w tablicy pod indeksem ''7''. \\ |
| - | O haszowaniu mówimy że jest doskonałe jeżeli w przypadku pesymistycznym wyszukiwanie wymaga stałej liczby odwołań do tablicy. | + | **Rozwiązanie** \\ |
| - | Chociaż haszowanie znajduje szerokie zastosowanie ze względu na swoje znakomite zachowanie już w przypadku średnim, to okazuje się że również w przypadku pesymistycznym można osiągnąć podobną jakość. | + | * ''h(k) = (k%12)+1'' |
| - | Zbiór kluczy jest **zbiorem statycznym** tzn. po umieszczeniu kluczy w tablicy, jej zawartość nigdy nie ulega zmianie. | + | * ''(k%12)+1 = 7'' |
| - | Takie przypadki czasami pojawiają się naturalnie np. w przypadku zbioru nazw plików na CD-ROM-ie.\\ | + | * ''k%12 = 6 ⇒ k = 12i+6'', gdzie ''i={0,1,...}'' |
| - | Podstawowy pomysł haszowania doskonałego polega na wprowadzeniu dwupoziomowego haszownia: \\ \\ | + | * ''12i+6 = 2x+4'' |
| + | * ''12i+2 = 2x'' | ||
| + | * ''6i+1 = x'', gdzie ''i={0,1,...}'' | ||
| + | * Co nam generuje ciąg wartości których docelowy indeks to ''7''. | ||
| - | Pierwszy poziom to zwykłe haszowanie uniwersalne z łańcuchową metodą rozwiązywania konfliktów. | + | **Zadanie 6** \\ |
| - | //n// kluczy rozmieszczamy w //m// miejscach za pomocą funkcji haszującej. Zamiast jednak tworzenia listy kluczy odwzorowywanych na pozycję //j// tworzymy dodatkową tablicę z haszowaniem //S<sub>j</sub>// wraz ze związaną z nią funkcją haszującą //h<sub>j</sub>//. | + | Tablica ''TAB'' jest tablicą haszującą w której konflikty są rozwiązywane za pomocą metody łańcuchowej. Haszowanie jest wykonywane przez mnożenie dla ''A=0.4''. Zakładamy że tablica ma rozmiar ''m=8'' i jest początkowo pusta. Funkcja obliczająca klucz na podstawie wartości elementu jest dana wzorem: ''k(x)=x+8''. Napisz wzór funkcji haszującej oraz przedstaw stan tablicy ''TAB'' po każdym wstawieniu wartości w następującej kolejności: ''3, 1, 7, 11, 4''. \\ |
| - | **Można tak dobrać funkcję //h<sub>j</sub>// aby zagwarantować że na drugim poziomie nie będzie kolizji!**. | + | **Rozwiązanie** \\ |
| - | Aby zagwarantować brak kolizji na drugim poziomie musimy pozwolić aby rozmiar //m<sub>j</sub>// tablicy //S<sub>j</sub>// był kwadratem liczby //n<sub>j</sub>// czyli kluczy odwzorowywanych na pozycję //j//. | + | * Po przetworzeniu powyższych wartości przez funkcję ''k(x)'', powstaje następujący zbiór kluczy \\ ''k = {11,9,15,19,12}'' |
| - | Wtedy można udowodnić że prawdopodobieństwo wystąpienia kolizji jest mniejsze od 1/2. | + | * ''h(k) = floor(8*(0.4k%1))'' |
| - | + | * ''TAB = [7], NIL, NIL, [3], [1, 11], NIL, [4], NIL'' | |
| - | ===== Problemy - konflikty ===== | + | |
| - | Konflikty pojawiają się w momencie kiedy dla dwóch różnych kluczy funkcja haszująca wyznacza tę samą pozycję. | + | |
| - | + | ||
| - | ==== Rozwiązywanie konfliktów ==== | + | |
| - | === Metoda łańcuchowa === | + | |
| - | W metodzie łańcuchowej wszystkie elementy którym odpowiada ta sama pozycja w tablicy, zostają umieszczone na jednej liście. | + | |
| - | Na pozycji //j// w tablicy jest pamiętany wskaźnik do początku listy tych wszystkich elementów, dla których funkcja //h// daje wartość //j//. | + | |
| - | Jeżeli w zbiorze nie ma takich elementów to pozycja //j// ma wartość NIL. \\ | + | |
| - | W przypadku pesymistycznym zakłada się że wszystkie klucze są odwzorowywane na tę samą pozycję w tablicy. W takim przypadku wyszukiwanie staje się bardzo nieefektywne gdyż jego złożoność wynosi //O(n)//. \\ | + | |
| - | Współczynnik zapełnienia //α// dla danej tablicy //T// o //m// pozycjach w której znajduje się //n// elementów określa się jako //n/m// czyli średnią liczbę elementów w łańcuchu. \\ | + | |
| - | Oczekiwany czas wyszukiwania zakończonego porażką wynosi //O(α)//. | + | |
| - | + | ||
| - | === Adresowanie otwarte === | + | |
| - | Adresowanie otwarte jest kolejną metodą rozwiązywania konfliktów. W tej metodzie wszystkie elementy są przechowywane wprost w tablicy (konsekwencją jest to że //α// nie może być większa od 1 - przepełnienie tablicy). \\ | + | |
| - | Wyszukanie elementu polega na kolejnym sprawdzaniu pozycji w tablicy //T// wyznaczanych za pomocą ciągu do momentu aż dany element zostanie znaleziony, lub do momentu aż będzie wiadomo że danego elementu na pewno nie ma w tablicy. | + | |
| - | Wyróżniamy różne metody generowania ciągu: | + | |
| - | * liniowa | + | |
| - | * kwadratowa | + | |
| - | * dwukrotna | + | |
| - | Wstawienie wartości do tablicy polega na znalezieniu w niej wolnego miejsca. | + | |
| - | Kolejność w jakiej będziemy analizować elementy tablicy powinna zależeć od wstawianego klucza. W tym celu należy zmienić definicję funkcji haszującej tak aby przyjmowała dwa argumenty: | + | |
| - | * klucz, | + | |
| - | * numer wyrazu ciągu począwszy od zera. | + | |
| - | Pozycja w tablicy //T// jest zatem wyznaczana na podstawie klucza oraz wyrazu ciągu kontrolnego. Kolejne elementy tablicy //T// wyznaczone przy pomocy funkcji haszującej są następujące:\\ | + | |
| - | //<h(k,0),h(k,1),...,h(k,m-1)>// | + | |
| - | Powyższy ciąg jest oczywiście jedną z permutacji elementów zbioru //{0,1,...,m-1}// \\ | + | |
| - | Przykładowa funkcja wstawiania może wyglądać następująco:<code> | + | |
| - | func INSERT(T,k) | + | |
| - | i := 0 | + | |
| - | while i < m | + | |
| - | j := h(k,i) | + | |
| - | if T[j] = NIL | + | |
| - | return j | + | |
| - | else | + | |
| - | i := i + 1 | + | |
| - | end if | + | |
| - | end while | + | |
| - | wyrzuć wyjątek o przepełnieniu tablicy z haszowaniem | + | |
| - | end func | + | |
| - | </code> | + | |
| - | Algorytm wyszukiwania klucza //k// przegląda ten sam ciąg pozycji, które odwiedził algorytm wstawiania. Dlatego wyszukiwanie można przerwać jeżeli znajdziemy dany klucz lub gdy napotkamy pustą pozycję gdyż klucz z pewnością nie będzie wstawiony dalej. \\ | + | |
| - | Przykładowa funkcja wyszukiwania może wyglądać następująco:<code> | + | |
| - | func SEARCH(T,k) | + | |
| - | i := 0 | + | |
| - | j := h(k,i) | + | |
| - | while T[j] != NIL and i < m | + | |
| - | if T[j] = k | + | |
| - | return j | + | |
| - | end if | + | |
| - | i := i + 1 | + | |
| - | j := h(k,i) | + | |
| - | end while | + | |
| - | return NIL | + | |
| - | end func | + | |
| - | </code> | + | |
| - | Usuwanie elementów z tablic z haszowaniem przez adresowanie otwarte jest trudne. | + | |
| - | Jeżeli usuwany element wyznaczony za pomocą //i//-tej wartości ciągu kontrolnego to nie możemy tej pozycji po prostu oznaczyć jako wolnej gdyż w przeciwnym wypadku dostęp do kluczy wyznaczonych za pomocą dlaszych wyrazów ciągu zostanie zablokowany. Problem ten można rozwiązać przy pomocy stałej np. //DELETED// która będzie umieszczana w miejsce usuniętej wartości natomiast którą funkcja //insert// będzie traktowała tak samo jak //NIL//. Powodem jest to że funkcja //insert// powinna kontynuować przeszukiwanie ponieważ na pozycjach wyznaczonych przy pomocy kolejnych wyrazów ciągu kontrolnego mogą znajdować się dalsze elementy. \\ | + | |
| - | Powyżej wymienione metody generowania ciągów kontrolnych gwarantują że //<h(k,0),h(k,1),...,h(k,m-1)>// jest permutacją liczb //{0,1,...,m-1}// dla każdego klucza //k//. | + | |
| - | + | ||
| - | == Adresowanie liniowe == | + | |
| - | Adresowanie liniowe jest najprostszą metodą tworzenia ciągu kontrolnego. Funkcja haszująca ma postać: //h(k,i) = (h'(k)+i) modulo m//. \\ | + | |
| - | Gdzie: \\ | + | |
| - | //h':U → {0,1,...,m}// \\ | + | |
| - | h' jest zwane pomocniczą funkcją haszującą. \\ | + | |
| - | Z powyższego wzoru wynika że pierwszy wyraz ciągu (a więc jednocześnie pierwsza pozycja w tablicy //T//) ma wartość //h'(k)// natomiast kolejną jest //h'(k)+1// itd. \\ | + | |
| - | Adresowanie liniowe ma jedną poważną wadę polegającą na istnieniu tendencji grupowania zajętych pozycji (grupowanie pierwotne). Długie spójne ciągi zajętych pozycji powodują że średni czas wyszukiwania rośnie. | + | |
| - | + | ||
| - | == Adresowanie kwadratowe == | + | |
| - | W adresowaniu kwadratowym stosuje się funkcje haszujące postaci: //h(k,i) = (h'(k)+c<sub>1</sub>i+c<sub>2</sub>i<sup>2</sup>) modulo m// \\ | + | |
| - | gdzie //h'(k)// jest podobnie jak w adresowaniu liniowym pomocniczą funkcją haszującą. \\ | + | |
| - | Pierwszym wyrazem ciągu kontrolnego wyznaczanego poprzez adresowanie kwadratowe jest //h'(k)// a kolejne zależą od kwadratu numeru pozycji //i// w ciągu kontrolnym. | + | |
| - | Ta metoda jest lepsza od adresowania liniowego ponieważ w dużym stopniu eliminuje niebezpieczeństwa grupowania pierwotnego. | + | |
| - | + | ||
| - | == Haszowanie dwukrotne == | + | |
| - | Jest to najlepsza metoda adresowanie otwartego generowania ciągów kontrolnych. | + | |
| - | W haszowaniu dwukrotnym funkcja haszująca ma postać: //h(k,i) = (h<sub>1</sub>(k) + ih<sub>2</sub>(k)) modulo m// \\ | + | |
| - | Gdzie:\\ | + | |
| - | //h<sub>1</sub>// i //h<sub>2</sub>// są pomocniczymi funkcjami haszującymi.\\ | + | |
| - | W odróżnieniu od wcześniej opisanych metod w tej metodzie wyrazy ciągu kontrolnego w dwojaki sposób zależą od wartości klucza. **Aby mieć pewność że w razie potrzeby przeszukana zostanie cała tablica musimy zapewnić że wartość //h<sub>2</sub>(k)// jest względnie pierwsza z rozmiarem tablicy**. Warunek ten można łatwo spełnić np.: | + | |
| - | * dobierając pewna potęgę jako wartość //m// oraz zapewniając że //h<sub>2</sub>(k)// daje tylko wartości nieparzyste. | + | |
| - | * jako wartość //m// dobrać pewną liczbę pierwszą a następnie zagwarantować że wartościami //h<sub>2</sub>(k)// są tylko liczby dodatnie mniejsze od //m// \\ np.: \\ dla liczby pierwszej //m// można przyjąć: \\ //h<sub>1</sub>(k) = k modulo m// \\ //h<sub>2</sub>(k) = 1 + (k modulo m')// \\ gdzie //m'// jest nieco mniejsze od //m// np. (m-1). \\ Jeśli np. //k//=123456 //m//=701 i //m'//=700 to \\ //h<sub>1</sub>(k) = 80// oraz //h<sub>2</sub>(k) = 257//. | + | |
