分离链接法哈希表删除函数每次少删1条数据该如何排查？

问题根因 #

你当前的实现每个哈希桶最多仅删除1个符合条件的节点，如果某个桶的链表中存在多个匹配toDelete的节点，剩余的匹配节点会被遗漏，这就是删除总数少于预期的原因。

现有代码的逻辑缺陷：

• 对每个桶的链表，仅通过单次while遍历找到第一个匹配节点就停止遍历，删除该节点后直接处理下一个桶，没有检查当前桶后续节点是否还有符合条件的。

修复方案 #

需要修改每个桶的遍历逻辑，删除一个匹配节点后继续向后遍历，直到整个链表遍历完成，参考修复后的代码：

void HashMap::deleteByString(string toDelete)
{
    bool haveDeleted = false;
    int totalDeleted = 0;

    auto start = chrono::steady_clock::now();
    for (int i = 0; i < buckets; i++) {
        Node* current = hashTable[i];
        Node* previous = NULL;
        // 遍历当前桶的完整链表
        while (current != nullptr) {
            if (current->data.getCountry() == toDelete) {
                Node* temp = current;
                if (previous != nullptr) {
                    previous->next = current->next;
                } else {
                    // 待删除节点是桶的头节点
                    hashTable[i] = current->next;
                }
                // 先移动current指针再删除节点，避免指针失效
                current = current->next;
                delete temp;
                haveDeleted = true;
                ++totalDeleted;
            } else {
                // 不匹配则正常向后移动指针
                previous = current;
                current = current->next;
            }
        }
    }
}

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