|
Lineární hašování (Litwin)Lineární hašování je zajímavé zejména tím, že nedochází ke štěpení stránek, kterým by hrozilo přetečení, ale štěpení probíhá rovnorměrně. Jedou za čas se rozštěpí každá stránka, ať je plná nebo prázdná. Protože štěpení není ovlivněno tím, kam vkládáme, používá se při vkládání do plné stránky tzv. oblast přetečení, což si můžeme představit jako seznam stránek se záznamy, které se do původní stránky nevešly (dalo by se implementovat třeba jako spojový seznam). Odkaz na tento seznam může být uložen v příslušné plné stránce primárního souboru. Obecný popisNa počátku začínáme s jednou stránkou (označme si ji 0), do které budeme ukládat všechny záznamy. Pokud se tam nevejdou, využijeme oblast přetečení. Přičemž ke štěpení dochází po každých L vkládáních (L je parametr zvolený na začátku tvorby primárního souboru). V původní stránce 0 zůstanou záznamy, jejichž poslední bit hašovaného klíče má hodnotu 0, do nové stránky s číslem 1 se přesunou ty záznamy, co mají poslední bit hašované hodnoty klíče jedničkový. Po dalších L vkládáních dochází opět ke štěpení stránky 0. Tentokrát přibude stránka s číslem 2. Záznamy ze stránky 0 se rozdělí podle předposledního bitu hašované hodnoty klíče - takže ve stránce 0 zůstanou záznamy, jejihž hašovaná hodnota končí na 00, a stránka 2 bude obsahovat záznamy končící na 10 (binárně). Po dalších L vkládáních se štěpí stránka 1 (rozlíší se záznamy, jejichž hašované hodnoty končí na 01 a 11). Pravděpodobně už v tom vidíte jistou pravidelnost. Pro jistotu ještě přidám tabulku, která by měla vše zpřehlednit.
Z tabulky můžeme vypozorovat například následující zákonitosti:
VkládáníVkládání je operace velmi jednoduchá. Jediná potíž spočívá v určení čísla stránky, kam nový záznam patří. To uděláme tak, že vezmeme [log n] + 1 posledních bitů hašované hodnoty záznamu ([log n] nám říká, kolik "hašovcích cyklů" již proběhlo - kolikrát byla hašována stránka 0). Pokud je takto získaná hodnota větší nebo rovna aktuálnímu počtu stránek, zanedbáme její nejvýznamnější bit. Tím dostaneme výsledné číslo stránky. Když totiž posledních [log n] + 1 bitů hašované hodnoty klíče dá vyšší číslo než n, záznamy ještě nebyly podle bitu [log n] + 1 od konce rozlišovány, a proto jej musíme zanedbat. Samozřejmě si musíme hlídat počet úspěšně provedených vkládání a nezapomínat po k*L (k je libovolné přirozené číslo) takových operací štěpit. Při štěpení je opět třeba zachovat konzistenci. Celá operace by šla provést například takto:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
A closed mouth says nothing wrong; a closed mind does nothing right. |