↑?關注 + 星標?，每天學Python新技能
后臺回復【大禮包】送你Python自學大禮包

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

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

>>>?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 之前，其數據結構如下圖所示：

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

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

indices 指向了一列索引，entries 指向了原本的存儲哈希表內容的結構。

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

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

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

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

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

最后

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

轉自：python七號

參考資料

推薦閱讀
女程序員做了個夢，神評論。。。
人臉識別的時候，一定要穿上衣服，否則 ...
PyCharm vs VSCode，是時候改變你的 IDE 了！
大學生上“暗網”發(fā)現“財富密碼”，結果…