带链接的基本哈希 Table

Question

我正在为即将到来的一些采访做准备，所以我正在重写一个基本的散列 table，并从头开始进行链接。我收到以下错误：

Exception thrown: read access violation.
hashTable was 0x1110116.

在这一行：

auto entry = hashTable[hashValue];

在插入函数中。我检查并重新检查了我的代码，但我看不出问题出在哪里。这是完整的代码：

#include <iostream>

const int size = 128;

struct Node {
    int key;
    int value;
    Node* next = nullptr;

    Node(const int& x, const int& y, Node* next = nullptr) : 
        key(x),
        value(y),
        next(next) {}
};
Node** hashTable = nullptr;


void print() {
    Node* temp;
    for (int i = 0; i < size; i++) {
        temp = hashTable[i];
        std::cout << "Key: " << temp->key << " Value: " << temp->value << " ";
    }
    std::cout << "\n";
}

int hash(int key) { return key % size; }

void insert(int key, int value) {
    int hashValue = hash(key);
    Node* previous = nullptr;
    auto entry = hashTable[hashValue];

    while (entry != nullptr) {
        previous = entry;
        entry = entry->next;
    }

    if (entry == nullptr) {
        entry = new Node(key, value);
        if (previous = nullptr) {
            hashTable[hashValue] = entry;
        }
        else {
            previous->next = entry;
        }
    }
    else {
        entry->value = value;
    }
}

void remove(int key) {
    int hashValue = hash(key);
    Node* previous = nullptr;
    auto entry = hashTable[hashValue];

    while (entry != nullptr && entry->key != key) {
        previous = entry;
        entry = entry->next;
    }

    if (entry == nullptr) {
        std::cout << "Key not found" << "\n";
        return;
    }
    else {
        if (previous == nullptr) {
            hashTable[hashValue] = entry->next;
        }
        else {
            previous->next = entry->next;
        }
        delete entry;
    }
}

void search(int key) {
    bool flag = false;
    int hashValue = hash(key);
    auto entry = hashTable[hashValue];

    while (entry != nullptr) {
        if (entry->key == key) {
            std::cout << entry->value << " ";
            flag = true;
        }
        entry = entry->next;
    }
    if (!flag) std::cout << "No key found" << "\n";
}


int main() {

    insert(1, 1);
    insert(2, 2);
    insert(3, 3);
    insert(4, 4);
    print();

    remove(2);
    print();

    search(3);


}

Answer 1

该代码使用了哈希表，但未为其内容分配任何 space。这是未定义的行为，肯定会崩溃。我刚刚制作的是一个长度为'size'的指针数组。您也可以使用新的或更好的但使用矢量。

编译器还警告在本应使用 == 时使用 =。

print() 函数会打印 nullptr 导致崩溃。我添加了一张支票。

你几乎成功了！

#include <iostream>

const int size = 128;

struct Node {
    int key;
    int value;
    Node* next = nullptr;

    Node(const int& x, const int& y, Node* next = nullptr) : 
        key(x),
        value(y),
        next(next) {}
};
Node* hashTable[size]; // give the hash table some space


void print() {
    Node* temp;
    for (int i = 0; i < size; i++) {
        temp = hashTable[i];
        if(temp) // don't try to print of temp == nullptr
            std::cout << "Key: " << temp->key << " Value: " << temp->value << " " << std::endl;
    }
    std::cout << "\n";
}

int hash(int key) { return key % size; }

void insert(int key, int value) {
    int hashValue = hash(key);
    Node* previous = nullptr;
    auto entry = hashTable[hashValue];

    while (entry != nullptr) {
        previous = entry;
        entry = entry->next;
    }

    if (entry == nullptr) {
        entry = new Node(key, value);
        if (previous == nullptr) {
            hashTable[hashValue] = entry;
        }
        else {
            previous->next = entry;
        }
    }
    else {
        entry->value = value;
    }
}

void remove(int key) {
    int hashValue = hash(key);
    Node* previous = nullptr;
    auto entry = hashTable[hashValue];

    while (entry != nullptr && entry->key != key) {
        previous = entry;
        entry = entry->next;
    }

    if (entry == nullptr) {
        std::cout << "Key not found" << "\n";
        return;
    }
    else {
        if (previous == nullptr) {
            hashTable[hashValue] = entry->next;
        }
        else {
            previous->next = entry->next;
        }
        delete entry;
    }
}

void search(int key) {
    bool flag = false;
    int hashValue = hash(key);
    auto entry = hashTable[hashValue];

    while (entry != nullptr) {
        if (entry->key == key) {
            std::cout << entry->value << " ";
            flag = true;
        }
        entry = entry->next;
    }
    if (!flag) std::cout << "No key found" << "\n";
}


int main() {

    insert(1, 1);
    insert(2, 2);
    insert(3, 3);
    insert(4, 4);
    print();

    remove(2);
    print();

    search(3);


}

带链接的基本哈希 Table

Basic Hash Table with Chaining

c++

hashtable