Функция двойного хеширования, возвращающая неправильное значение
Я создаю двойную карту хеширования, но функция удаления не работает после вставки. Я следую тому же формату для увеличения индекса, но он не попадает в правильный индекс.
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,
Почему он возвращает неправильное значение?
Решение
Это связано с тем, что функция hash2 возвращает значение 2 для ключа 10. Для hash2 (10) hash2 может быть показан как.
return 10 % (10-1) + 1
это в свою очередь по приоритету оператора оценивается до значения 2 как.
return (10 %(10-1))+1
и в функции вставки, когда происходит столкновение, вы добавляете значение hash2 к значению hash, чтобы получить новый индекс, который оценивается как.
h= f + ( P * f2 ) % M
h= 0 + (1 * 2 ) % 10 \\ this evaluates to 2.
вот почему вы получаете новый индекс как 2.
Изменить: Код имеет несколько проблем с приоритетом оператора.
Первый
h = f + (p * f2)% M; // Обернуть массив при необходимости
Это не оборачивается вокруг массива. так как% имеет больший приоритет, чем +. f имеет значение в диапазоне [0-M-1], а (p * f2)% M имеет значения в диапазоне [0-M-1]. Таким образом, вышеприведенное выражение может вычислять значение в диапазоне [0-2 * M-2]. Это верно и для других таких выражений в коде. Это причина, по которой некоторые ключи могут отсутствовать в хэш-таблице.
Другие решения