Perfektni hashovani od Cormacka

Uživatelský avatar
Almer
Site Admin
Příspěvky: 686
Registrován: 12. 10. 2004 10:58
Typ studia: Informatika Ph.D.
Bydliště: Mala Strana - 203
Kontaktovat uživatele:

Perfektni hashovani od Cormacka

Příspěvek od Almer »

Vysvetli mi to nekdo trosku polopatisticky? Tedy lidsky?
Zakládající člen klubu Ortodoxních Matfyzáků :-D

Jsem LAMER ale neumim se ani podepsat ]:-)
Germoe
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

Příspěvek od Germoe »

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".
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: Perfektni hashovani od Cormacka

Příspěvek od Him »

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 ;)
Odpovědět

Zpět na „NDBI003 Organizace a zpracování dat II“