COMPUTERWORLD
pod kapotou
Hašování

Jedním z kritérií hodnocení dobře fungujícího databázového systému je rychlost přístupu k požadovaným datům podle hodnoty klíče K, tj. vybraného atributu (nebo skupiny atributů). Tento problém se nejčastěji řeší indexováním. Indexová struktura založená na B-stromech nabízí takový rychlý přístup. Pro nalezení prvního záznamu s hodnotou klíče K stačí přečíst několik stránek z disku, v závislosti na hloubce B-stromu.

Nejlepší by ovšem bylo přečíst stránku pouze jednu, tj. mít k dispozici tzv. přímý přístup. Možná, že by stačilo vzít hodnotu klíče tabulky (záznamu) a chápat ji přímo jako adresu na disku. Tato možnost je ovšem v praxi těžko uskutečnitelná. Např. je-li klíčem RODNÉ_ČÍSLO, pak pro relaci ZAMĚSTNANEC obsahující data o 1000 zaměstnancích bychom potřebovali obrovský diskový prostor (pro nositele potencionálně všech rodných čísel), který by ale byl zaplněn pouze na 1000 místech.

Mnohem lepší ideou je nalézt funkci, která transformuje hodnotu klíče na adresu. Již ze střední školy známe, že jeden ze způsobů, jak zadat funkci, je tabulka. Tak toto není ten případ. Tím bychom se vlastně zase dostali k indexování (první úroveň indexu je právě takovou tabulkou). Takže spíše půjde o funkci vyjádřenou nějakým předpisem, algoritmem.

Již dávno před databázemi používali tuto techniku tvůrci operačních systémů, překladačů apod. Jde o tzv. hašování. Proč zrovna hašování? Hašování jako haše. Jde o počeštění angl. slova hashing. Skutečně, hašování je na místě, neboť funkce realizující hašování občas připomínají kuchyňskou techniku “rozsekání” něčeho na haši. Pro mladší informatiky připomínám, že podle dávné normy pojmů výpočetní techniky se místo hašování říkalo metoda rozptýlených tabulek. Nejstarší článek o hašování znám z roku 1968 (J. Morris, Scatter Storage Techniques, CACM, 11, 1), pro zájemce lze doporučit nahlédnout do díla D. Knutha “Art of Computer Programming” z r. 1973.

O co však jde. Představme si adresový prostor velikosti {0,1,...,M-1}. Každé (relativní) adrese odpovídá místo v paměti, do kterého lze uložit hodnotu nějakého klíče K (např. RODNÉ_ČÍSLO). Této datové struktuře se tradičně říká hašovací tabulka. Předpokládaný počet hodnot klíče je N, kde M³ N. Obvykle N = 0,8M, tj. počet míst hašovací tabulky je o něco větší než množina hodnot klíče K, které do něj chceme vložit.

Hašovací funkce je výpočetně jednoduchý předpis, kterým transformujeme hodnoty klíče do relativních adres adresového prostoru (absolutní adresy se spočtou snadno pouhou lineární transformací). Jinými slovy řečeno pomocí hašovací funkce se “strefujeme” do hašovací tabulky a umisťujeme hodnoty klíčů na odpovídající místa. Bylo by iluzorní se domnívat, že funkci lze nalézt tak, že dvěma různým hodnotám klíče odpovídají dvě různé adresy, tj. že funkce bude prostá. Vznikají kolize, tj. několik hodnot klíčů má být umístěno na jednom místě. Kolize se řeší obvykle tzv. otevřeným adresováním, tj. kolidující hodnota klíče se umístí na nejbližší volné místo s vyšší adresou, případně se začne od začátku hašovací tabulky. Toto tzv. rehašování lze provádět i jiným, rafinovanějším způsobem, např. další hašovací funkcí (dvojité hašování) nebo, podobně jako u indexsekvenční organizace, pomocí oblasti přetečení, přičemž kolidující záznamy jsou zřetězeny pomocí ukazatelů.

Hledání v takovéto datové struktuře je podobné vkládání prvků do struktury. K hodnotě klíče k dané hašovací funkci h spočteme hodnotu h(k) interpretovanou jako relativní adresu do hašovací tabulky T. Je-li na místě h(k) v T klíč k, je vše v pořádku, není-li, je nutno postupovat v souladu se strategií, jak byly řešeny kolize. Např. při otevřeném adresování se od daného místa prohledává T sekvenčně. Co když ale k v T není? Pak se samozřejmě hledá do prvního volné místa v T. Tím je zaručeno, že k se v T nenachází.

Lze tušit, že kvalita hašování je silně závislá na vlastnostech hašovací funkce. Kritériem vhodnosti je např. průměrná délka řetězce kolidujících prvků. Hašovacích funkcí existuje mnoho, včetně matematické analýzy jejich vlastností. Jednou z nejefektivnějších hašovacích funkcí je h = k mod M' (zbytek po dělení M', kde M' je nejbližší prvočíslo menší než M a k je číselný klíč). Zřejmě platí 0£ h(k) £ M'-1£ M.

Je-li h prostá funkce, hovoříme o perfektním hašování, je-li navíc M = N, jde o minimální perfektní hašování (obojí se v praxi vyskytuje poměrně zřídka). Perfektní hašování se někdy také nazývá případ, kdy hašování vede ke konstantnímu počtu přístupů na disk, hledáme-li záznam s daným klíčem.

Jiným problémem je, že ne každá množina prvků je okamžitě připravena k hašování. Např. hodnoty atributu ADRESA jsou dlouhé řetězce znaků, které je nutné nejprve upravit. To se obvykle dělá metodou skládání (folding). Řetězec se rozdělí na skupiny po 4 znacích, ty se chápou jako řetězec nul a jedniček. Ze všech takto vzniklých řetězců se vytvoří pomocí aplikace operátoru XOR (výlučné nebo) 32bitové číslo. Skládání také zabezpečí, že původní, možná nerovnoměrné rozložení hodnot klíče, se bude po transformaci blížit rovnoměrnému. Další “náhodnost” vnese do metody použití funkce h, tj. cílem je, aby se hašovací tabulka zaplňovala co nejrovnoměrněji.

Tabulka samotných hodnot klíčů není příliš užitečná. Metodu lze snadno využít pro ukládání záznamů s klíčem K či řádků tabulky relační databáze. Pozor, zatím však šlo u datovou strukturu ve vnitřní paměti, tj. v dané podobě je metoda pro databáze nepoužitelná. I když ... . Existují techniky pro zpracován spojení relací, kdy se jedna z nich celá hašuje do vnitřní paměti (viz příští pokračování Databázové abecedy).

Implementace přímého přístupu v diskovém prostředí znamená realizovat hašování v adresovém prostoru stránek. To lze chápat buď tak, že interval <0,M-1> reprezentuje adresy stránek a hodnoty hašovací funkce jsou celá čísla z tohoto intervalu. Pak vlastně všechny kolidující záznamy padají do jedné stránky a v případě přetečení do následujících.

Jinou možností je určit přímo i relativní pozici záznamu ve stránce. Samozřejmě záznamy musí být pevné délky. Pak hašovací funkce h1 může pro dané klíče dávat hodnoty z intervalu <0, 1) a výsledná funkce h může být definována jako

h(x) = ë M* b * h1(x) û

kde b je blokovací faktor, tj. maximální počet záznamů, které se vejdou do stránky, a ë x û dává celou část x. Řešení kolizí je řízeno strategií “umístit záznam, který koliduje, pokud možno na téže stránce, kam skutečně patří”. Tímto způsobem obdržíme datovou strukturu zvanou obvykle soubor s přímým přístupem. Obvykle už není na místě hovořit o hašovací tabulce. T je nyní prostor na disku vybraný pro uložení souboru či relace. Na obr. 1 je ukázána typická situace s kolizí, kdy hodnota klíče 45 koliduje s hodnotou 97 a rehašováním se dostává na místo 73.

Definujme nyní faktor naplnění l prostoru T jako N/M. Intuice říká, že bude-li nízký faktor l (celého prostoru), tj. prostor pro záznamy bude dostatečně veliký, obdržíme hledaný záznam pravděpodobně na jeden přístup. Naopak, se vzrůstajícím l by se měla prodlužovat délka řetězce záznamů, které kolidují v daném místě.

 

 

 

 

h(45) = 70

29

56

31

49

97

35

80

45

10

str. 0 0-15

str. 1 16-31

str. 2 32-47

str. 3 48-63

str. 4 64-79

str. 6 80-95

Obr. 1 Příklad kolize při vstupu hodnoty klíče 45

Budeme předpokládat, že hodnoty klíče jsou nahodilé a vzájemně nezávislé. Faktor naplnění lze též interpretovat jako pravděpodobnost, že místo dané hodnotou h(k), kde k je klíč, je obsazené. Lze dokázat jednoduché, ale užitečné tvrzení.

  • Je-li l je faktor naplnění adresového prostoru při hašování s lineárním prohledáváním, pak pro předpokládanou délka řetězce kolizí L platí

E(L) = 1/(1-l )

Např. pro l = 0,5, vychází E(L) = 2, pro l = 0,9, pak E(L) = 10.

Pro soubor uložený ve stránkách je rozhodující spíše faktor naplnění stránky a počet záznamů ve stránce. Důležité je, jak jsou řetezce kolizí rozloženy do stránek. Měření např. ukazují, že při faktoru naplnění stránky 0,8 a b = 40 je pravděpodobnost čtení další stránky 0,01 a to je přijatelný výsledek.

Protože použitý paměťový prostor zůstává u hašování během aktualizací neměnný (hovoří se též o statickém hašování), zhoršuje se průměrný čas přístupu k jednomu záznamu (vinou např. délky řetězce v oblasti přetečení nebo lineárním prohledáváním adresového prostoru) na ekvivalent sekvenčního prohledávání souboru. Problém se řeší reorganizací kompletní struktury, což těžko obstojí např. v databázových systémech či při vícenásobném přístupu k souborům. Zdůrazněme také, že hašování je vhodné, když K je jednoznačný klíč (v relačním modelu dat jde např. o primární klíč relace). Modifikace hašování pro libovolný klíč je však možná.

Jinou nevýhodou statického hašování je, že takto organizovaný soubor nemá žádné uspořádání, což snižuje je ho použitelnost v některých typech dotazů.

Existují dynamické metody, které řeší problém přístupu tak, že je vždy zachován konstantní počet přístupů při hledání podle hodnoty klíče. Dále existují i takové metody, které hašují způsobem, který zachovává uspořádání.



<seznam dílů seriálu>   <COMPUTERWORLD>