python – 有没有理由不使用OrderedDict？

OrderedDict是dict的子类,需要更多内存来跟踪添加键的顺序.这不是微不足道的.该实现在封面下添加了第二个dict,以及所有键的双重链接列表(这是记住订单的部分),以及一堆弱反射代理.它的速度并不慢很多,但至少使用普通字典使内存翻倍.

但如果合适,请使用它！这就是为什么它在那里:-)

这个怎么运作

基本字典只是一个普通的字典映射键值 – 它根本不是“有序”的.当< key,value>添加了对,密钥将附加到列表中.列表是记住订单的部分.

但如果这是一个Python列表,删除一个密钥将花费O(n)时间两次：O(n)时间在列表中找到密钥,O(n)时间从列表中删除密钥.

所以这是一个双向链表.这使得删除键常量(O(1))时间.但是我们仍然需要找到属于密钥的双向链表节点.为了使该操作也是O(1)时间,第二个 – 隐藏 – 字典将键映射到双向链表中的节点.

所以添加一个新的< key,value> pair需要将对添加到基本字典,创建一个新的双向链表节点来保存密钥,将新节点附加到双向链表,并将密钥映射到隐藏字典中的新节点.工作量的两倍多,但总体上还是O(1)(预期的情况)时间.

类似地,删除当前存在的密钥也是工作量的两倍多但O(1)整体预期时间：使用隐藏的字典找到密钥的双向链表节点,从列表中删除该节点,然后删除密钥从这两个词.

等等.效率很高.