hash algoritam potreban

[ivanhoe]

treba mi neka hash funkcija za koji bi vazilo da je H(A,B) = H(B,A), jel postoji tako nesto? Pri tome H() treba da daje (dovoljno) unique brojeve, da nema kolizije kljuceva...

Radi se o tome da imam 2 ID-ja (32-bitni integeri) i da treba da ih povezem u relaciju u bazi, ali mi je redosled ID-ja nebitan (odnosno bitno je da ne zavisi od redosleda).Hocu da izbegnem da moram da stavljam 2 rekorda u bazu, jedan za {A,B} i drugi za {B,A}, nego da imam jedan record oblika { H(A,B) }

[degojs]

Može li ovako - napravi jednu funkciju GetHash(a,b) i onda je pozivaj:

hash = a < b ? GetHash(a,b) : GetHash(b,a)



Odnosno to raspoređivanje "manji pa veći" možeš da radiš unutar same funkcije.. I tako onda možeš da imaš jedan 64-bitni broj koji je uvek isti za ulaz (a,b) i (b,a) i onda računaš hash za njega.

Inače, algoritam za samu hash funkciju bi trebao da nađeš bez većih problema. Ako ne budeš imao uspeha, javi.

[robi-bobi]

^ fino

[Petar Marić]

Hm, a zašto ne bi koristio:

def my_hash(a, b):
    return postojeci_hash(napravi_kljuc(min(a, b), max(a, b)))

[ivanhoe]

da, to sa sortiranjem po redu je i meni palo na pamet, nije lose, jednostavno je, a trebalo bi da sljaka... verovatno cu naprosto da uradim md5 od toga, i to je to..

[degojs]

Što se hash funkcije tiče.. u stvari, tebi ne mora da bude komplikovana, čini mi se.

Ako budeš probavao ovo što sam ja napisao, onda znači kombinuješ ta dva 32-bitna broja u jedan 64-bitni, pa hash onda jednostavno računaš kao ostatak celobrojnog deljenja.

Npr.

hash = x % 11;

(gde je % simbol koji označava celobrojno deljenje).

Što bi obezbedilo da je hash vrednost između 0 i 10. Naravno, ako ti treba više mogućih hash vrednosti, onda samo stavi veći broj. Mada, proveri na netu, ne sećam se sad koje su mane tako jednostavne hash funkcije.

[Petar Marić]

Kolizija ključeva?

[degojs]

Petre, ne može namena funkcije da joj bude mana.

Hash funkcije se koriste da bi podatke grupisale, npr. u svrhu bržeg pronalaženja, pa je onda ne samo normalno, nego traženo da određeni broj podataka ima istu hash vrednost.

Npr. hash funkcija koja korisnike grupiše prema prvom slovu korisničkog imena. I onda kada čovek ukuca username, mi lepo pogledamo koje je prvo slovo (=hash) i pretraživanje vršimo u tabeli gde smo sačuvali samo korisnike čije korisničko ime počinje sa tim slovom (u bazi, za svako slovo imamo po jednu tabelu).

Mana je što podrazumeva da je distribucija elementa u skupu ujednačena, tj. da imamo otpilike jednak broj korisnika za svako (prvo) slovo korisničkog imena (a-z). To bi bila valjda mana i te gore funkcije sa ostatkom celobrojnog deljenja.


Osim ako si hteo da se našališ u smislu da je nešto mnogo 2^64 mogućih vrednosti deliti u 11 grupa, onda se razumemo.. Ili je u pitanju komentar na lapsus gore (prvi put sam dobro napisao "..ostatak celobrojnog deljenja", a drugi put greškom "..označava celobrojno deljenje")..

Anyway.. raspričao sam se

[Petar Marić]

Originalno napisao degojs

Osim ako si hteo da se našališ u smislu da je nešto mnogo 2^64 mogućih vrednosti deliti u 11 grupa, onda se razumemo..

Upravo to