OrderedDict是的子类
dict,并且需要更多内存来跟踪键的添加顺序。这不是小事。该实现
dict在幕后增加了第二个,所有键的双向链接列表(这是记住顺序的部分),以及一堆weakref代理。它并没有慢
很多 ,但至少比使用plain的内存多了一倍
dict。
但是,如果合适,请使用它!这就是为什么它在那里:-)
这个怎么运作
基本dict只是将键映射到值的普通dict-根本不是“有序的”。
<key, value>添加一对后,
key会附加到列表中。列表是记住订单的部分。
但是,如果这是Python列表,则 删除 密钥将花费
O(n)两倍的时间:
O(n)在列表中找到密钥的
O(n)时间,以及从列表中删除密钥的时间。
因此,它是一个双向链接列表。这使得删除键的
O(1)时间为常数()。但是我们仍然需要找到属于该键的双向链接列表节点。为了节省操作
O(1)时间,第二个-
隐藏的dict将键映射到双向链接列表中的节点。
因此,添加新
<key,value>对需要将对添加到基本字典,创建一个新的双向链接列表节点来保存密钥,将该新节点附加到双向链接列表中,并将密钥映射到隐藏字典中的该新节点。工作量是原来的两倍多,但
O(1)总体上还是(预期的情况)。
同样,删除存在的密钥也要花两倍的
O(1)时间,但总的来说是预期的时间:使用隐藏的字典来查找密钥的双向链接列表节点,从列表中删除该节点,然后从两个字典中删除密钥。
等等,这非常有效。



