从3.6开始字典都是有序的，并且从3.7开始这成了正式的Python语言特性！！！！！
实现原理 多维护了一个index的列表 用来对应数据存入hashtable的顺序
比如 k1第一个入hashtable 他在table里的索引是2
那么维护的index列表为 [None, None, 0, None, None ......]
k2在hashtable里的索引是0
index列表 [1, None, 0, None, None ......]
有序字典 和 带默认值的字典
collections.OrderedDict 是字典的子类，保存了他们被添加的顺序。
collections.defaultdict 是字典的子类，提供了一个工厂函数，为字典查询提供一个默认值。
以下示例基本来自Python3官方文档，有兴趣的同学可以去看原文档。
有序字典 OrderedDict
注：Python 3.7及以后，默认的 dict 就已经是有序的了，所以 OrderedDict 的作用没有以前那么重要了。
但是 OrderedDict 和 dict 还是有一些不同：
- 常规的
dict被设计为非常擅长映射操作。 跟踪插入顺序是次要的。 -
OrderedDict旨在擅长重新排序操作。 空间效率、迭代速度和更新操作的性能是次要的。 - 算法上，
OrderedDict可以比dict更好地处理频繁的重新排序操作。 这使其适用于跟踪最近的访问（例如在LRU cache中）。 - 对于
OrderedDict，相等操作(即==)检查匹配顺序。
In [190]: a={'a': 3, 'b': 2}
In [191]: b={'b': 2, 'a': 3}
In [192]: a
Out[192]: {'a': 3, 'b': 2}
In [193]: b
Out[193]: {'b': 2, 'a': 3}
In [194]: a==b
Out[194]: True
In [195]: c=OrderedDict({'a': 3, 'b': 2})
In [196]: d=OrderedDict({'b': 2, 'a': 3})
In [197]: c==d
Out[197]: False
-
OrderedDict类的popitem()方法有不同的签名。它接受一个可选参数来指定弹出哪个元素。
OrderedDict.popitem(last=True)
dict 的 popitem() 方法 无需参数
-
OrderedDict类有一个move_to_end()方法，可以有效地将元素移动到任一端。
OrderedDict 的实例方法
-
popitem(last=True)：有序字典的
popitem()方法移除并返回一个(key, value)键值对。 如果last值为真，则按LIFO后进先出的顺序返回键值对，否则就按FIFO先进先出的顺序返回键值对。即：默认弹出最后一个元素的键值对。
In [211]: c=OrderedDict({'a': 3, 'b': 2})
In [212]: c.popitem(True)
Out[212]: ('b', 2)
In [213]: c
Out[213]: OrderedDict([('a', 3)])
- move_to_end(key, last=True)：将现有
key移动到有序字典的任一端。 如果last为真值（默认）则将元素移至末尾；如果last为假值则将元素移至开头。如果 key 不存在则会触发KeyError。
In [214]: d = OrderedDict.fromkeys('abcde')
In [215]: d
Out[215]: OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None)])
# 将b移到末尾
In [216]: d.move_to_end('b')
In [217]: d
Out[217]: OrderedDict([('a', None), ('c', None), ('d', None), ('e', None), ('b', None)])
# 将b移到开头
In [218]: d.move_to_end('b', last=False)
In [219]: d
Out[219]: OrderedDict([('b', None), ('a', None), ('c', None), ('d', None), ('e', None)])
-
OrderedDict的项(item)，键(key)和值(value)视图 现在支持逆序迭代，通过 reversed() 。
In [228]: d = OrderedDict.fromkeys('abcde')
In [229]: d
Out[229]: OrderedDict([('a', None), ('b', None), ('c', None), ('d', None), ('e', None)])
In [230]: list(reversed(d.items()))
Out[230]: [('e', None), ('d', None), ('c', None), ('b', None), ('a', None)]
In [231]: list(reversed(d.keys()))
Out[231]: ['e', 'd', 'c', 'b', 'a']
In [232]: list(reversed(d.values()))
Out[232]: [None, None, None, None, None]
OrderedDict 例子和用法
- 如果新条目覆盖现有条目，则原始插入位置将更改并移至末尾：
class LastUpdatedOrderedDict(OrderedDict):
'Store items in the order the keys were last added'
def __setitem__(self, key, value):
super().__setitem__(key, value)
self.move_to_end(key)
In [242]: l = LastUpdatedOrderedDict.fromkeys('abcde')
In [243]: l
Out[243]:
LastUpdatedOrderedDict([('a', None),
('b', None),
('c', None),
('d', None),
('e', None)])
In [244]: l['a'] = 9
In [245]: l
Out[245]:
LastUpdatedOrderedDict([('b', None),
('c', None),
('d', None),
('e', None),
('a', 9)])
- 一个
OrderedDict对于实现functools.lru_cache()的变体也很有用:
class LRU(OrderedDict):
'Limit size, evicting the least recently looked-up key when full'
def __init__(self, maxsize=128, /, *args, **kwds):
self.maxsize = maxsize
super().__init__(*args, **kwds)
def __getitem__(self, key):
value = super().__getitem__(key)
self.move_to_end(key)
return value
def __setitem__(self, key, value):
if key in self:
self.move_to_end(key)
super().__setitem__(key, value)
if len(self) > self.maxsize:
oldest = next(iter(self))
del self[oldest]
a = LRU(2)
a["a"] = 5
print(a)
a["b"] = 5
print(a)
a["c"] = 5
print(a)
结果：
LRU([('a', 5)])
LRU([('a', 5), ('b', 5)])
LRU([('b', 5), ('c', 5)])
defaultdict 对象
collections.defaultdict([default_factory[, ...]])
对象包含一个名为 default_factory 的属性，构造时，第一个参数用于为该属性提供初始值，默认为 None。所有其他参数（包括关键字参数）都相当于传递给 dict 的构造函数。
defaultdict 例子
使用 list 作为 default_factory，很轻松地将（键-值对组成的）序列转换为（键-列表组成的）字典：
In [250]: s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
In [251]: d = defaultdict(list)
In [252]: for k, v in s:
...: d[k].append(v)
...:
In [253]: d
Out[253]: defaultdict(list, {'yellow': [1, 3], 'blue': [2, 4], 'red': [1]})
In [254]: sorted(d.items())
Out[254]: [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
当每个键第一次遇见时，它还没有在字典里面，所以自动创建该条目，即调用 default_factory 方法，返回一个空的 list。 list.append() 操作添加值到这个新的列表里。当再次存取该键时，就正常操作，list.append() 添加另一个值到列表中。这个计数比它的等价方法 dict.setdefault() 要快速和简单：
In [255]: d = {}
In [256]: for k, v in s:
...: d.setdefault(k, []).append(v)
...:
In [257]: sorted(d.items())
Out[257]: [('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]
设置 default_factory 为 int，使 defaultdict 用于计数：
In [258]: s = 'mississippi'
In [259]: d = defaultdict(int)
In [260]: for k in s:
...: d[k] += 1
...:
In [261]: sorted(d.items())
Out[261]: [('i', 4), ('m', 1), ('p', 2), ('s', 4)]
当一个字母首次遇到时，它会查询失败，则 default_factory 会调用 int() 来提供一个整数 0 作为默认值。后续的自增操作建立起对每个字母的计数。
函数 int() 总是返回 0，这是常数函数的特殊情况。一个更快和灵活的方法是使用 lambda 函数，可以提供任何常量值（不只是0）：
# 可以理解为 字典的默认值为 "<missing>"
In [263]: def constant_factory(value):
...: return lambda: value
...:
In [264]: d = defaultdict(constant_factory('<missing>'))
In [265]: d
Out[265]: defaultdict(<function __main__.constant_factory.<locals>.<lambda>()>, {})
In [266]: d.update(name='John', action='ran')
In [267]: d
Out[267]:
defaultdict(<function __main__.constant_factory.<locals>.<lambda>()>,
{'name': 'John', 'action': 'ran'})
In [268]: '%(name)s %(action)s to %(object)s' % d
Out[268]: 'John ran to <missing>'
设置 default_factory 为 set 使 defaultdict 用于构建 set 集合：
In [272]: s = [('red', 1), ('blue', 2), ('red', 3), ('blue', 4), ('red', 1), ('blue', 4)]
In [273]: d = defaultdict(set)
In [274]: for k, v in s:
...: d[k].add(v)
...:
In [275]: d
Out[275]: defaultdict(set, {'red': {1, 3}, 'blue': {2, 4}})
In [276]: sorted(d.items())
Out[276]: [('blue', {2, 4}), ('red', {1, 3})]
