我正在创建一个双哈希映射,但删除功能在插入后不起作用。我遵循相同的格式来增加索引,但它只是没有达到正确的索引。
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;
}
}
这是我的主要内容:
RHHM bh(10);
bh.insert(0, 'A');
bh.insert(10, 'B');
bh.insert(20, 'C');
bh.print(std::cout);
输出:
<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>
如您所见,第一个索引散列为0
. 由于10
密钥与 冲突0
,双散列(10
)应该散列到1
,但它的散列到2
。为什么它返回错误的值?