Python 有序字典的实现

2019 年 11 月 29 日
筆記

最近在看 requests 源码的时候看到作者使用了 urllib3 中自己实现的OrderedDict类，收获颇多。自己实现一个数据结构往往是最需要算法和优化的地方，各种语法糖黑科技，相当的 Pythonic，看这种代码实在是一种享受。如果要我自己实现的话，自己会想到用一个有序存储的对象（如列表）去 hack 内部的实现，但这样有几个缺点：

列表的插入、删除操作性能不如字典，复杂度是 O(N) 量级的。
自定义类需要继承于dict，没有利用继承的方法特性。

来看看大神是怎么实现的吧。

`init`方法

Python

class OrderedDict(dict):      def __init__(self, *args, **kwds):          if len(args) > 1:              raise TypeError('expected at most 1 arguments, got %d' % len(args))          try:              self.__root          except AttributeError:              self.__root = root = []                     # sentinel node              root[:] = [root, root, None]              self.__map = {}          self.__update(*args, **kwds)

在上一篇文章中说到一些关于列表的坑，说到不要用a=b=[]这样的语句来初始化，其实也不全然，我们来看 7-8 行做了什么。第 7 行使self.__root和root同时指向一个空列表，相关于给self.__root起了一个短别名，关键是第 8 行：

Python

>>> root[:] = [root, root, None]  >>> root  [[...], [...], None]

什么鬼？没见过[...]这种的啊，我来看看

Python

>>> root[0]  [[...], [...], None]  >>> root[0] is root  True

What? 自己是自己的元素？简直是从前有座山山上有座庙啊，子子孙孙无穷尽啊。到底发生了什么事？Python 中万物皆指针，而root[:]=...的赋值是不改变指针指向的地址而是改变指向地址的内容。右边第一个和第二个元素是指向自己的指针，这样就构造了一个我中有我的列表。

再看命名，明白了，这是一个双向链表！列表的前两个元素分别指向上一个结点和下一个结点，第三个元素是结点的值。只用两行就初始化了一个链表，学到了。另外还初始化了一个字典，暂时不知道有什么用。

`setitem`方法

Python

def __setitem__(self, key, value, dict_setitem=dict.__setitem__):      'od.__setitem__(i, y) <==> od[i]=y'      # Setting a new item creates a new link which goes at the end of the linked      # list, and the inherited dictionary is updated with the new key/value pair.      if key not in self:          root = self.__root          last = root[0]          last[1] = root[0] = self.__map[key] = [last, root, key]      dict_setitem(self, key, value)

关键的部分到了，这个魔法方法加了第三个参数来方便子类扩展。函数体部分，画一个图就明白了。

root的上一个结点就是末结点，保存为last。
创建一个新结点，它的上结点和下结点分别设为last和root，结点的值为字典的键。
将last的下结点和root的上结点指向该结点。
将结点加入__map并加入字典。

这样创建就结点就变成了新的末结点了。从此也可看出，root是一个守护结点，本身并不存储值，但会简化算法。__map 是结点的哈希表，避免了从头开始寻找所需的结点。

`delitem`方法

Python

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 is      # then removed by updating the links in the predecessor and successor nodes.      dict_delitem(self, key)      link_prev, link_next, key = self.__map.pop(key)      link_prev[1] = link_next      link_next[0] = link_prev

删除结点时，从哈希表中弹出该结点，然后将它的上结点和下结点相连，并从字典中删除。

实现了这三个方法，剩下的就好办了，__iter__只需从头开始遍历链表并取出键值就可以了。

总结

实现有序字典的关键在于选取一个合适的数据结构来存储顺序信息，这里作者使用了双向链表，然后把结点哈希。这样进行插入、删除操作的时间复杂度为 O(1) ，与dict类型一致，代价就是 O(2n) 的空间复杂度。