infoarena

de 2 zile tot caut (pe net) o functie hash ce intoarce valori pana in 2^22 si care sa aiba o probabilitate cat mai mica de a produce coliziuni. ma poate ajuta cineva?

Cauta despre Bernstein Hash.

Din ce am constatat eu pentru siruri merge foarte bine rabin-karp, adica consideri sirul un numar intr-o baza si il calculezi modulo cateva numere prime mari (2 numere prime sunt arhisuficiente si nu mai trebuie sa tratezi coliziunile). Apoi daca vrei sa faci toate operatiile (inserare, cautare si stergere) pe numere intregi cred ca merge foarte bine "double-hashing" (tehnica care apare si in articolul de pe infoarena), aloci static la inceput 2 tabele de hash si bagi elementul curent in tabelul unde ai cat mai putine elemente ce au cheia egala cu cheia elementului curent (functia de hash tot f(x)=x%mod). Nustiu ce sa spun despre hash`uri pe numere reale, nu am incercat niciodata.

o functie buna de hash pe care o stiu (pentru numere intregi):

iei un numar impar mare random la inceput si functia de hash pentru x e cam asa:
(x * nr) >> (32 - nrb) (unde nrb e cati biti semnificativi vrei sa pastrezi (in cazul tau 22))
nu te intereseaza daca da overflow, asta e :)

e mult mai rapida in cazul in care accesezi de multe ori functia de hash pentru ca nu are modul (%) care ia mult timp.
cu ajutorul ei am reusit sa fac problema secv5 sa intre in timp  :P

Nu merge si mai bine daca in loc de impar iei prim ? (adica sa ai mai putine coliziuni)
De obicei numerele prime fac magie pe hash-urile astea :)

habar n-am daca merge mai bine  :D

Functia asta e aia pe care ne-a zis-o Mircea (si pe care eu nu am tinut-o minte)?

multumesc mult pentru sfaturi.

Adi: de obicei eu folosesc trei numere prime pentru hashul acela, nu doua. probabilitatea de coliziune fiind ceva 1/(p1*p2*p3) (poate gresesc?). problema era sa pot cauta in O(1) o informatie din hash.

Cosmin: eu am gasit pe net o functie de tipul celei care ai zis-o tu:

presupunand ca vreau sa comprim un sir de caractere 's':


fie, aici se poate introduce si o siftare pe biti ca sa nu sara de 2^22.

am incercat acest lucru la problema Ograzi, dar iau doar 90. sa aiba multe coliziuni functia mea?

Incearca sa tratezi cumva si coliziunile. In articolul de pe site sunt prezentate mai multe solutii pentru asta.

n-am vazut ca exista articol pe site  :-'

pana la urma nu m-am lamurit. care e mai buna? cu nr impar sau cu nr prim?

Cum majoritatea numerelor prime sunt si impare ... nu risti nimic luand unul prim :)

dap  :P