Python实现哈希表时remove函数删除桶首节点失败的问题排查

你的哈希表实现中，put和get功能正常，但删除桶内第一个节点时失效，核心原因是未正确更新桶的头引用，以下是问题分析和修复方案：

问题根源 #

错误实现1的问题 #

你最初的remove函数用prev = Node(None, None, node)创建了一个临时节点，这个节点不属于桶的链表结构。当删除第一个节点时，修改prev.next只会改变这个临时节点的指针，不会影响self.buckets[bucketIndex]存储的链表头引用，因此原头节点依然存在于桶中，导致get仍能获取到值。

错误实现2的问题 #

你补充的版本中，node = node.next只是修改了局部变量node的指向，并未改变self.buckets[bucketIndex]中存储的引用。Python中变量是对象的引用，局部变量的赋值不会影响容器（如这里的buckets列表）内的引用，所以桶的头节点还是原来的对象，删除操作无效。

修复后的remove函数 #

def remove(self, key):
    bucketIndex = self._hash(key)
    node = self.buckets[bucketIndex]
    prev = None
    while node is not None and node.key != key:
        prev = node
        node = node.next
    if not node:
        return None
    value = node.value
    if not prev:
        # 删除的是桶的第一个节点，直接更新桶的头引用
        self.buckets[bucketIndex] = node.next
    else:
        prev.next = node.next
    return value

修复说明 #

• 当prev为None时，说明要删除的是桶的第一个节点，此时直接修改self.buckets[bucketIndex]，让它指向原头节点的下一个节点，这样桶的头引用就被正确更新。
• 当删除的是链表中间或末尾节点时，通过prev.next = node.next跳过目标节点，完成删除，这部分逻辑原本是正确的。

验证修复后的代码：

hashTable = HashTable()
hashTable.put('a', 111)
print(hashTable.get('a'))  # 输出111
hashTable.remove('a')
print(hashTable.get('a'))  # 输出None，符合预期

hashTable.put('C', 222)
print(hashTable.get('C'))  # 输出222
hashTable.remove('C')
print(hashTable.get('C'))  # 输出None，符合预期

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