為什么 Python3.6 之后字典是有序的

字典的本質(zhì)就是 hash 表，hash 表就是通過 key 找到其 value ，平均情況下你只需要花費 O(1) 的時間復(fù)雜度即可以完成對一個元素的查找，字典是否有序，并不是指字典能否按照鍵或者值進行排序，而是字典能否按照插入鍵值的順序輸出對應(yīng)的鍵值。

比如，對于一個無序字典，插入順序和遍歷的順序是不一致的：

>>>?my_dict?=?dict()
>>>?my_dict["name"]?=?"lowman"
>>>?my_dict["age"]?=?26
>>>?my_dict["girl"]?=?"Tailand"
>>>?my_dict["money"]?=?80
>>>?my_dict["hourse"]?=?None
>>>?for?key，value?in?my_dict.items():
...?????print(key，value)
...
money?80
girl?Tailand
age?26
hourse?None
name?lowman

而一個有序字典的輸出是這樣的：

name?lowman
age?26
girl?Tailand
money?80
hourse?None

那為什么 Python3.6 之后，Python 的字典就有序了呢？

先從 Python3.6 之前說起。在 Python 3.6 之前，其數(shù)據(jù)結(jié)構(gòu)如下圖所示：

由于不同鍵的哈希值不一樣，哈希表（entries）中的順序是按照哈希值大小排序的，遍歷時從前往后遍歷并不能輸出鍵值插入的順序，其表現(xiàn)起來就是無序的。

此外，這種方式還有一個缺點，就是如果以稀疏的哈希表存儲時，會浪費較多的內(nèi)存空間，Python3.6 之后，對其進行了優(yōu)化，哈希索引和真正的鍵值對分開存放，數(shù)據(jù)結(jié)構(gòu)如下所示：

indices 指向了一列索引，entries 指向了原本的存儲哈希表內(nèi)容的結(jié)構(gòu)。

你可以把 indices 理解成新的簡化版的哈希表，entries 理解成一個數(shù)組，數(shù)組中的每個元素是原本應(yīng)該存儲的哈希結(jié)果：鍵和值。

查找或者插入一個元素的時候，根據(jù)鍵的哈希值結(jié)果取模 indices 的長度，就能得到對應(yīng)的數(shù)組下標(biāo)，再根據(jù)對應(yīng)的數(shù)組下標(biāo)到 entries 中獲取到對應(yīng)的結(jié)果，比如 hash("key2") % 8 的結(jié)果是 3，那么 indices[3] 的值是 1，這時候到 entries 中找到對應(yīng)的 entries[1] 既為所求的結(jié)果：

這么做的好處是空間利用率得到了較大的提升，我們以 64 位操作系統(tǒng)為例，每個指針的長度為 8 字節(jié)，則原本需要 8 * 3 * 8 為 192

現(xiàn)在變成了 8 * 3 * 3 + 1 * 8 為 80，節(jié)省了 58% 左右的內(nèi)存空間，如下圖所示：

此外，由于 entries 是按照插入順序進行插入的數(shù)組，對字典進行遍歷時能按照插入順序進行遍歷，這也是為什么 Python3.6 以后的版本字典對象是有序的原因。

最后

如果你對 Python 解釋器的實現(xiàn)感興趣，可以閱讀 CPython 的源碼，源碼之下無秘密，閱讀源碼也是提升自己最快的學(xué)習(xí)方式，這里推薦一個學(xué)習(xí) CPython 的開源倉庫 CPython-Internals^[1]，圖文注釋并茂，是非常有價值的學(xué)習(xí)資源。如果本文對你有幫助，還請點贊關(guān)注哈。

參考資料