我试图使用抽象基类MutableMapping在Python中实现映射，但是在实例化时遇到错误。我将如何制作这个字典的工作版本，以尽可能多的方式模拟内置的dict类，以清楚起见，使用抽象基类？
>>> class D(collections.MutableMapping):
... pass
...
>>> d = D()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: Can't instantiate abstract class D with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__
一个好的答案将演示如何使这项工作，特别是不子类化dict(我非常熟悉的概念)。
如何使用抽象基类实现字典？
一个好的答案将演示如何使这项工作，特别是 没有子类字典。
以下是错误消息：TypeError: Can't instantiate abstract class D with abstract methods __delitem__, __getitem__, __iter__, __len__, __setitem__
事实证明，必须实现它们才能使用抽象基类(ABC)，MutableMapping.
实现
因此，我实现了一个映射，它在大多数方面的工作方式类似于字典，它使用对象的属性引用字典进行映射。(委托与继承不同，所以我们只委托给实例__dict__，我们可以使用任何其他即席映射，但你似乎并不关心实现的那部分。在 Python 2 中这样做是有意义的，因为 MutableMapping 在 Python 2 中没有__slots__，所以无论哪种方式，你都在创建一个__dict__。在 Python 3 中，您可以通过设置__slots__来完全避免字典。
from collections.abc import MutableMapping
class D(MutableMapping):
'''
Mapping that works like both a dict and a mutable object, i.e.
d = D(foo='bar')
and
d.foo returns 'bar'
'''
# ``__init__`` method required to create instance from class.
def __init__(self, *args, **kwargs):
'''Use the object dict'''
self.__dict__.update(*args, **kwargs)
# The next five methods are requirements of the ABC.
def __setitem__(self, key, value):
self.__dict__[key] = value
def __getitem__(self, key):
return self.__dict__[key]
def __delitem__(self, key):
del self.__dict__[key]
def __iter__(self):
return iter(self.__dict__)
def __len__(self):
return len(self.__dict__)
# The final two methods aren't required, but nice for demo purposes:
def __str__(self):
'''returns simple dict representation of the mapping'''
return str(self.__dict__)
def __repr__(self):
'''echoes class, id, & reproducible representation in the REPL'''
return '{}, D({})'.format(super(D, self).__repr__(),
self.__dict__)
示范
为了演示用法：
>>> d = D((e, i) for i, e in enumerate('abc'))
>>> d
<__main__.D object at 0x7f75eb242e50>, D({'b': 1, 'c': 2, 'a': 0})
>>> d.a
0
>>> d.get('b')
1
>>> d.setdefault('d', []).append(3)
>>> d.foo = 'bar'
>>> print(d)
{'b': 1, 'c': 2, 'a': 0, 'foo': 'bar', 'd': [3]}
为了确保字典API，吸取的教训是您可以随时检查collections.abc.MutableMapping：
>>> isinstance(d, MutableMapping)
True
>>> isinstance(dict(), MutableMapping)
True
虽然由于集合导入的注册，字典总是可变映射的实例，但反之亦然：
>>> isinstance(d, dict)
False
>>> isinstance(d, (dict, MutableMapping))
True
完成本练习后，我很清楚，使用抽象基类只能保证该类的用户使用标准 API。在这种情况下，假设 MutableMapping 对象的用户将保证使用 Python 的标准 API。
警告：
未实现fromkeys类构造函数方法。
>>> dict.fromkeys('abc')
{'b': None, 'c': None, 'a': None}
>>> D.fromkeys('abc')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: type object 'D' has no attribute 'fromkeys'
可以屏蔽内置的字典方法，如get或setdefault
>>> d['get'] = 'baz'
>>> d.get('get')
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'str' object is not callable
再次揭开面具相当简单：
>>> del d['get']
>>> d.get('get', 'Not there, but working')
'Not there, but working'
但我不会在生产中使用此代码。
没有字典的演示，Python 3：
>>> class MM(MutableMapping):
... __delitem__, __getitem__, __iter__, __len__, __setitem__ = (None,) *5
... __slots__ = ()
...
>>> MM().__dict__
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'MM' object has no attribute '__dict__'
在不实际使用dict的情况下演示这一点的最佳方法可能是实现一些非常简单的东西，与dict非常不同，而且并非完全无用。就像固定大小bytes到相同大小的bytes的固定大小映射一样。(例如，您可以将其用于路由表 - 它将比将解压缩的键映射到解压缩值的dict要紧凑得多，尽管显然是以速度和灵活性为代价的
。哈希表只是一个(hash, key, value)元组的数组。由于这样做的重点是将数据打包，因此我们将这些数据塞进一个struct，这意味着我们可以使用一个大bytearray进行存储。为了将插槽标记为空，我们将其哈希值设置为0— 这意味着我们需要通过将任何真实的0转换为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' ' * 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__。但是，更好的地方是文档，它将告诉您，如果您实现这五种方法(加上基类所需的任何其他方法，但从表中可以看到没有)，您将免费获得所有其他方法。您可能无法获得所有这些实现的最有效实现，但我们会回到这一点。
首先，让我们处理__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__.就像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)
同样适用于values，以及可能的其他方法。
至少
您需要在子类中实现从 MutableMapping 继承的所有抽象方法
class D(MutableMapping):
def __delitem__(self):
'''
Your Implementation for deleting the Item goes here
'''
raise NotImplementedError("del needs to be implemented")
def __getitem__(self):
'''
Your Implementation for subscripting the Item goes here
'''
raise NotImplementedError("obj[index] needs to be implemented")
def __iter__(self):
'''
Your Implementation for iterating the dictionary goes here
'''
raise NotImplementedError("Iterating the collection needs to be implemented")
def __len__(self):
'''
Your Implementation for determing the size goes here
'''
raise NotImplementedError("len(obj) determination needs to be implemented")
def __setitem__(self):
'''
Your Implementation for determing the size goes here
'''
raise NotImplementedError("obj[index] = item, needs to be implemented")
>>> D()
<__main__.D object at 0x0258CD50>
此外
您需要提供一种数据结构来存储您的映射(哈希、AVL、红黑)，以及一种构建字典的方法
以MutableMapping为基类，您应该在类中自己创建此方法：__delitem__, __getitem__, __iter__, __len__, __setitem__.
要创建自定义字典类，您可以从字典派生它：
>>> class D(dict):
... pass
...
>>> d = D()
>>> d
{}
抽象基类的整个思想是它有一些成员(C++术语中的纯虚拟成员)，你的代码必须提供这些成员 - C++这些是纯虚拟成员和你可以覆盖的其他虚拟成员。
Python与C++的不同之处在于，所有类的所有成员都是虚拟的，可以被覆盖(你可以向所有类和实例添加成员)，但抽象基类有一些必需的缺失类，这些类等同于C++纯虚拟。
解决了这个问题后，您只需要提供缺少的成员即可创建派生类的实例。
对于您尝试做的事情的示例，请参阅此处接受的答案，但不要在类中使用字典，您必须提供它自己提供的方法。