OrderedDict内部维护了一个双向链表，它会根据元素加入的顺序来排列键的位置。第一个新加入的元素被放置在链表的末尾，接下来对已存在的键做重新赋值，不会改变键的位置。
请注意：OrderedDict的大小是普通字典的2倍。这是由于它额外创建的链表所致。
OrderedDict 源码
# pre 和 next 属性作为前驱节点和后驱节点，
# key 储存键，__weakref__支持弱引用
class _Link(object):
__slots__ = 'prev', 'next', 'key', '__weakref__'
class OrderedDict(dict):
'保留插入顺序的字典'
# 继承自字典的键值对字典
# 方法： __getitem__, __len__, __contains__, get
# The remaining methods are order-aware.
# 时间复杂度和正常字典一样
# 内部的 self.__map 字典把 key 和双向链表指针关联
# 循环双链表以一个哨兵元素开始和结束
# 哨兵元素永远不会被删除 （简化算法）
# The sentinel is in self.__hardroot with a weakref proxy in self.__root.
# The prev links are weakref proxies (to prevent circular references).
# Individual links are kept alive by the hard reference in self.__map.
# Those hard references disappear when a key is deleted from an OrderedDict.
def __init__(self, other=(), /, **kwds):
'''Initialize an ordered dictionary. The signature is the same as
regular dictionaries. Keyword argument order is preserved.
'''
try:
self.__root
except AttributeError:
self.__hardroot = _Link()
self.__root = root = _proxy(self.__hardroot)
root.prev = root.next = root
self.__map = {}
self.__update(other, **kwds)
def __setitem__(self, key, value,
dict_setitem=dict.__setitem__,
proxy=_proxy, Link=_Link):
'od.__setitem__(i, y) <==> od[i]=y'
# Setting a new item creates a new link at the end of the linked list,
# and the inherited dictionary is updated with the new key/value pair.
'添加新元素的时候会在链表的末尾创建新链表，并使用新的 键值对 更新被继承的字典'
if key not in self:
self.__map[key] = link = Link()
root = self.__root # 哨兵节点
last = root.prev
'''
将root节点作为尾节点，创建新节点，
并更新root节点的前驱节点的后继节点和root节点的前驱节点的指向，
形象一点就是在root 节点前不断的对新节点进行前插（基本链表算法）
'''
link.prev, link.next, link.key = last, root, key
last.next = link
root.prev = proxy(link)
dict_setitem(self, key, value)
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
''' 移除并返回一个键值对，
参数 last 为真就采用 LIFO ，也就是最后一个键值对；
为假就采用 FIFO ，也就是第一个键值对。'''
def popitem(self, last=True):
'''Remove and return a (key, value) pair from the dictionary.
Pairs are returned in LIFO order if last is true or FIFO order if false.
'''
if not self:
raise KeyError('dictionary is empty')
root = self.__root
if last:
link = root.prev
link_prev = link.prev
link_prev.next = root
root.prev = link_prev
else:
link = root.next
link_next = link.next
root.next = link_next
link_next.prev = root
key = link.key
del self.__map[key]
value = dict.pop(self, key)
return key, value
def move_to_end(self, key, last=True):
'''Move an existing element to the end (or beginning if last is false).
Raise KeyError if the element does not exist.
'''
link = self.__map[key]
link_prev = link.prev
link_next = link.next
soft_link = link_next.prev
link_prev.next = link_next
link_next.prev = link_prev
root = self.__root
if last:
last = root.prev
link.prev = last
link.next = root
root.prev = soft_link
last.next = link
else:
first = root.next
link.prev = root
link.next = first
first.prev = soft_link
root.next = link
使用有序字典
1. 创建 collections.OrderedDict()
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
dic['k3'] = 'v3'
print(dic)
2. 清空 dic.clear()
dic.clear()
3. 拷贝 dic.copy()
dic_copy = dic.copy()
4. fromkeys( key_list, value)
import collections
dic = collections.OrderedDict() # OrderedDict()
name = ['A','B','C']
new_dic = dic.fromkeys(name) # OrderedDict([('A', None), ('B', None), ('C', None)])
new_dic_val = dic.fromkeys(name,777) # OrderedDict([('A', 777), ('B', 777), ('C', 777)])
print(dic)
print(new_dic)
print(new_dic_val)
5. 键值对的列表items() / 键keys() / 值 values()
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
print(dic.items()) # odict_items([('k1', 'v1'), ('k2', 'v2')])
print(dic.keys()) # odict_keys(['k1', 'k2'])
print(dic.values()) # odict_values(['v1', 'v2'])
6. move_to_end(key)(指定一个key，把对应的key-value移到最后)
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
dic.move_to_end('k1')
print(dic)
# OrderedDict([('k2', 'v2'), ('k1', 'v1')])
7. pop(key)(获取指定key的value，删除)
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
dic['k3'] = 'v3'
k = dic.pop('k2')
print(k,dic)
#v2 OrderedDict([('k1', 'v1'), ('k3', 'v3')])
8.popitem() (后进先出弹出最后元素，返回 key 和 value)
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
dic['k3'] = 'v3'
print(dic.popitem(),dic)
print(dic.popitem(),dic)
# ('k3', 'v3') OrderedDict([('k1', 'v1'), ('k2', 'v2')])
# ('k2', 'v2') OrderedDict([('k1', 'v1')])
9.setdefault(key)(获取指定key的value，如果key不存在，则创建)
import collections
dic = collections.OrderedDict()
dic['k1'] = 'v1'
dic['k2'] = 'v2'
dic['k3'] = 'v3'
val = dic.setdefault('k5')
print(val,dic)
# None OrderedDict([('k1', 'v1'), ('k2', 'v2'), ('k3', 'v3'), ('k5', None)])
网友评论