Mel bych dotaz, jak vlastne funguje to Universalni hashovani, ani po preceteni skript a zapisku nemam pocit, ze znam byt jen myslenku teto metody.
Definuje se tam, ze trik je udajne ve vyberu hashovaci funkce z nejake mnoziny funkci, dale existence c-universalnich systemu, ale k cemu je to dobre a jak se to aplikuje pri samonem vypoctu, to je mi zahadou.
...idealne by se hodilo znat, pokud jste tu otazku dostali u zkousky, co vsechno chtel vedet. Diky
Univerzalni hashovani?
- Necroman
- Supermatfyz(ák|ačka)
- Příspěvky: 459
- Registrován: 20. 1. 2005 19:46
- Typ studia: Informatika Mgr.
- Login do SIS: suchm4am
- Bydliště: Louny / kolej Jednota, Praha
- Kontaktovat uživatele:
Univerzalni hashovani?
Naposledy upravil(a) Necroman dne 24. 1. 2008 09:27, celkem upraveno 1 x.
WANTED:
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
Dead or Alive
^-^
( ^ )
Schroedinger's Cat
-
- Matfyz(ák|ačka) level III
- Příspěvky: 186
- Registrován: 10. 12. 2004 22:35
- Typ studia: Informatika Bc.
- Kontaktovat uživatele:
Re: Universlani hashovani?
Skus mrknut sem:
http://techie.devnull.cz/skola/ds/ds.pdf
Je to tam sice pekne popisane ale nie az tak pekne aby sa mi to oplatilo ucit.
Viacmenej este prikladam hint ako som to pochopil ja:
Insert:
Mas nejaku tabulku a v nej hodnoty. K nim konkretnu has.fciu. patriacu do suboru has.fcii. H nejak oindexovane. (toto je dane)
Ak pridavas a dlzka j-teho retazca by bola mensia nez konstanta ktoru si na zaciatku stanovis, tak potom najdes novu hashovaciu fciu a cele to prehashujes. Kde ta nova hash fcia, ti da nejaku rezervu aby si to nemusel cele stale prehashovavat. Je tam este najaka podmienka kedy sa to prehesovava ale nejak si nemozem spomenut - ma to nieco spolocne stym aku velka je mnozina hashovanych prvkov a aka velka je tabulka.
Ak sa neporusia tieto podmienky, tak to skratka pridas povodnou hash.fciou.
Delete:
Opacny postup.
Cele to ber ako hint - mozno som to blbo pochopil a naviac cele preskocil :/ ....snad to dnes nedostanem.
Vela stastia na skuske!!!
PS: vyhodu to ma taku ze mozes neahodne vstupne data "znahodnit" dobrou hash fciou.
predstav si ze mas:
f1(x) = x mod 10
vstupne data 10, 20, 30, 40, 50, 60, 70,...
po tomto usudis ze by bola dobra
f2(x)=x/10 mod 10
vstupne data 10, 20, 30, 40, 50, 60, 70, 11, 12, 13, 14
a skratka to zas zmenis na f3....
http://techie.devnull.cz/skola/ds/ds.pdf
Je to tam sice pekne popisane ale nie az tak pekne aby sa mi to oplatilo ucit.
Viacmenej este prikladam hint ako som to pochopil ja:
Insert:
Mas nejaku tabulku a v nej hodnoty. K nim konkretnu has.fciu. patriacu do suboru has.fcii. H nejak oindexovane. (toto je dane)
Ak pridavas a dlzka j-teho retazca by bola mensia nez konstanta ktoru si na zaciatku stanovis, tak potom najdes novu hashovaciu fciu a cele to prehashujes. Kde ta nova hash fcia, ti da nejaku rezervu aby si to nemusel cele stale prehashovavat. Je tam este najaka podmienka kedy sa to prehesovava ale nejak si nemozem spomenut - ma to nieco spolocne stym aku velka je mnozina hashovanych prvkov a aka velka je tabulka.
Ak sa neporusia tieto podmienky, tak to skratka pridas povodnou hash.fciou.
Delete:
Opacny postup.
Cele to ber ako hint - mozno som to blbo pochopil a naviac cele preskocil :/ ....snad to dnes nedostanem.
Vela stastia na skuske!!!
PS: vyhodu to ma taku ze mozes neahodne vstupne data "znahodnit" dobrou hash fciou.
predstav si ze mas:
f1(x) = x mod 10
vstupne data 10, 20, 30, 40, 50, 60, 70,...
po tomto usudis ze by bola dobra
f2(x)=x/10 mod 10
vstupne data 10, 20, 30, 40, 50, 60, 70, 11, 12, 13, 14
a skratka to zas zmenis na f3....
MOTTO-1: Nieje dôležité vedieť ale pochopiť!!!
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.
MOTTO-2: Neuč sa!!! Život ťa naučí. Mňa naučil, že sa mám učiť.