Universal hashing

Vše co se týká bakalářských státních závěrečných zkoušek.

Universal hashing

Příspěvekod ('._.) » 24. 8. 2011 20:30

Ahoj,

mal by som otazku k univerzalnemu hashovaniu. To ako funguje a podmienky vyberu hashovacich funkcii chapem viz. napr wiki.
Ale unika mi jedna vec, ak idem napriklad zahashovat prvok X, tak vyberiem nahodne nejaku hashovaciu funkciu a s nou ho zahashujem. Ako je potom mozne ten prvok najst, alebo zistit ci sa v tabulke nachadza? Musi sa prejst cela mnozina hashovacich funkcii? To znie ako hlupost.

Dik.
('._.)
 

Re: Universal hashing

Příspěvekod Myshaak » 25. 8. 2011 13:58

('._.) píše:Ahoj,

mal by som otazku k univerzalnemu hashovaniu. To ako funguje a podmienky vyberu hashovacich funkcii chapem viz. napr wiki.
Ale unika mi jedna vec, ak idem napriklad zahashovat prvok X, tak vyberiem nahodne nejaku hashovaciu funkciu a s nou ho zahashujem. Ako je potom mozne ten prvok najst, alebo zistit ci sa v tabulke nachadza? Musi sa prejst cela mnozina hashovacich funkcii? To znie ako hlupost.

Dik.

Ono to totiz funguje malinko jinak. (Teda pokud jsem to za ty dva mesice, co jsem z Matfyzu, uplne nezapomnel! :D) Neni to tak, ze "mam prvek -> vyberu si nahodne funkci, s kterou ho zahesuju", ale "chci heshovat -> vyberu si nahodne funkci -> s touhle funkci pak uz hesuju vsechny prvky" - cili potom i pro nalezeni prvku pouziju tuhle predem vybranou (ale nahodne) funkci.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
 
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Bydliště: Tanvald / Troja A820
Typ studia: Informatika Mgr.


Zpět na Bakalářské SZZ

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron