Faginovo hašování (Rozšiřitelné hašování - Extendible hashing)

aneb něco z organizace a zpracování dat I. Tento algoritmus má sloužit k efektivnímu přístupu k velkému množství dat, která se najedou nevejdou do paměti.

Máme hašovací funkci H, která každý klíč K převede na řetězec R+1 bitů. Přičemž tato hašovací funkce musí rovnoměrně rozmisťovat své hodnoty i pro neznámý definiční obor klíčů.

Schéma obsahuje pomocnou strukturu - adresář -, což je pole ukazatelů do primárního souboru. Toto pole je přibližně tak velké jako předpokládaný počet stránek (do každé stránky se vejde b záznamů). Velikost adresáře je 2^D. D je parametr a s přidáváním nových záznamů postupně narůstá.

Vyhledávání záznamu

Pokud vyhledávámě nějaký záznam, tak vezmeme jeho klíč K a vypočteme jeho hašovanou hodnotu H (K). Vezmeme jejích D prvních bitů, které budou tvořit index do adresáře. Například pokud D = 3 a hašovaná hodnota vyjde 10111001 (R = 7), index do adresáře je 5 (tedy šestá položka od začátku, protože se indexuje od nuly). Záznam s daným klíčem se tedy musí nacházet ve stránce, jejíž adresu obsahuje šestá položka od začátku adresáře.

Při zjišťování, zda se záznam nachází v dané stránce se může využít bitů hašovaného klíče, které se nepoužily při indexování do adresáře. Jako řešení kolizí se prý používá otevřené adresování (definuje se nějaká hašovací funkce H2 (k, i), kde i je počet nezdarů, přičemž H2 (k, 0) = H (k)). Když se záznam ve stránce nenajde, nenachází se v primárním souboru.

Každá stránka si uchovává tzv. lokální hloubku D', což udává, v kolika prvních bitech se shodují haošvané hodnoty klíčů jejích záznamů. D' musí být menší nebo rovno D (hloubce adresáře). Navíc pokud je D' ostře menší než D, z adresáře na danou stránku vede více odkazů (přesně jich je 2^(D - D')).

Příklad: Máme stránku s D' = 3 a adresář s D = 5. Dejme tomu, že jeden z odkazů na tuto stránku se v adresáři nachází pod indexem 11100. To znamená, že v dané stránce se nachází pouze záznamy, jejichž hašované hodnoty klíče mají stejne první tři bity - kokrétně 111. V ostatních bitech se hašované hodnoty klíčů mohou lišít. To znamená, že na danou stránku musí odkazovat i položky adresáře s indexy 11101, 11110 a 11111, protože také mají stejné první tři bity jako index 11100. Toto pozorování vede k zajímavému důsledku, že pokud na nějakou stránku odkazuje více položek adresáře, jsou tyto položky umístěny za sebou.

Vkládání nového záznamu

Zpočátku postupujeme velmi podobně jako v případě vyhledávání určitého záznamu. Zahašujeme klíč a pohledem do adresáře zjistíme, do jaké stránky nový záznam patří. Pokud vkládaný záznam již existuje, operace vkládání selže. V opačném případě vložení nic nebrání. Celý algoritmus se může rozvětvit do několika případů:

• Stránka ještě není naplněna. Nový záznam do ní vložíme a tím celá operace končí.

• Stránka je naplněna, ale její D' je ostře menší než parametr adresáře D. Stránku musíme rozštěpit. Vytvoříme novou stránku. Oběma stránkám nastavíme D' na hodnotu o jedničku vyšší než měla stará stránka. To znamená, že ve staré stránce, kde se dříve nacházely záznamy s klíčem, jejichž hašované hodnota se shodovaly v old(D') bitech, budou teď záznamy, jejichž hašované hodnoty klíčů se shodují v old(D') bitech a jejich další bit má hodnotu 0. Do nové stránky umístíme záznamy, jejichž hašované hodnoty klíčů se shodují v old(D') bitech následovaných bitem s hodnotou 1. Pokud by při tomto přerozdělování opět došlo k přeplnění jedné ze stránek, musíme příslušnou stránku opět rozdělit na dvě a zvednout o jedničku jejich D'. A to dělat tak dlouho, dokud se bude nějaká stránka přeplňovat. Po každém štěpení a přerozdělení původních záznamů je nutné upravit položky v adresáři, které odkazovaly na původní stránku, do níž se vkládalo (a která se rozštěpila). Tyto položky adresáře se budou nacházet za sebou, a protože D >= D', přiřazení bude triviální (nová stránka bude na vyšším indexu než ta stará).

• Stránka je naplněna a její D' je rovno parametru adresáře D. Provedeme štěpení stránky na dvě a přerozdělíme záznamy. Právádíme úplně stejně jako v předchozím případě. Tak dostaneme (nejméně dvě) stránky, jejichž D' > D, což je porušení invariantu. Musíme zvětšit adresář. Zvýšíme hodnotu jeho parametru D o jedničku, čímž zdvojnásobíme počet jeho položek. V adresáři se tedy budou rozlišovat hašované hodnoty klíčů záznamů o jeden bit delší. Nyní je třeba přepointrovat celý adresář. Provádí se to odzadu ("odspoda").

  Přitom platí, že se pro každou stránku krom těch, co vznikly štěpením, zvýšil rozdíl mezi jejím D' a D, z čehož plyne, že na ni musí ukazovat více položek (minimálně dvakrát více - ale adresář se může postupně zvětšovat vícekrát). Například pokud na stránku (do které se aktuálně nevkládá) s D' = 3 v adresáři s D = 5 odkazovaly položky s indexy 11000, 11001, 11010 a 11011, a adresář zvětšil svoje D na hodnotu 6, budou na tuto stránku ukazovat položky 110000, 110001, 110010, 110011, 110100, 110101, 110110 a 110111. Zde si všimneme dvou věcí: (1) Na stránku budou ukazovat položky, které mají D' bitů shodných s položkami, které na ni odkazovaly před zvětšováním adresáře. (2) Nově odkazující položky mají větší index než staré odkazující položky. (2) plyne z toho, že indexy nových položek jsou reprezentovány více bity a že se jejich index rozšířil o nejnižší (nejpravější) bit. (1) plyne z toho, co znamená pro stránku D'. Takže jak provedeme ono "přepointření?"

  Máme nový adresář (již jsme zvětšili D o jedničku). Začneme od hodnoty s největším indexem, což je 111111 (D = 6). Tato položka bude odkazovat na stejnou stránku jako odkazuje index 11111. Další polžoka, která nese index 111110, bude odkazovat též na místo, kam ukazuje 11111. A takhle postupně odzdola procházíme všechny položky adresáře a upravujeme ukazatele (vždy se podíváme, kam ukazuje hodnota s pětibitovým indexem, a stejnou adresu nahrajeme do dvou po sobě jdoucích hodnot s šestibitovými indexy).

Upozornění: Při vkládání je třeba zachovávat konzistenci. Proto po štěpení stránky a přerozdělení původních záznamů musíme upravit adresář, a až poté se znovu pokusit vložit nový záznam. Adresář vždy musí být konzistentní s primárním souborem (představte si, že může v libovolném okamžiku vypadnout proud a náš server nikdo nezajistil UPSkou. Předpokládá se ale, že jednotlivé operace zápisu stránek na disk jsou atomické, stejně tak úprava položek adresáře). To znamená, že i při štěpení stránek musíme postupovat velmi opatrně:

• Vytvořit dvě nové stránky již se zvýšeným D'.
• Naskládat do nich původní záznamy.
• Upravit adresář.
• Prohlásit původní stránku za volnou.
• Pokusit se do jedné z nových stránek (podle hašované hodnoty klíče víme, do které) vložit nový záznam.
• Při dalším přetečení opakovat celý cirkus znova

Takže jsem postup při vkládání nového záznamu popsal sice obecně správně, ale špatně z pohledu zachovávání konzistence indexu. Při štěpení vytváříme dvě nové stránky, do kterých přerozdělujeme záznamy ze stránky původní, kterou však NERUŠÍME, dokud neupravíme index.

Toto upozornění je jen moje pozorování. Může existovat jednodušší způsob, nebo to celé nemusí být pravda... Tím myslím use it on your own risk.