哈希表重哈希崩溃求助：插入达容量一半时程序终止

核心崩溃原因及修复 #

1. 空指针解引用（直接崩溃原因）
   原rehash函数中直接访问oldHashNodes[i]->key，但旧哈希表中存在大量空桶（开放寻址法未使用的位置、链地址法为空的桶），空指针解引用直接导致程序终止。

2. 链地址法数据丢失
   链地址法下每个桶是链表，原代码仅处理链表头节点，未遍历后续节点，会丢失数据。

3. 哈希表容器未正确扩容
   原代码仅将现有HashNodes元素设为NULL，但未扩容到新的容量，导致新桶位置未初始化，后续访问出错。

修复后的rehash函数代码 #

void rehash(){
    int oldMaxHashValues = maxHashValues;
    // 若需质数容量，改用getNextPrimeNum获取下一个质数，优化开放寻址性能
    // maxHashValues = getNextPrimeNum(2 * maxHashValues);
    maxHashValues = 2 * maxHashValues;

    vector<Node*> oldHashNodes = HashNodes;
    // 正确扩容哈希表，新位置初始化为NULL
    HashNodes.resize(maxHashValues, NULL);
    assigned.resize(maxHashValues, false);
    currentHashValues = 0;
    collisions = 0; // 重置碰撞计数（按需调整）

    // 遍历旧哈希表所有桶
    for (int i = 0; i < oldMaxHashValues; i++) {
        Node* node = oldHashNodes[i];
        if (node == NULL) {
            continue;
        }
        // 链地址法遍历整个链表
        if (method == "sep_chain") {
            while (node != NULL) {
                Insert(node->key);
                Node* temp = node;
                node = node->next;
                delete temp; // 释放旧节点，避免内存泄漏
            }
        } else {
            // 开放寻址法每个桶仅一个节点
            Insert(node->key);
            delete node;
        }
    }
}

其他优化建议 #

• 质数容量优化：开放寻址法（双重哈希、自定义探测）中，哈希表容量设为质数能大幅减少碰撞概率，建议将maxHashValues = 2*maxHashValues替换为maxHashValues = getNextPrimeNum(2 * maxHashValues)，需实现getNextPrimeNum函数。
• 重哈希时机调整：将if(currentHashValues== maxHashValues/2)改为if(currentHashValues >= maxHashValues/2)，避免因整数除法或边界情况导致触发不及时。
• 内存泄漏处理：修复后的代码中添加了delete操作释放旧节点，避免内存泄漏。

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