|
hash algoritam potreban
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) } |
Može li ovako - napravi jednu funkciju GetHash(a,b) i onda je pozivaj:
hash = a < b ? GetHash(a,b) : GetHash(b,a) :D 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. |
^ fino
|
Hm, a zašto ne bi koristio:
Kôd:
def my_hash(a, b): |
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..
|
Š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. |
Kolizija ključeva? :)
|
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 :1023: |
Citat:
|
| Vreme je GMT +2. Trenutno vreme je 04:21. |
Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.