python - 从 python 有序字典中删除一个键的复杂性

Question

在 python 中从 python dict 或 defaultdict 中删除一个键是 O(1) 操作，as mentioned here和 here .要从 OrderedDict 中删除键，我们可以使用 del d[key] 或使用 popitem() 方法，如 the docs 中所述。 .

OrderedDict的底层实现是什么以及del操作的时间复杂度？

编辑:这个答案 OrderedDict performance (compared to deque) , 指 OrderedDict 中 del 的复杂度为 O(1)。但是，我们如何在实现细节级别证明它的合理性？

Answer 1

implementation Python 3.7 中的 OrderedDict.__delitem__ 如下:

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__ 的复杂度也是常数。