从 python 中删除一个键dict or defaultdict在Python中是O(1)操作，正如这里提到的 https://www.ics.uci.edu/~brgallar/week8_2.html and here https://wiki.python.org/moin/TimeComplexity。从中删除密钥OrderedDict，我们可以使用del d[key] or use popitem()方法，如中提到的the docs https://docs.python.org/3.6/library/collections.html#collections.OrderedDict.popitem.
底层实现是什么OrderedDict和时间复杂度del手术？
编辑：这个答案OrderedDict 性能（与 deque 相比） https://stackoverflow.com/questions/8176513/ordereddict-performance-compared-to-deque，指的是复杂度del in OrderedDict为 O(1)。然而，我们如何在实施细节层面证明它的合理性呢？
The 执行 https://github.com/python/cpython/blob/3.7/Lib/collections/__init__.py#L129 of OrderedDict.__delitem__在Python 3.7中如下：
def __delitem__(self, key, dict_delitem=dict.__delitem__):
'od.__delitem__(y) <==> del od[y]'
# Deleting an existing item uses self.__map to find the link which gets
# removed by updating the links in the predecessor and successor nodes.
dict_delitem(self, key)
link = self.__map.pop(key)
link_prev = link.prev
link_next = link.next
link_prev.next = link_next
link_next.prev = link_prev
link.prev = None
link.next = None
这段代码做了三件事：
- 从内部键值字典中删除一个项目。
- 从保存链表节点的字典中删除一个节点。
- 从双向链表中删除一项。
由于上述所有操作的平均情况复杂度是恒定的，因此平均情况复杂度为OrderedDict.__delitem__也是恒定的。
但请注意，从字典中删除键的最坏情况复杂度是O(n)，因此这同样适用于有序字典。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
