为什么要使用虚拟插槽？

Question

在Cpython实现中，当我们删除一个字典中的键时，Cpython会将相应的条目设置为一个虚拟条目，为什么是一个虚拟条目？我可以让 ertry 的值为零吗？

我不擅长C，所以我在python中模拟了它，下面是我python的实现代码：

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.entyies = [DictEntry() for _ in range(self.size)]

def insert(self, key, item):
    hash_value = _hash(key)
    _key = hash_value & (self.size - 1)
    if not self.is_slot_empty(_key):
        _key = self.next_slot(_key, hash_value)
    entry = self.entyies[_key]
    entry.key = _key
    entry.hash = hash_value
    entry.value = item
    self.used += 1
    # if need resize
    if self.size * 2 / 3 < self.used:
        old_entyies = self.entyies
        self.entyies = [DictEntry() for _ in range(self.size * 2)]
        self.size = 2 * self.size
        self.mask = self.size - 1
        self.pow2 += 1
        for entry in old_entyies:
            if entry.value:
                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
    while self.entyies[key].hash != hash_value:
        print(self.entyies[key].value, obj)
        key = key * 5 + 1 + perturb
        perturb <<= PERTURB_SHIFT
        key = key % 2 ** self.pow2

    # set to empty
    entry = self.entyies[key]
    entry.key = None
    entry.hash = None
    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
    while self.entyies[key].hash != hash_value:
        key = key * 5 + 1 + perturb
        perturb <<= PERTURB_SHIFT
        key = key % 2 ** self.pow2
    return self.entyies[key].value

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):
    if self.entyies[key].value:
        return False
    return True

def __repr__(self):
    return '%s' % [(entry.hash, entry.value) for entry in self.entyies]enter code here

而且我可以根据需要插入、删除值。当我想要一个空条目时，我将测试条目的值是否为 None.So 我不清除 'dummy entry' for?

的设计

任何人都可以向我展示 'dummy' 功能并指出我代码中的错误吗？

Answer 1

（注意：我不太熟悉 Python 的 dict 实现的内部结构，我在这里一般指的是哈希 table。）

散列的基本思想table 是您可以从键中导出散列值，并使用它直接转到保存相应值的table 条目。然而，任何实现都必须处理两个不同键具有相同散列值的可能性（或者以其他方式通过对散列值执行的模运算映射到相同的条目索引）。 Python 通过一种名为 "closed hashing" 的策略处理此问题：如果正确的条目已被不同的键占用，则会检查计算出的其他可能条目的序列，直到最终找到一个空条目。（不允许 table 接近 100% 满，因此此检查永远不会花费不合理的时间，并保证找到一个空条目。） get() 的实现遵循相同的顺序，直到找到正确的键或找到空条目。

现在，假设有两个键 A 和 B，它们存在哈希冲突，按顺序插入到字典中，然后 A 被删除。如果您通过将 A 的条目设置为空来实现它，那么请考虑在随后调用 get(B) 时会发生什么：它会立即找到该空条目，并报告 B 是根本不存在！这个问题可以通过有一个特殊的标志值来解决，它不同于实际的键或空条目，用于指示已删除的条目。当 get() 看到其中之一时，它知道它需要继续寻找其他可能的入口位置。当 set() 看到一个时，它可以用插入的密钥覆盖它（尽管它仍然需要扫描直到找到一个实际的空条目，以确保密钥不存在）。

为什么要使用虚拟插槽？

Why use dummy slots?

python

dictionary

cpython