Двойная функция хэширования возвращает неправильное значение

Question

Я создаю карту двойного хэширования, но функция удаления не работает после вставки. Я использую тот же формат для увеличения индекса, но он просто не попадает в правильный индекс.

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. Почему он возвращает неправильное значение?

Answer 1

Это потому, что функция hash2 возвращает значение 2 для ключа 10.For hash2 (10), hash2 может быть показан как.

return 10 % (10-1) + 1 

это, в свою очередь, приоритетом оператора, оцененным значением 2 как.

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

и в функции вставки, когда есть столкновение вы добавляете значение hash2 к хэш-значению, чтобы получить новый индекс, который оценивает, как.

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

вот почему вы получите новый индекс как 2.

Edit: Код имеет тихие несколько проблем с оператором старшинством. Первый h = f + (p * f2)% M; // Оберните массив, если необходимо

Это не обертывает массив. поскольку% имеет больше приоритета, чем +. f имеет значение в диапазоне [0-M-1], а (p * f2)% M имеет значения в диапазоне [0-M-1]. Таким образом, приведенное выше выражение может оценивать значение в диапазоне [0-2 * M-2]. Это справедливо для других подобных выражений в коде. По этой причине некоторые из ключей могут отсутствовать в хэш-таблице.