Printable View
what would be the simplest easy-to-calculate non-collision hash function for mapping the following between 0-10 inclusive:
224562,137456,214562
140145,214576,162145
144467,199645,234534
i tried digit-extraction method for 2,4,5,6 position but i get collision. I am workin gon other methods, meanwhile if someone finds out please let me know asap...
thanks
You will always have collision. You want to pick a hash function that will give a reasonable distributsion of keys. For integers, the most common is "key % <prime #>" - this implies that the size of your hash table will be a prime #.
You will have collisions so you must choose a collision resolution technique. The most common is seperate chaining - using this technique, each entry in the hash table is a linked list - when there is a collision, the key is simply added to the list.
key % 11 does well will your set of data - but there is still one collision.
gg
yes, i am getting collision with other digits too when using digit-extration , but i was told that there is a non-collision solution. I am working on the folding method to see if it works.
Well, if your homework is to find a hash function for the given data, then thats different - it's also your homework.
The solution will most likely be a hashing technique discussed in class or in your book. Nothing wrong with getting creative though :)
gg
hey Codeplug, i was not saying that you were wrong. I was just letting you know that i am working on the same thing and still not getting non-collision answer. I appreciate you replying :) thanks
I may be pointing out something obvious, but since your data set is from 0-10 then why not just create a table large enough to hold them and just use each number as the index? Am I missing something? Also, how do you handle duplicate values?
It's an asignment to come up with a hash function that results in no collisions with the given the set of keys.
iori, I didn't think you were saying I was wrong - btw :)
Post the solution when you find it - I'm curious.
If you've exhausted all the hashing techniques you know of, I think your best bet is to look for something in this form:
h(key) = f(key) % 11
You just have to find a "f(key)" that result in h(key) having no collisions.
gg
hey guys,
to the ones curious for the solutions i saw in the class:
one of the solutions to this is using this formula:
y=(3x-1) mod 11 where x is the given number
the second solution one was a lil longer:
say for the number 224562
we divide the number into 3 parts like this 22,45,62
now we swap the posiition of the 3 parts : 22,54,26
we add the numbers: 22+54+26 giving 102
answer in step#4 mod 21 : 102 mod 21=18
answer in step#5 mod 12: 18 mod 12=6
hmmmmmm.......