# double hashing not filling 100% of big tables

• 04-11-2009
simpatico_qa
double hashing not filling 100% of big tables
Hello,

I'm having some problems with filling a hash table using the following hash functions:

Code:

```int h1(int k, int m){         int h1 =  mod(k,m);         return h1; } int h2(int k, int m){         int h2probe = mod(2*k+1,m);         return h2probe; } int h(int k,int i, int m){         int h1a = h1(k,m);         int h2a = h2(k,m);         int h = mod(h1a + i*h2a, m);         return h; int insert(int H[], int m, int key){         if (isFull(H, m) == -1) return -1;         int i=0;         int key2 = key*2+1;         if(key2 < 0) key /= 2;         int probe = h(key,i,m);                        // 0 <= probe < m;         while (H[probe] != 0)                        // we know there is room, so will terminate if the hashing function is able to map at each spot.                 probe = h(key,++i,m);         H[probe] = key;         return probe; }```

The problem is that when I try to fill an 18 slots table slot 14 never gets a change to be filled. Similar deadlocks occur with other sizes. While a table of 10 elements fills correctly. The literature found about double hashing seem not to answer my problem. The insertion code simply tries again increasing i. However deadlocks occur. Any suggestions on how to solve it still using double hashing and the h functions specified above(so only play with the insertion method). Mod(a,m) return the module > 0.
• 04-12-2009
simpatico_qa
no hashing experts over here?
• 04-12-2009
matsp
You may want to check that your two hash functions generate an equal number of odd and even hashes - if odd ones are more common, then you may find that you are more often than not ending up with an even number in your sum.

--
Mats
• 04-12-2009
simpatico_qa
hmm... I'm not clear on the problem (of even and odd numbers) and even more on how to achieve it in code inside the insertion function. I wonder if you could be more specific.
• 04-12-2009
matsp
If two numbers are odd, the sum of them is always even. Certainly h2() is guaranteed to ALWAYS be odd. Key2 is also guaranteed to be odd in your calculation (unless it overflows into negative range - I don't know what your key value range is, so I can't say if it happens to be overflowing from time to time).

So if your hashes in each hash function more often generates an odd number than even, you have more likelihood of getting an even number than an odd one.

Since 18 is not an odd number, it is impossible that mod 18 will give an odd result.

You could perhaps produce a table of all the results for your hash functions (seeing as there isn't a huge number of them), and the resulting combined hash.

--
Mats
• 04-12-2009
simpatico_qa
Code:

``` int key2 = key*2+1;         if(key2 < 0) key /= 2;```
This is relevant only for overflow (to guarantee that the key is always positive.

h2() produces an odd number, but h1() should produce an even number. The case are that the first will be an even number:
h1 + 0h2
the second an odd h1 + h2 .
the 3rd an even h1 + 2h2
and so on ...

I don't see why mod 18 should not return odd numbers. Given 19 it should return the odd 1 for example.
• 04-12-2009
matsp
18 comes from "I try to fill an 18 slots".

--
Mats
• 04-12-2009
simpatico_qa
I'm still not clear. 18 is an upper bound for the mod, so using it how I do should guarantee values in the range up to 18. However 14 doesn't get it since I reach the deadlock situation of h1 returning 8 and h2 4 and counting down. The problem as I said doesn't occur with all table sizes, and in other cases the deadlock occurs before 14 being the last unfilled element in the table. So what can I do to fix the code to always fill all the slots?
• 04-12-2009
matsp
So, have you analyzed what your hash values are for each key. Adding something like:
Code:

`printf("key=%d, h1 = %d, %h2=%d, h=%d\n", k, h1a, h2a, h2);`
inside your h function will (I'm guessing, at least) show what is going on, and what values you are getting out of it.

I'm still pretty sure that the problem is that you are not getting enough variation in your hash keys.

--
Mats
• 04-12-2009
simpatico_qa
I've already seen the problem and the values through the debugger. I found out: 14 doesn't get it since I reach the deadlock situation of h1 returning 8 and h2 4 and counting down. The problem as I said doesn't occur with all table sizes, and in other cases the deadlock occurs before 14 being the last unfilled element in the table. So what can I do to fix the code to always fill all the slots?

Now the problem is that how can I tweak the code to make it go over that 12 when it reaches it, not modifying h1 and h2.
• 04-13-2009
quzah
Did you really just ask how you can make your hashing work right without changing your hashing functions? :confused: Run your hash in a loop, feeding it consecutive incrementing numbers, filling an array of X size, where each time it hits that spot, you increment the value in the array. If you find some cells ending up blank, then you need to tune your hashing functions.

You either change the number of buckets, or you change the way you're filling them. That's how hashing works.

Quzah.