od Germoe » 30. 8. 2010 02:11
No, pokusím se...
Hašování je dvoufázové, tj. máme primární soubor, adresář, funkci, která hashuje do adresáře a skupinu funkcí, která pak z adresáře hašuje do primárního souboru.
První funkce závisí na klíči a na počtu řádků adresáře (např. h(k,s)=k mod s).
skupina funkcí je skupina funkcí dvou proměnných (např. hi(k,r)= (k>>i) mod r, pokud r je mocnina dvou; (k XOR i) mod r jinak).
V adresáři je na každém řádku trojice p (tj. počátek oblasti v primárním souboru), i (tj. kterou funkci použít) a r (tj. počet prvků v této oblasti).
Vyhledávání: Vezmeš klíč a proženeš ho funkcí h, pak koukneš na příslušný řádek do tabulky a získaná data proženeš funkcí hi; označme j=h(k,s), podíváme se na adresu pj + hi_j(k,rj) zda tam něco je a zda odpovídá klíč, pokud ne, pak požadovaný záznam neexistuje.
Vkládání: Vezmeš klič a proženeš ho funkcí h, tím zjistíš, do jakého bloku patří. Koukneš, zda je za oním blokem volné místo, pokud není, najdeš nejbližší volný blok délky r+1 a změníš v adresáři p příslušným způsobem. Zvětšíš r na r+1. Hledáš nejnižší i takové, že v bloku nenastane kolize, aktualizujeme v adresáři hodnotu i a přerovnáme prvky bloku dle výsledků funkce hi. Pokud se nepodaří rozmístit prvky, opět zvýšíme r o jedna (může znovu vzniknout potřeba přemístit blok)... mohou v souboru vznikat díry, je tedy vhodné ho občas "setřást".
No, pokusím se...
Hašování je dvoufázové, tj. máme primární soubor, adresář, funkci, která hashuje do adresáře a skupinu funkcí, která pak z adresáře hašuje do primárního souboru.
První funkce závisí na klíči a na počtu řádků adresáře (např. [i]h(k,s)=k mod s[/i]).
skupina funkcí je skupina funkcí dvou proměnných (např. [i]h[sub]i[/sub](k,r)= (k>>i) mod r, pokud r je mocnina dvou; (k XOR i) mod r jinak[/i]).
V adresáři je na každém řádku trojice [i]p[/i] (tj. počátek oblasti v primárním souboru), [i]i[/i] (tj. kterou funkci použít) a [i]r[/i] (tj. počet prvků v této oblasti).
Vyhledávání: Vezmeš klíč a proženeš ho funkcí [i]h[/i], pak koukneš na příslušný řádek do tabulky a získaná data proženeš funkcí [i]h[sub]i[/sub][/i]; označme [i]j=h(k,s)[/i], podíváme se na adresu [i]p[sub]j[/sub] + h[sub]i_j[/sub](k,r[sub]j[/sub])[/i] zda tam něco je a zda odpovídá klíč, pokud ne, pak požadovaný záznam neexistuje.
Vkládání: Vezmeš klič a proženeš ho funkcí [i]h[/i], tím zjistíš, do jakého bloku patří. Koukneš, zda je za oním blokem volné místo, pokud není, najdeš nejbližší volný blok délky [i]r+1[/i] a změníš v adresáři [i]p[/i] příslušným způsobem. Zvětšíš [i]r[/i] na [i]r+1[/i]. Hledáš nejnižší [i]i[/i] takové, že v bloku nenastane kolize, aktualizujeme v adresáři hodnotu [i]i[/i] a přerovnáme prvky bloku dle výsledků funkce [i]h[sub]i[/sub][/i]. Pokud se nepodaří rozmístit prvky, opět zvýšíme [i]r[/i] o jedna (může znovu vzniknout potřeba přemístit blok)... mohou v souboru vznikat díry, je tedy vhodné ho občas "setřást".