Thread: 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.

no hashing experts over here?

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.

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.

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?

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.