在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。所以我不清除'dummy entry'的设计？
任何人都可以向我展示“虚拟”功能并指出我代码中的错误吗？
请您参考如下方法:
(注意:我不太熟悉 Python 的 dict 实现的内部结构，我在这里一般指的是哈希表。)
哈希表的基本思想是可以从键中导出一个哈希值，并使用它直接转到保存相应值的表条目。然而，任何实现都必须处理两个不同键具有相同散列值的可能性(或者以其他方式通过对散列值执行的模运算映射到相同的条目索引)。 Python 通过一种称为“封闭散列”的策略来处理此问题:如果正确的条目已被不同的键占用，则会检查其他可能条目的计算序列，直到最终找到一个空条目。 (该表不允许接近 100% 满，因此此检查永远不会花费不合理的时间，并保证找到一个空条目。)get() 的实现如下相同的顺序，直到找到正确的键或找到空条目。
现在，假设有两个键 A 和 B，它们有哈希冲突，按顺序插入到字典中，然后是 A 被删除。如果您通过将 A 的条目设置为空来实现它，那么请考虑在随后调用 get(B) 时会发生什么:它会立即找到该空条目，并报告 B 根本不存在!这个问题可以通过有一个特殊的标志值来解决，它不同于实际的键或空条目，用于指示已删除的条目。当 get() 看到其中之一时，它知道它需要继续寻找其他可能的入口位置。当 set() 看到一个时，它可以用插入的 key 覆盖它(尽管它仍然需要扫描直到找到一个实际的空条目，以确保 key 不存在)。
