在不实际使用dict
anywhere 的情况下演示这一点的最佳方法可能是实现一些非常简单、与 非常不同dict
且并非完全无用的东西。就像从固定大小bytes
到相同固定大小的固定大小映射bytes
。dict
(例如,您可以将它用于路由表——它比将解包键映射到解包值要紧凑得多,尽管显然以速度和灵活性为代价。)
哈希表只是一个(hash, key, value)
元组数组。由于这样做的重点是打包数据,因此我们将它们塞进 astruct
中,这意味着我们可以只使用 bigbytearray
进行存储。为了将插槽标记为空,我们将其哈希值设置为0
— 这意味着我们需要0
通过将其转换为 a来“转义”任何实数1
,这很愚蠢,但更易于编码。为简单起见,我们还将使用最愚蠢的probe
算法。
class FixedHashTable(object):
hashsize = 8
def __init__(self, elementsize, size):
self.elementsize = elementsize
self.size = size
self.entrysize = self.hashsize + self.elementsize * 2
self.format = 'q{}s{}s'.format(self.elementsize, self.elementsize)
assert struct.calcsize(self.format) == self.entrysize
self.zero = b'\0' * self.elementsize
self.store = bytearray(struct.pack(self.format, 0,
self.zero, self.zero)
) * self.size
def hash(self, k):
return hash(k) or 1
def stash(self, i, h, k, v):
entry = struct.pack(self.format, h, k, v)
self.store[i*self.entrysize:(i+1)*self.entrysize] = entry
def fetch(self, i):
entry = self.store[i*self.entrysize:(i+1)*self.entrysize]
return struct.unpack(self.format, entry)
def probe(self, keyhash):
i = keyhash % self.size
while True:
h, k, v = self.fetch(i)
yield i, h, k, v
i = (i + 1) % self.size
if i == keyhash % self.size:
break
正如错误消息所说,您需要为抽象方法__delitem__
、__getitem__
、__iter__
、__len__
和提供实现__setitem__
。但是,更好的地方是docs,它将告诉您,如果您实现这五个方法(加上基类所需的任何其他方法,但从表中可以看出没有),您将得到所有其他方法都是免费的。您可能无法获得所有这些最有效的实现,但我们会回到这一点。
首先,让我们处理__len__
. 通常人们期望这是 O(1),这意味着我们需要独立跟踪它,并根据需要更新它。所以:
class FixedDict(collections.abc.MutableMapping):
def __init__(self, elementsize, size):
self.hashtable = FixedHashTable(elementsize, size)
self.len = 0
现在,__getitem__
只需进行探测,直到找到所需的密钥或到达末尾:
def __getitem__(self, key):
keyhash = self.hashtable.hash(key)
for i, h, k, v in self.hashtable.probe(keyhash):
if h and k == key:
return v
并且__delitem__
做同样的事情,除了如果找到它会清空插槽并更新len
.
def __delitem__(self, key):
keyhash = self.hashtable.hash(key)
for i, h, k, v in self.hashtable.probe(keyhash):
if h and k == key:
self.hashtable.stash(i, 0, self.hashtable.zero, self.hashtable.zero)
self.len -= 1
return
raise KeyError(key)
__setitem__
有点棘手——如果找到,我们必须替换槽中的值;如果没有,我们必须填补一个空位。在这里,我们必须处理哈希表可能已满的事实。当然,我们必须照顾len
:
def __setitem__(self, key, value):
keyhash = self.hashtable.hash(key)
for i, h, k, v in self.hashtable.probe(keyhash):
if not h or k == key:
if not h:
self.len += 1
self.hashtable.stash(i, keyhash, key, value)
return
raise ValueError('hash table full')
那叶子__iter__
。就像 a 一样dict
,我们没有任何特定的顺序,所以我们可以迭代哈希表槽并产生所有非空的槽:
def __iter__(self):
return (k for (h, k, v) in self.hashtable.fetch(i)
for i in range(self.hashtable.size) if h)
当我们这样做时,我们不妨写一个__repr__
. 请注意,我们可以使用我们免费获得的事实items
:
def __repr__(self):
return '{}({})'.format(type(self).__name__, dict(self.items()))
但是,请注意默认items
只创建一个ItemsView(self)
,如果您通过源跟踪它,您会看到它迭代self
并查找每个值。如果性能很重要,您显然可以做得更好:
def items(self):
pairs = ((k, v) for (h, k, v) in self.hashtable.fetch(i)
for i in range(self.hashtable.size) if h)
return collections.abc.ItemsView._from_iterable(pairs)
同样 for values
,可能还有其他方法。