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

Question

如此处和此处所述，从python dict或defaultdictpython中删除密钥是O（1）操作。要从中删除密钥，我们可以使用或使用方法，如docs中所述。OrderedDictdel d[key]popitem()

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

编辑：此答案的OrderedDict性能（与双端队列相比），称为delin 的复杂度OrderedDict为O（1）。但是，我们如何才能在实现细节级别证明它的合理性呢？

Answer 1

该实施的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

此代码执行3件事：

• 从内部键值字典中删除一个项目。
• 从包含链接列表节点的字典中删除一个节点。
• 从双向链接列表中删除一个项目。

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