为什么要使用虚拟插槽

Question

在Cpython实现中,当我们删除dict中的键时,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

我可以插入,删除值,如我所愿.当我想要一个空条目时,我将测试条目的值是否为无.所以我不清楚'虚拟条目'的设计？

任何人都可以向我展示"虚拟"功能,并在我的代码中指出错误吗？

Answer 1

(注意:我对Python dict实现的内部结构并不熟悉,我在这里一般都是哈希表.)

哈希表的基本思想是,您可以从键中派生哈希值,并使用它直接转到保存相应值的表条目.然而,任何实现都必须处理两个不同密钥具有相同散列值的可能性(或者通过对散列值执行的模运算来映射到相同的条目索引).Python的通过一个名为"封闭散列"的策略来处理它:如果正确的入口已经采取不同的密钥,其他可能的项的计算顺序进行检查,直到一个空文件,终于找到了.(该表不允许接近100%满,因此该检查从不花费不合理的时间,并保证找到一个空条目.)执行get()遵循相同的顺序,直到右键是找到,或找到一个空条目.

现在,假设有两个密钥A和B具有哈希冲突的密钥按顺序插入到dict中,然后A被删除.如果你通过将A's条目设置为空来实现它,那么考虑在后续调用中会发生什么get(B):它会立即找到那个空条目,并报告B根本不存在!可以通过使用特殊标志值来修复此问题,该标志值与实际键或空条目不同,用于指示已删除的条目.当get()看到其中一个时,它知道它需要继续寻找其他可能的入口位置.当set()看到一个时,它可以用插入的密钥覆盖它(虽然它仍然需要扫描,直到它找到一个实际的空条目,以确保密钥不存在).