Почему функция удаления из хэш-таблицы крашит програму?

Question

У меня есть задание реализовать хеш-таблицу названий городов. Вот один метод который удаляет из таблицы один елемент:

void Dictionary::DELETE_W(int key) {
    int hs = Hash_Func(key);
    while (this->elements[hs] != NULL){
        if (this->elements[hs]->get_key() == key) {
            break;
        }
        hs = Hash_Func(hs + 1);
    }
    std::cout << hs << std::endl;
    if (this->elements[hs] == NULL) {
        std::cout << "Елемент за ключем : " << key << " не существует..." << std::endl;
    }
    else{
        delete this->elements[hs];
    }
    std::cout << " Елемент удален" << std::endl;
}

Вот реализация хеш-функции:

int Dictionary::Hash_Func(int key) {
    return key % this->SIZE;
}

Но почему-то функция удаления крашит програму. Подскажите пожалуйста что не так?

Вот полный код:

Файл Dictionary.h:

#pragma once
#include <iostream>
#include "Cell.h"

class Dictionary {
private:
    Cell** elements;
    const int SIZE = 2;
public:
    Dictionary();
    ~Dictionary();

    int get_SIZE() { return this->SIZE; }

    int Hash_Func(int);
    void INSERT(int, std::string);
    std::string MEMBER(int);
    void DELETE_W(int);
    void CLEAR();
    void PRINT();
};

Dictionary::Dictionary() {
    elements = new Cell * [this->SIZE];
    for (int i = 0; i < this->SIZE; i++) {
        elements[i] = NULL;
    }
}

Dictionary::~Dictionary() {
    for (int i = 0; i < this->SIZE; i++) {
        delete elements[i];
    }
    delete[] elements;
}

int Dictionary::Hash_Func(int key) {
    return key % this->SIZE;
}

void Dictionary::INSERT(int key, std::string word) {
    int hs = Hash_Func(key);
    while (this->elements[hs] != NULL && this->elements[hs]->get_key() != key) {
        hs = Hash_Func(hs + 1);
    }
    if (this->elements[hs] != NULL) {
        delete this->elements[hs];
    }
    this->elements[hs] = new Cell(key, word);
}

std::string Dictionary::MEMBER(int key) {
    int hs = Hash_Func(key);
    while (this->elements[hs] != NULL && this->elements[hs]->get_key() != key){
        hs = Hash_Func(hs + 1);
    }
    if (this->elements[hs] == NULL) {
        std::cout << "Елемента за заданим ключем не iснує..." << std::endl;
        return 0;
    }
    else {
        return this->elements[hs]->get_word();
    }
}

void Dictionary::DELETE_W(int key) {
    int hs = Hash_Func(key);
    while (this->elements[hs] != NULL){
        if (this->elements[hs]->get_key() == key) {
            break;
        }
        hs = Hash_Func(hs + 1);
    }
    std::cout << hs << std::endl;
    if (this->elements[hs] == NULL) {
        std::cout << "Елемента за заданим ключем: " << key << " не існує..." << std::endl;
    }
    else{
        delete this->elements[hs];
    }
    std::cout << " Елемент видалено" << std::endl;
}

void Dictionary::CLEAR() {
    for (int i = 0; i < this->SIZE; i++) {
        delete this->elements[i];
        this->elements[i] = nullptr;
    }
}

void Dictionary::PRINT() {
    for (int i = 0; i < this->SIZE; i++){
        std::cout << " [" << i << "]" << " " << this->elements[i]->get_word() << std::endl;
    }
}

Файл Cell.h:

#pragma once

class Cell {
private:
    int key;
    std::string word;
public:
    Cell();
    Cell(int, std::string);
    ~Cell() = default;
    
    int get_key() { return this->key; }
    std::string get_word() { return this->word; }
};

Cell::Cell() {
    key = 0;
    word = "";
}

Cell::Cell(int key, std::string word) {
    this->key = key;
    this->word = word;
}

Answer 1

Это конечно как минимум странная хеш-таблица с точки зрения поведения! При вставке элемента, если хеш (не ключ!) совпадает, то старый элемент удаляется, чтобы вставить новый. Ну да ладно!
Без примера работы трудно сказать точно в чем проблема, но ошибки есть

Если ключ отрицательный то хеш будет или 0 или -1 Hash_Func(-3) == -1 Тогда при попытке адресации элемента массива с отрицательным индексом получится неопределенное поведение

    int hs = Hash_Func(key); // если key==-3, то hs==-1
    while (elements[hs] != NULL) // чтение из elements[-1] - скорее всего краш

Если массив заполнен, а элемента с таким ключем нет в массиве, то цикл будет бесконечным. Например в массиве элементы с ключами 2 и 3, то вызов DELETE_W(4) даст бесконечный цикл.

    while (elements[hs] != NULL) // если 
    {
        if (elements[hs]->get_key() == key) 
            break;
        hs = Hash_Func(hs + 1);
    }

То же самое в функциях MEMBER() и INSERT() - если массив заполнен, но нет элемента с таким ключем, то получается бесконечный цикл

INSERT(int key, std::string word) 
{
    int hs = Hash_Func(key);
    while (this->elements[hs] != NULL && this->elements[hs]->get_key() != key) 
        hs = Hash_Func(hs + 1);

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

    if (this->elements[hs] == NULL) 
    else
        delete this->elements[hs]; // будет попытка повторного освобождения памяти

В функции CLEAR() вообще указатель не проверяется на NULL сразу делается delete

CLEAR() {
    for (int i = 0; i < this->SIZE; i++)
        delete this->elements[i];

Может и ещё ошибки есть - дальше не стал смотреть.

БЛОГ НА HUSL

Почему функция удаления из хэш-таблицы крашит програму?

Ответы (1 шт):