Python 3.7+如何以O(1)时间弹出字典最先插入的键值对

Python原生普通字典无法实现稳定的O(1)时间复杂度弹出最先插入的键值对，具体说明如下：

• Python 3.7及以上版本的内置dict虽然默认保留键值对的插入顺序，但核心优化方向是哈希查询性能，没有为队首弹出操作做常数时间适配。如果强行在普通dict上实现弹出首个键值对，通常会写类似first_key = next(iter(dictionary)); dictionary.pop(first_key)的代码，这种写法无法保证稳定O(1)耗时：随着前部键值对被不断删除，哈希表前部会积累大量已删除的哑标记位，后续查找首个有效键的耗时会逐步升高，最坏情况下时间复杂度为O(n)。
• 如果需要稳定O(1)时间完成先进先出的键值对弹出，直接使用标准库collections模块的OrderedDict即可。它的底层通过独立双向链表维护插入顺序，首尾节点的查找、删除操作都是纯指针操作，稳定保持O(1)时间复杂度。
  示例代码：

  from collections import OrderedDict
  
  dictionary = OrderedDict({
      'a': 2,
      'b': 3,
      'c': 4
  })
  # 弹出最先插入的键值对，稳定O(1)时间
  print(dictionary.popitem(last=False))  # 返回('a', 2)
  

  补充说明：OrderedDict.popitem()方法的last参数默认值为True，此时行为和普通dict的popitem()完全一致，会弹出最后插入的键值对；传入last=False时就会按照先进先出规则，弹出最早插入的键值对。

注意：不要因为Python 3.7+的普通dict保留插入顺序，就认为它可以完全替代OrderedDict。二者的设计目标不同：普通dict面向通用哈希表场景，顺序相关的首尾弹出、节点移动等操作都没有做专门优化；OrderedDict面向顺序敏感场景，针对顺序相关操作做了专门的常数时间适配，这类场景下性能表现远好于普通dict。

内容的提问来源于stack exchange，提问作者Hari Raagav T R