18-haszowanie, struktury danych, haszowanie

//-->.pos {position:absolute; z-index: 0; left: 0px; top: 0px;}(adresowanie rozpraszające, mieszające)HaszowanieHaszowanieW adresowaniu haszującym wyróżniamy następująceelementy:funkcja haszująca(hash function), h, której argumentem jest wartośćx nazywanakluczem haszowanym(hash key);x jest wartością pewnego pola lub grupy pól w rekordach określonegotypu;h(x) jest liczbą całkowitą z przedziału [0, B – 1], gdzie B jest liczbąkubełków(ang.buckets), tj. pozycji w pewnej przestrzeni adresowej;przez kubełek rozumiemy zbiór rekordów, dla których funkcjahaszująca przyjmuje tę samą wartość (funkcja ta dla różnychrekordów i dla różnych kluczy haszujących może zwracać tę samąwartość)Tadeusz PankowskiH. Garcia-Molina, J.D. Ullman, J. Widom,Implementacja systemów baz danych, WNT, Warszawa, 2003Haszowanie, T. Pankowski1Haszowanie, T. Pankowski2Haszowanie – pośrednie ibezpośrednieKubełek może być implementowany na wielesposobów:wartość funkcji haszującej jest traktowana jako pozycjaw pewnejtablicy haszowej, która zawiera wskaźniki napoczątek listy bloków rekordów przyporządkowanych dodanego kubełka (hashowanie pośrednie);wartość funkcji haszującej wskazuje bezpośredniopierwszy blok rekordów przyporządkowanych dodanego kubełka (hashowanie bezpośrednie);xHaszowanie pośrednie1...k...B–1......h(x)...r1, ..., rn...r’1, ..., r’n’*......Ogólny schemat haszowania pośredniego: tablica haszowaidentyfikuje kubełki i zawiera wskaźniki na listy blokówrekordów o jednakowej wartości funkcji haszującejHaszowanie, T. Pankowski3Haszowanie, T. Pankowski4Haszowanie bezpośrednieHaszowanie jako metodaindeksowania• Zauważmy,żejeśli w blokach pamiętane są niecałe rekordy (krotki), ale adresy rekordów(wskaźniki do rekordów pamiętanych w plikach),to haszowanie, podobnie jak na przykład indeksyo strukturze B-drzewa, może być traktowane jakometoda szybkiego dostępu do tych rekordów.• Wówczas celowe jest współistnienie wieleścieżekdostępu (adresowań haszujących), a którychkażda organizowana jest dla innych atrybutów(kluczy) wyszukiwania.5Haszowanie, T. Pankowski6xh(x)1...B–1Funkcja haszująca wskazuje na pierwszy blokrekordów. Rekordy nadmiarowe umieszczane są wblokach przepełnień.Haszowanie, T. PankowskiHaszowanie – operacja dołączaniaINSERT:h(a) = 1h(b) = 2h(c) = 1h(d) = 0h(e) = 1123Haszowanie – operacja usuwaniaDelete:efc123dacbeabc defgbyć może“g” do górydPamięć haszowana.Blok mieści 2 rekordy.Rekordy nadmiaroweumieszczane są w blokachnadmiarów (przepełnień).Haszowanie, T. Pankowski7Haszowanie, T. Pankowski8Funkcja haszująca – przykładklucz = ‘x1x2… xn’ n-bajtowy ciąg znakówB – liczba kubełkówh := x1+ x2+ ….. xn(suma kodów znaków)adres := h mod B, (liczba od 0 do B-1)�½Ta funkcja może być niedobra …�½Patrz: Knuth Vol. 3 – przegląd funkcjihaszujących.Dobra funkcjahaszująca:równomiernie rozprasza wartościkluczy na wszystkie kubełkiniski koszt obliczenia wartości•Haszowanie, T. Pankowski9Haszowanie, T. Pankowski10Rozmieszczanie rekordów w kubełkach• Czy rekordy posortowane wg klucza?Tak, jeśli czas CPU jest parametrem krytycznymi operacje Insert/Delete niezbyt częsteReguła efektywności• Współczynnik wykorzystania pamięcimiędzy 50% a 80%Wsp.wykorzystania = faktyczna liczba kluczymaksymalna liczba kluczyJeśli < 50%, marnowanie pamięciJeśli > 80%, częste przepełnieniazależy od jakości funkcji haszująceji od liczby kluczy na blokHaszowanie, T. Pankowski11Haszowanie, T. Pankowski12Jak radzić sobie ze wzrostem liczby kluczy?• Przepełnienia i ich reorganizacja• Haszowanie dynamiczneRozszerzalne(Extensible)Haszowanie dynamiczneLiniowe(Linear)Haszowanie, T. Pankowski14Haszowanie rozszerzalneRóżnica względem statycznych tablic haszowych:1.Istnieje poziom pośredni zawierający tablicę haszową kubełków, tj.wskaźników na bloki reprezentujące kubełki (pierwsze bloki tychkubełków).2.Tablica haszowa może się zwiększać. Jej długość jest zawsze potęgąliczby 2. Przy zwiększaniu tablica podwaja swoją długość.3.Nie muszą istnieć bloki danych dla każdego kubełka; niektórekubełki mogą wskazywać na ten sam blok, jeśli blok ten możepomieścić rekordy należące teoretycznie do różnych kubełków.4.Funkcja haszująca oblicza dla każdego klucza ciąg b bitów (np.b=32). Jednak na danym kroku haszowania wykorzystywana jestmniejsza liczba bitów, tj. i bitów początkowych ciągu. Oznacza to,żetablica haszowa kubełków zawiera wówczas 2ipozycji.Haszowanie rozszerzalneWykorzystanie pierwszychispośródbbitówtworzonych przez funkcję haszującąbh(K)→00110101wybieramyi→zwiększa się w czasie ….Haszowanie, T. Pankowski15Haszowanie, T. Pankowski16Haszowanie rozszerzalnei=1110001Wskazuje ile bitów jestbranych pod uwagęDołączanie przy haszowaniu rozszerzalnym –powstanie przepełnieniai=11100011. Wymagane jest utworzeniedodatkowego kubełka.2. Konieczne staje siępowiększenie (podwojenie)wielkości tablicy haszowej.3. Przyjmujemy i = 2.Adres bloku dla kluczyzaczynających się na 1110011100110011010 1100b=4, i=1Tablica haszowa ma tylko dwie pozycje.Pierwsza wskazuje na kubełek rekordów, dla których pierwszy bit wartościfunkcji haszującej h(x) jest 0, a druga – dla których pierwszy bit jest równy 1.Z każdym kubełkiem związana jest liczba i wskazująca liczbę rozróżnialnychbitówHaszowanie, T. Pankowski17Insert 101011100Haszowanie, T. Pankowski18Dołączanie przy przy haszowaniu rozszerzalnym –rozwiązanie problemu przepełnieniai=1110001Dołączanie przy przy haszowaniu rozszerzalnym –tworzenie nowego bloku dla kubełkai= 200011011i=200012000000011 20001 01110111210011010211001 210011010 11001011Insert 10101 21100Nowa tablica haszowaInsert:Zawartość dwóch kubełków (00 i 01)umieszczona jest w jednym blokuDołączenie wymagautworzenia nowego bloku dlakubełka 00 i rehaszowaniadotychczasowego bloku.Nie ma potrzeby zmianytablicy haszowej.01110000Haszowanie, T. Pankowski19

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

hannaeva.xlx.pl