John Calderaio John Calderaio - 9 days ago 4
C++ Question

Double hashing function returning wrong value

I am creating a double hashing map, but the remove function does not work after inserting. I follow the same format for increasing the index, but it just does not hit the correct index.

class RHHM {
unsigned int hash2( int key ) {

return key % (M-1) + 1;

}

//Private variables

hashNode ** map; //Backing array
unsigned int M; //Capacity of array

//If index that key hashes to is empty, insert. Else, replace value at hashed index.
int insert( int key, char value ) {

int f = hash( key );
int f2 = hash2 ( key );
int p = 0;
int h = f + (p * f2) % M;

while( map[h] != NULL ) {

if( p == M )
return -1 * p;

if( map[h]->key == key ) {
map[h]->value = value;
return p;
}
else {
++p;
h = f + (p * f2) % M;
}
}

map[h] = new hashNode( key, value );
return p;
}

int remove( int key, char &value) {

int f = hash( key );
int f2 = hash2 ( key );
int p = 0; //Keeps track of how many indexes have been checked
int h = f + (p * f2) % M;

while( map[h] != NULL ) {

if( p == M ) //If item is not found in table, return false
return -1 * p;

if( key == map[h]->key ) //If key is found, break out of loop
break;
else {
++p;
h = f + (p * f2) % M; //Wrap around array if necessary
}

}

if( map[h] == NULL ) //If end of cluster reached, return false
return -1 * p;

value = map[h]->value; //Stores the value of the item to be deleted
delete map[h]; //Delete the item the user specified
map[h] = NULL;
++p;
h = f + (p * f2) % M;
for( ; map[h] != NULL; h = f + (p * f2) % M) { //While still in the cluster, remove and reinsert all items
int tempKey = map[h]->key;
char tempValue = map[h]->value;
delete map[h];
map[h] = NULL;
insert(tempKey, tempValue);
++p;
}
return p;

}

}


And here is my main:

RHHM bh(10);
bh.insert(0, 'A');
bh.insert(10, 'B');
bh.insert(20, 'C');
bh.print(std::cout);


Output:

<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>


As you can see, the first index hashes to
0
. Since the
10
key collides with
0
, double hash (
10
) should hash to
1
, but its hashing to
2
.
Why is it returning the wrong value?

Answer

This is because the hash2 function returns a value 2 for the key 10.For hash2(10), hash2 can be shown as.

return 10 % (10-1) + 1

this in turn by operator precedence evaluated to the value 2 as.

return (10 %(10-1))+1

and in the insert function when there is a collision you add the hash2 value to the hash value to get the new index which evaluates as.

h= f + ( P * f2 ) % M
h= 0 + (1 * 2 ) % 10 \\ this evaluates to 2.

thats why you get the new index as 2.

Edit: The code has quiet a few issues with operator precedence. First h = f + (p * f2) % M; //Wrap around array if necessary

This doesn't wrap around the array. since % has more precedence than +. f has value in the range[0-M-1] and the (p *f2) % M has values in the range [0-M-1]. So the above expression may evaluates to a value in the range [0-2*M-2]. This holds true for other such expressions in the code. This is a reason some of the key may be missing in hash table.

Comments