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) 的空間複雜度。
