Univerzalni hashovani?

[Necroman]

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

[MIKI]

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....