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

比如，對(duì)于一個(gè)無(wú)序字典，插入順序和遍歷的順序是不一致的：

>>> 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

而一個(gè)有序字典的輸出是這樣的：

name lowman
age 26
girl Tailand
money 80
hourse None

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

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

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

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

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

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

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

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

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

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

最后：

如果你對(duì) Python 解釋器的實(shí)現(xiàn)感興趣，可以閱讀 CPython 的源碼，源碼之下無(wú)秘密，閱讀源碼也是提升自己最快的學(xué)習(xí)方式，這里推薦一個(gè)學(xué)習(xí) CPython 的開(kāi)源倉(cāng)庫(kù) CPython-Internals，圖文注釋并茂，是非常有價(jià)值的學(xué)習(xí)資源

到此這篇關(guān)于Python3.6 之后字典是有序的?的文章就介紹到這了,更多相關(guān)Python字典有序性?xún)?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論