Удаление из HashTable C++

Question

Как удалить из массива на основе hashtable? Мне нужно подготовить для удаления нескольких символов из моего стола. Если я сбрасываю то, что хочу удалить в массиве символов фиксированного размера, как бы найти те, которые я «потенциально» удалю?

bool hashmap::get(char const * const symbol, stock& s) const 
{ 
    int hashVal = this->hashStr(symbol); 
    int initialHash = -1; 

    while (hashTable[hashVal].m_symbol != NULL) 
    { // try to find a match for the stock associated with the symbol. 

     if (initialHash == -1) 
     { 
      initialHash = hashVal; 
     } 
     if (strcmp(hashTable[hashVal].m_symbol, symbol) == 0) 
     { 
      s = &hashTable[hashVal]; 
      return true; 
     } 
     ++hashVal %= maxSize; 
    } 
    if (hashTable[hashVal].m_symbol == NULL || hashVal == initialHash) 
    { 
     return false; 
    } 
    else return true; 
} 

bool hashmap::put(const stock& s, int& usedIndex, int& hashIndex, int& symbolHash) 
{ 
    hashIndex = this->hashStr(s.m_symbol); // Get remainder, Insert at that index. 
    symbolHash = (int&)s.m_symbol; 
    usedIndex = hashIndex; 

    while (hashTable[hashIndex].m_symbol != NULL) 
    { 
     ++usedIndex %= maxSize; // if necessary wrap index around 
     if (hashTable[usedIndex].m_symbol == NULL) 
     { 
      hashTable[usedIndex] = s; 
      return true; 
     } 
     else if (strcmp(hashTable[usedIndex].m_symbol , s.m_symbol) == 0) 
     { 
      return false; // prevent duplicate entry 
     } 
    } 
    hashTable[hashIndex] = s; // insert if no collision 
    return true; 
} 

bool hashmap::remove(char const * const symbol) 
{ 
    int hashVal = this->hashStr(symbol); 
    int initialHash = -1; 

    while (hashTable[hashVal].m_symbol != NULL ) 
    { 
     if (initialHash == -1) 
     { 
      initialHash = hashVal; 
     } 
     if (strcmp(hashTable[hashVal].m_symbol, symbol) == 0) 
     { 
      hashTable[hashVal].m_symbol = NULL; 
      return true; 
     } 
     ++hashVal %= maxSize; // wrap around if needed 
    } // go to the next cell if not found 

    if (hashVal != initialHash && hashTable[hashVal].m_symbol != NULL) 
    { 
     return true; 
    } 
    return false; 
} 

int hashmap::hashStr(char const * const str) 
{ 
    size_t length = strlen(str); 
    int hash = 0; 
    for (unsigned i = 0; i < length; i++) 
    { 
     hash = 31 * hash + str[i]; 
    } 
    return hash % maxSize; 
} 

Answer 1

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

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

Редактировать: Удаление сложнее, чем может быть сразу очевидно. Например, предположим, что вы хотите удалить что-то хэшированное в позицию N в таблице, но вы найдете его в позиции N + 3. Может быть, однако, что-то в позиции N + 4, которая (например,) могла первоначально хешировать в положение N-1. Итак, если вы настаиваете на попытке удалить из таблицы, как это, вы должны пройти от того места, где это хэшируется до всего следующего пустого места в таблице, и повторить хэш каждого из этих элементов, чтобы выяснить, откуда он изначально пришел, и заверить, что если вы удалите что-то, каждая из этих цепочек останется неповрежденной от своей исходной хэш-точки, где бы она ни была.

Это есть возможно сделать это произведение - но это нет простой. Учитывая, насколько плохо работает линейный зондирование, это просто не стоит!