DevProTalk

DevProTalk (http://www.devprotalk.com/index.php)
-   Programiranje (http://www.devprotalk.com/forumdisplay.php?f=23)
-   -   hash algoritam potreban (http://www.devprotalk.com/showthread.php?t=6040)

ivanhoe 22. 08. 2008. 18:12

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) }

degojs 22. 08. 2008. 18:46

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.

robi-bobi 22. 08. 2008. 19:09

^ fino

Petar Marić 22. 08. 2008. 19:13

Hm, a zašto ne bi koristio:
Kôd:

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


ivanhoe 22. 08. 2008. 19:19

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 22. 08. 2008. 19:23

Š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ć 22. 08. 2008. 21:43

Kolizija ključeva? :)

degojs 22. 08. 2008. 23:37

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:

Petar Marić 23. 08. 2008. 09:11

Citat:

Originalno napisao degojs (Napišite 59117)
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 :1038:


Vreme je GMT +2. Trenutno vreme je 00:49.

Powered by vBulletin® Verzija 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright © DevProTalk. All Rights Reserved.

Mišljenja, saveti, izjave, ponude ili druge informacije ili sadržaji nastali na Sajtu su vlasništvo onoga ko ih je kreirao, a ne DevProTalk.com, tako da ne morate da se oslanjate na njih.
Autori poruka su jedini odgovorni za ovakve sadržaje. DevProTalk.com ne garantuje tačnost, kompletnost ili upotrebnu vrednost informacija, stavova, saveta ili datih izjava. Ne postoje uslovi pod kojima bi mi bili odgovorni za štetu ili gubitak koji je posledica bilo čijeg oslanjanja na nepouzdane informacije, ili bilo kakve informacije nastale kroz komunikaciju između registrovanih članova.
Web sajt može sadržavati linkove na druge web sajtove na Internetu ili neke druge sadržaje. Ne kontrolišemo niti podržavamo te druge web sajtove, niti smo pregledali bilo kakve sadržaje na takvim sajtovima. Mi nećemo biti odgovorni za legalnost, tačnost ili prikladnost bilo kog sadržaja, oglasa, proizvoda, usluga ili informacije lociranim na ili distribuiranih kroz druge web sajtove, niti za bilo kakvu štetu nastalu kao posledica takvih informacija. DevProTalk.com drži i čuva druga prava vlasništva na web sajtu. Web sajt sadrže materijale zaštićene copyright-om, zaštitne znakove i druge informacije o pravu vlasništva ili softver. Članovi mogu poslatu informacije zaštićene pravima vlasništva njihovih nosilaca i ona ostaju zaštićena bez obzira da li su oni koji prenose te informacije to naveli ili ne. Osim informacija koje su u javnom vlasništvu ili za koje dobijete dozvolu, nemate pravo da kopirate, modifikujete ili na bilo koji način menjate, objavljujete, prenosite, distribuirate, izvršavate, prikazujete ili prodajte bilo koju informaciju zaštićenu pravima vlasništva. Slanjem informacija ili sadržaja na bilo koji deo DevProTalk.com, Vi automatski dozvoljavate i predstavljate garanciju da imate pravo da dozvolite DevProTalk.com ili članovima DevProTalk.com bespovratnu, kontinualnu, neograničenu, globalnu dozvolu da koriste, kopiraju, izvršavaju, prikazuju i distribuiraju takve informacije i sadržaje i da iz takvih sadžaja koriste bilo koji deo u bilo koje svrhe, kao i pravo i dozvolu da koriste gore navedene sadržaje. Svi zaštitni znakovi (trademarks), logotipi, oznake usluga, firme ili imena proizvoda koji se pominju na ovom web sajtu su vlasništvo kojim raspolažu njihovi vlasnici.