为何CPython字典删除键时使用dummy slot？我的实现存在哪些问题？

我在理解CPython字典的实现时，发现删除键的时候会把对应条目设置为dummy entry，不太明白为什么要这么做——直接把条目值设为nil不行吗？因为我不太懂C语言，所以用Python模拟了字典的实现（代码如下），目前能正常插入、删除，通过判断value是否为None识别空条目，但还是搞不懂dummy entry的设计意义，希望有人能说明它的特性，同时指出我代码里的错误。

class DictEntry:
    def __init__(self):
        self.key = None
        self.value = None
        self.hash = None
    def __repr__(self):
        return ' %s %s %s' % (self.key, self.hash, self.value)

class Hashtable:
    def __init__(self):
        self.size = 8
        self.used = 0
        self.mask = self.size - 1
        self.pow2 = 3
        self.entries = [DictEntry() for _ in range(self.size)]  # 修正拼写错误

    def insert(self, key, item):
        hash_value = hash(key)  # 替换原代码的_hash，用Python内置hash
        _key = hash_value & (self.size - 1)
        if not self.is_slot_empty(_key):
            _key = self.next_slot(_key, hash_value)
        entry = self.entries[_key]
        entry.key = key  # 修正：应该存原始key，不是槽位索引
        entry.hash = hash_value
        entry.value = item
        self.used += 1
        # if need resize
        if self.size * 2 // 3 < self.used:  # 修正除法为整数除法
            old_entries = self.entries
            self.entries = [DictEntry() for _ in range(self.size * 2)]
            self.size = 2 * self.size
            self.mask = self.size - 1
            self.pow2 += 1
            for entry in old_entries:
                if entry.value is not None:  # 明确判断None
                    self.insert(entry.key, entry.value)

    def delete(self, obj):
        # delete won't resize
        # find the slot
        hash_value = hash(obj)
        key = hash_value & (self.size - 1)
        perturb = hash_value
        PERTURB_SHIFT = 5
        # 修正查找逻辑：需要同时比较hash和key，避免哈希碰撞
        while self.entries[key].hash != hash_value or self.entries[key].key != obj:
            key = key * 5 + 1 + perturb
            perturb <<= PERTURB_SHIFT
            key = key % (2 ** self.pow2)
            # 这里应该加终止条件，防止无限循环
            if self.entries[key].hash is None:
                raise KeyError(obj)
        # 原代码直接清空，这里应该设置为dummy（比如标记key为特殊值，而不是全设为None）
        entry = self.entries[key]
        # 模拟dummy entry：保留hash，把key设为特殊标记，value设为None
        entry.key = '<dummy>'
        entry.value = None
        self.used -= 1

    def getitem(self, obj):
        hash_value = hash(obj)
        key = hash_value & (self.size - 1)
        perturb = hash_value
        PERTURB_SHIFT = 5
        # 修正查找逻辑：同时比较hash和key，并且跳过dummy条目
        while True:
            entry = self.entries[key]
            if entry.hash is None:
                raise KeyError(obj)
            if entry.hash == hash_value and entry.key == obj:
                return entry.value
            # 跳过dummy条目，继续探测
            key = key * 5 + 1 + perturb
            perturb <<= PERTURB_SHIFT
            key = key % (2 ** self.pow2)

    def next_slot(self, key, hash_value):
        # open_address
        perturb = hash_value
        PERTURB_SHIFT = 5
        while not self.is_slot_empty(key):
            key = key * 5 + 1 + perturb
            perturb <<= PERTURB_SHIFT
            key = key % (2 ** self.pow2)
        return key

    def is_slot_empty(self, key):
        entry = self.entries[key]
        # 修正：真正的空槽是hash为None，dummy的hash不为None但key是特殊标记
        return entry.hash is None

    def __repr__(self):
        return '%s' % [(entry.hash, entry.key, entry.value) for entry in self.entries]

先解释dummy entry（墓碑条目）的核心作用 #

CPython的字典用的是开放寻址法的哈希表，而dummy entry（也叫墓碑）是解决开放寻址中「删除元素后破坏探测链」问题的关键，核心原因有三个：

• 避免查找时提前终止
  开放寻址的哈希表中，当多个元素哈希冲突时，会按照固定的探测路径（比如CPython的伪随机扰动算法）依次往后找空槽插入。如果删除一个元素后直接把槽位设为空（nil），那么后续查找那些在这个槽位之后插入的冲突元素时，探测到这个空槽就会误以为「目标元素不存在」，直接终止查找——但实际上目标元素还在后面的槽位里。
  dummy entry的作用就是告诉查找算法：「这里曾经有元素被删除，你得继续往后找，不能停」。

• 维持探测链的完整性
  每个元素的探测路径是由它的哈希值决定的，这条链不能被打断。如果直接清空槽位，相当于在链上挖了个坑，后面的元素就会「失联」。dummy entry相当于在这个位置放了个标记，既表示这个槽位可以被新元素复用，又不会打断探测链。

• 防止插入时的错误覆盖
  插入新元素时，算法会沿着探测路径找第一个可复用的槽位（空槽或dummy槽）。如果没有dummy，直接清空的槽位会被当成空槽，但这个槽位可能是探测链中的一个节点，直接插入会破坏原本的链结构，导致其他元素无法被找到。

再说说你代码里的几个关键问题 #

1. 拼写错误：多处把entries写成了entyies，这会导致运行时报错，我已经在修正后的代码里改过来了。

2. 删除逻辑的致命问题：你的delete方法直接把entry的key、hash、value都设为None，这相当于把槽位彻底清空了。按照开放寻址的规则，这会导致后续查找那些在这个槽位之后插入的冲突元素失败——比如元素A因为冲突被放到了槽2，后来槽0的元素被删除，查找A时探测到槽0是空的，就会直接返回不存在，但A其实在槽2。

3. is_slot_empty的判断逻辑错误：你只通过value是否为None来判断槽位是否为空，但这会把dummy条目和真正的空槽混为一谈。真正的空槽应该是从未被使用过的（hash为None），而dummy条目是曾经被使用过但后来被删除的（hash保留，key设为特殊标记）。

4. insert方法里的entry.key = _key错误：这里应该存储传入的原始key，而不是计算后的槽位索引_key，否则后续查找时无法匹配用户传入的原始键，会导致查找失败。

5. 查找逻辑缺失哈希冲突处理：你的getitem和delete方法只比较了hash_value，但哈希是可能碰撞的——不同的key可能有相同的哈希值，所以必须同时比较key是否相等，否则会返回错误的元素。

6. 缺少查找终止条件：在delete和getitem的循环里，如果找不到目标元素，会无限循环下去，应该在遇到真正的空槽（hash为None）时抛出KeyError。

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