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

Question

从 python dict 或 python 中的 defaultdict 中删除一个键是 O(1) 操作，as mentioned here and here. To remove a key from OrderedDict, we can either use del d[key] or use popitem() method, as mentioned in the docs.

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

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

Answer 1

Python3.7中OrderedDict.__delitem__的implementation如下：

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

这段代码做了 3 件事：

从内部键值字典中删除一个项目。
从保存链表节点的字典中删除一个节点。
从双向链表中删除一个项目。

由于上述所有操作都需要常数时间，因此 OrderedDict.__delitem__ 的复杂度也是常数。

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

Complexity of deleting a key from python ordered dict

python

python-3.x

dictionary

ordereddictionary