Welcome to Dream.In.Code
Getting C++ Help is Easy!

Join 136,150 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,092 people online right now. Registration is fast and FREE... Join Now!




Hash function

 
Reply to this topicStart new topic

Hash function

stl_cards
11 Apr, 2007 - 05:54 PM
Post #1

New D.I.C Head
*

Joined: 26 Mar, 2007
Posts: 5


My Contributions
I need to come up with a hash function with a minimal amount of collisions. I have been given 10 numbers and have to have 23 spaces to store them. The numbers are: 774, 843, 889, 912, 958, 16, 85, 200, 315, 407. The best thing I have come up with is Num / 4 %(MOD) 23
User is offlineProfile CardPM
+Quote Post

NickDMax
RE: Hash Function
12 Apr, 2007 - 05:41 AM
Post #2

2B||!2B
Group Icon

Joined: 18 Feb, 2007
Posts: 2,858



Thanked: 49 times
Dream Kudos: 550
My Contributions
Well you could just nomalize and use: hash = (double)Num/Max * 23;
CODE
<mathematica code>
hash[x_] := Floor[(x/1000)*23]
hash[{774, 843, 889, 912, 958, 16, 85, 200, 315, 407}]
-> {17, 19, 20, 20, 22, 0, 1, 4, 7, 9}
which only has 20 twice.

and

hash[x_] := Floor[(x/1024)*23]
hash[{774, 843, 889, 912, 958, 16, 85, 200, 315, 407}]
-> {17, 18, 19, 20, 21, 0, 1, 4, 7, 9}
each item has a unique hash.

When i use your version
hash[x_]:=Mod[Floor[x/4],23]
hash[{774, 843, 889, 912, 958, 16, 85, 200, 315, 407}]
-> {9, 3, 15, 21, 9, 4, 21, 4, 9, 9}
which has a problem with 9's and 21's... however
hash[x_]:=Mod[Floor[x/45],23]
hash[{774, 843, 889, 912, 958, 16, 85, 200, 315, 407}]
-> {17, 18, 19, 20, 21, 0, 1, 4, 7, 9}
(coincidance... I think not!!!)
</mathematica code>


Well I will leave you to figure out what way to use and why.
User is offlineProfile CardPM
+Quote Post

Reply to this topicStart new topic
Time is now: 12/1/08 11:03PM

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month