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ý popis

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

• Stránky se štěpí rovnoměrně a předvídatelně
• Číslo stránky, kterou budeme příště štěpit, je rovno (n << 1) >> 1. Kde n je aktuální počet stránek a << a >> značí bitový posun vlevo a vpravo. Vlastně jde o počet stránek s vynulovaným nejvyšším jedničkovým bitem.
• Číslo bitu od konce, podle kterého budeme rozlišovat záznamy při štěpení, je [log n] + 1. Symbol log značí logaritmus o základu 2 a n opět určuje počet aktuálně existujících stráenk. Závorky [ ] znamenají dolní celou část.

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:

• Zjistíme, kterou stránku budeme štěpit. Označme si ji k.
• Alokujeme novou stránku v primárním souboru.
• Bit, podle kterého budeme rozlišovat záznamy, si označíme jako j-tý bit.
• Z štěpené stránky a její oblasti přetečení nakopírujeme do nové stránky záznamy, jejichž hašované hodnoty mají j-tý bit nastavený na 1. Pokud by se nová stránka přeplnila, tak jí hned vytvoříme oblast přetečení.
• Zvýšíme n (počet stránek) o jedničku. Tím umožníme vyhledávání a přidávání záznamů do nové stránky. Před tímto krokem o ní datová struktura vlastně "neví."
• Odstraníme záznamy s jedničkovou hodnotou j-tého bitu z původní stránky a její oblasti přetečení.