基于现有插入逻辑的哈希表如何实现条目删除？

当前实现的哈希表采用*链地址法（拉链法）*解决哈希冲突，每个桶存储单链表的头指针，插入逻辑为头插法；现有search方法仅返回匹配key的目标节点本身，由于单链表不支持反向回溯前驱节点，因此删除操作无法直接依赖现有search能力实现，需要在遍历过程中追踪目标节点的前驱位置才能完成删除。

核心实现逻辑 #

删除操作按以下步骤执行：

• 计算待删除key的哈希值，定位到对应的桶索引，获取该桶下的单链表起始指针
• 遍历单链表，同时维护两个指针：当前遍历节点curr、当前节点的前驱节点prev，逐个匹配节点key与待删key
• 匹配到目标节点后分场景处理：
  • 若目标节点是当前桶的头节点：直接将桶的头指针指向目标节点的下一个节点，即可完成头节点的移除
  • 若目标节点位于链表中间或尾部：将前驱节点的next指针跳过目标节点，直接指向目标节点的下一个节点，完成节点移除
  • 遍历完整个链表都未匹配到对应key时，直接返回删除失败的标识即可

适配现有代码的可运行删除方法 #

/**
 * 删除指定key的哈希表条目
 * @param k 待删除条目的主键
 * @return 删除成功返回true，未找到对应条目返回false
 */
public boolean delete(int k) {
    // 定位目标节点所在的桶
    int index = hash(k);
    HNode curr = head[index];
    HNode prev = null;

    while (curr != null) {
        if (curr.key == k) {
            // 待删节点为桶的头节点
            if (prev == null) {
                head[index] = curr.next;
            }
            // 待删节点为非头节点
            else {
                prev.next = curr.next;
            }
            // 断开节点引用便于垃圾回收
            curr.next = null;
            return true;
        }
        // 双指针同步后移
        prev = curr;
        curr = curr.next;
    }
    // 全链表遍历完成未找到匹配节点
    return false;
}

补充说明 #

• 由于插入采用头插法，若同一key被重复插入到同一个桶中，当前删除方法只会移除遍历过程中遇到的第一个匹配key的节点。如果需要删除所有同key条目，只需移除找到即返回的逻辑，遍历完全链表后完成所有匹配节点的移除即可。
• 现有search方法不需要做任何修改，它仅用于返回第一个匹配key的节点，和删除逻辑无强耦合，可以和删除方法共存。

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