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?
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.