Perfektni hashovani od Cormacka
- Almer
- Site Admin
- Příspěvky: 686
- Registrován: 12. 10. 2004 10:58
- Typ studia: Informatika Ph.D.
- Login do SIS: lasap4am
- Bydliště: Mala Strana - 203
- Kontaktovat uživatele:
Perfektni hashovani od Cormacka
Vysvetli mi to nekdo trosku polopatisticky? Tedy lidsky?
Zakládající člen klubu Ortodoxních Matfyzáků
Jsem LAMER ale neumim se ani podepsat ]
Jsem LAMER ale neumim se ani podepsat ]
-
- Matfyz(ák|ačka) level I
- Příspěvky: 34
- Registrován: 28. 5. 2008 15:40
- Typ studia: Informatika Ph.D.
Re: Perfektni hashovani od Cormacka
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".
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".
Re: Perfektni hashovani od Cormacka
http://wiki.matfyz.cz/wiki/DBI007_probr ... Cormack.29 - toto by nepomohlo? (Cormacka jsem se ucil na zkousku v ramci OZD I, ne II)
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW