含20主桶10溢出桶的哈希表实现Access Violation问题求助

嘿，我完全理解你隔了一年捡C++的痛苦——指针和内存管理分分钟让人头大！Access Violation一般都是非法访问内存导致的，比如用了未初始化的指针、越界访问数组，或者溢出桶的指针没正确处理。咱们一步步来把这个哈希表弄对。

第一步：先把类结构理清楚（修正初始化问题） #

你提到有类声明，那先确保每个桶的结构是正确的。首先，槽（Slot）应该是存储key和data的结构体，然后桶（Bucket）包含槽数组、计数器、溢出指针。咱们先把基础结构写对：

#include <string>
#include <cstdlib> // 用于abs()
using namespace std;

// 定义槽结构：存储key和data，加占用标记避免空槽混淆
struct Slot {
    string key;
    string data;
    bool is_occupied = false; // 默认未占用，避免野值
};

// 定义桶结构：3个槽、已用槽计数器、溢出桶指针
struct Bucket {
    Slot slots[3];
    int count = 0;
    Bucket* overflow = nullptr; // 初始化为空指针，杜绝野指针！
};

// 哈希表类
class HashTable {
private:
    static const int MAIN_BUCKETS = 20;
    static const int OVERFLOW_BUCKETS = 10;
    Bucket main_buckets[MAIN_BUCKETS];
    Bucket overflow_buckets[OVERFLOW_BUCKETS];
    int next_overflow_idx = 0; // 记录下一个可用的溢出桶索引

    // 简单字符串哈希函数：转成整数后取模主桶数量
    int hash(const string& key) {
        int hash_val = 0;
        for (char c : key) {
            hash_val = hash_val * 31 + c; // 常用的字符串哈希计算方式
        }
        return abs(hash_val) % MAIN_BUCKETS; // 取正后取模，避免负数索引
    }

    // 获取一个可用的溢出桶
    Bucket* get_free_overflow_bucket() {
        if (next_overflow_idx >= OVERFLOW_BUCKETS) {
            // 溢出桶用完了，这里可以抛异常或返回空指针提示错误
            return nullptr;
        }
        return &overflow_buckets[next_overflow_idx++];
    }

public:
    HashTable() {
        // 手动初始化所有桶的计数器和溢出指针（兼容旧C++标准）
        for (int i = 0; i < MAIN_BUCKETS; i++) {
            main_buckets[i].count = 0;
            main_buckets[i].overflow = nullptr;
        }
        for (int i = 0; i < OVERFLOW_BUCKETS; i++) {
            overflow_buckets[i].count = 0;
            overflow_buckets[i].overflow = nullptr;
        }
        next_overflow_idx = 0;
    }

    // 插入key和data的核心函数
    bool insert(const string& key, const string& data) {
        int target_main_idx = hash(key);
        Bucket* current_bucket = &main_buckets[target_main_idx];

        // 先尝试在当前桶的空槽插入
        for (int i = 0; i < 3; i++) {
            if (!current_bucket->slots[i].is_occupied) {
                current_bucket->slots[i].key = key;
                current_bucket->slots[i].data = data;
                current_bucket->slots[i].is_occupied = true;
                current_bucket->count++;
                return true;
            }
        }

        // 当前桶满了，遍历溢出桶链找空槽
        while (current_bucket->overflow != nullptr) {
            current_bucket = current_bucket->overflow;
            for (int i = 0; i < 3; i++) {
                if (!current_bucket->slots[i].is_occupied) {
                    current_bucket->slots[i].key = key;
                    current_bucket->slots[i].data = data;
                    current_bucket->slots[i].is_occupied = true;
                    current_bucket->count++;
                    return true;
                }
            }
        }

        // 溢出链也满了，分配新的溢出桶
        Bucket* new_overflow = get_free_overflow_bucket();
        if (new_overflow == nullptr) {
            // 没有可用溢出桶，插入失败
            return false;
        }
        // 在新溢出桶的第一个槽插入数据
        new_overflow->slots[0].key = key;
        new_overflow->slots[0].data = data;
        new_overflow->slots[0].is_occupied = true;
        new_overflow->count++;
        // 把当前桶的溢出指针指向新桶
        current_bucket->overflow = new_overflow;
        return true;
    }

    // 根据key查找data的函数
    string find(const string& key) {
        int target_main_idx = hash(key);
        Bucket* current_bucket = &main_buckets[target_main_idx];

        while (current_bucket != nullptr) {
            for (int i = 0; i < 3; i++) {
                if (current_bucket->slots[i].is_occupied && current_bucket->slots[i].key == key) {
                    return current_bucket->slots[i].data;
                }
            }
            current_bucket = current_bucket->overflow;
        }
        // 未找到返回空字符串，也可以用自定义标记
        return "";
    }
};

第二步：排查你之前Access Violation的常见原因 #

你遇到的错误大概率是这几个问题：

• 野指针：溢出指针overflow没初始化为nullptr，导致访问随机内存地址。上面的代码里所有指针都默认/手动初始化为空，彻底避免这个问题。
• 数组越界：比如访问slots[3]（槽索引是0-2），或者主桶/溢出桶的索引超过20/10的范围。哈希函数里的abs()就是为了避免负数索引导致的越界。
• 溢出桶分配逻辑混乱：比如重复分配同一个溢出桶，或者溢出桶用完了还继续访问超出数组范围的内存。next_overflow_idx变量就是用来追踪可用溢出桶的。

第三步：测试代码的小技巧 #

可以写个简单的main函数验证功能：

#include <iostream>
int main() {
    HashTable my_table;
    // 插入基础数据
    my_table.insert("apple", "red round fruit");
    my_table.insert("banana", "long yellow fruit");
    // 插入足够多数据触发溢出桶
    for (int i = 0; i < 65; i++) {
        my_table.insert("item_" + to_string(i), "content_" + to_string(i));
    }
    // 测试查找
    cout << "apple: " << my_table.find("apple") << endl;
    cout << "item_60: " << my_table.find("item_60") << endl;
    cout << "nonexistent: " << my_table.find("nonexistent") << endl;
    return 0;
}

额外提示 #

• 如果你的原代码用了new动态分配内存，一定要在析构函数里用delete释放，避免内存泄漏。上面的代码用静态数组，不用手动管理内存，更适合新手。
• 可以扩展删除功能：把槽的is_occupied设为false即可，不用清空字符串，这样后续插入可以复用空槽。

内容的提问来源于stack exchange，提问作者Thomas Shaw