[toc]

OrderedDict 最大的特征:相较于普通字典,OrderedDict 会记录键值对插入到字典中的顺序。

要点

  1. 在 Python 3.6 之前,普通字典并不记录插入顺序,迭代时的顺序受散列表的散列函数的影响。[1]
  2. 在 Python 3.6 以及之后,内置的普通字典也记录插入顺序,但是这个 feature 是实现的方式变更后的副产品,不建议使用。[1]
  3. 在判断两个 OrderedDict 相等时,不仅需要元素相同,而且元素的插入顺序也要是一样。[1]
  4. 可以使用 move_to_end 将某个元素移到头部或者尾部。[1]

代码实现

思路

代码见此:Sourcegraph

主要思路:构建了一个双端循环链表(circular doubly linked list),初始化时一个哨兵元素(sentinel element),这个元素不会被删除。

每当需要插入一个元素时,元素的 key 将添加到链表尾部

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
        link.prev, link.next, link.key = last, root, key
        last.next = link
        root.prev = proxy(link)
    dict_setitem(self, key, value)

待解决问题

  1. sentinel element 这个设计为什么能够简化算法?
  2. weakref proxy 如何避免循环引用?

ref