在Python 3.5（含）以前，字典是不能保證順序的，鍵值對A先插入字典，鍵值對B后插入字典，但是當(dāng)你打印字典的Keys列表時，你會發(fā)現(xiàn)B可能在A的前面。

但是從Python 3.6開始，字典是變成有順序的了。你先插入鍵值對A，后插入鍵值對B，那么當(dāng)你打印Keys列表的時候，你就會發(fā)現(xiàn)B在A的后面。

不僅如此，從Python 3.6開始，下面的三種遍歷操作，效率要高于Python 3.5之前：

for key in 字典

for value in 字典.values()

for key, value in 字典.items()

從Python 3.6開始，字典占用內(nèi)存空間的大小，視字典里面鍵值對的個數(shù)，只有原來的30%~95%。

Python 3.6到底對字典做了什么優(yōu)化呢？為了說明這個問題，我們需要先來說一說，在Python 3.5（含）之前，字典的底層原理。

當(dāng)我們初始化一個空字典的時候，CPython的底層會初始化一個二維數(shù)組，這個數(shù)組有8行，3列，如下面的示意圖所示：

my_dict = {}

'''
此時的內(nèi)存示意圖
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---]]
'''

現(xiàn)在，我們往字典里面添加一個數(shù)據(jù)：

my_dict['name'] = 'kingname'

'''
此時的內(nèi)存示意圖
[[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指針, 指向kingname的指針],
[---, ---, ---],
[---, ---, ---]]
'''

這里解釋一下，為什么添加了一個鍵值對以后，內(nèi)存變成了這個樣子：

首先我們調(diào)用Python 的hash函數(shù)，計算name這個字符串在當(dāng)前運行時的hash值：

>>> hash('name')
1278649844881305901

特別注意，我這里強調(diào)了『當(dāng)前運行時』，這是因為，Python自帶的這個hash函數(shù)，和我們傳統(tǒng)上認(rèn)為的Hash函數(shù)是不一樣的。Python自帶的這個hash函數(shù)計算出來的值，只能保證在每一個運行時的時候不變，但是當(dāng)你關(guān)閉Python再重新打開，那么它的值就可能會改變，如下圖所示：

假設(shè)在某一個運行時里面，hash('name')的值為1278649844881305901?，F(xiàn)在我們要把這個數(shù)對8取余數(shù)：

>>> 1278649844881305901 % 8
5

余數(shù)為5，那么就把它放在剛剛初始化的二維數(shù)組中，下標(biāo)為5的這一行。由于name和kingname是兩個字符串，所以底層C語言會使用兩個字符串變量存放這兩個值，然后得到他們對應(yīng)的指針。于是，我們這個二維數(shù)組下標(biāo)為5的這一行，第一個值為name的hash值，第二個值為name這個字符串所在的內(nèi)存的地址（指針就是內(nèi)存地址），第三個值為kingname這個字符串所在的內(nèi)存的地址。

現(xiàn)在，我們再來插入兩個鍵值對：

my_dict['age'] = 26
my_dict['salary'] = 999999

'''
此時的內(nèi)存示意圖
[[-4234469173262486640, 指向salary的指針, 指向999999的指針],
[1545085610920597121, 執(zhí)行age的指針, 指向26的指針],
[---, ---, ---],
[---, ---, ---],
[---, ---, ---],
[1278649844881305901, 指向name的指針, 指向kingname的指針],
[---, ---, ---],
[---, ---, ---]]
'''

那么字典怎么讀取數(shù)據(jù)呢？首先假設(shè)我們要讀取age對應(yīng)的值。

此時，Python先計算在當(dāng)前運行時下面，age對應(yīng)的Hash值是多少：

>>> hash('age')
1545085610920597121

余數(shù)為1，那么二維數(shù)組里面，下標(biāo)為1的這一行就是需要的鍵值對。直接返回這一行第三個指針對應(yīng)的內(nèi)存中的值，就是age對應(yīng)的值26。

當(dāng)你要循環(huán)遍歷字典的Key的時候，Python底層會遍歷這個二維數(shù)組，如果當(dāng)前行有數(shù)據(jù)，那么就返回Key指針對應(yīng)的內(nèi)存里面的值。如果當(dāng)前行沒有數(shù)據(jù)，那么就跳過。所以總是會遍歷整個二位數(shù)組的每一行。

每一行有三列，每一列占用8byte的內(nèi)存空間，所以每一行會占用24byte的內(nèi)存空間。

由于Hash值取余數(shù)以后，余數(shù)可大可小，所以字典的Key并不是按照插入的順序存放的。

注意，這里我省略了與本文沒有太大關(guān)系的兩個點：

1. 開放尋址，當(dāng)兩個不同的Key，經(jīng)過Hash以后，再對8取余數(shù)，可能余數(shù)會相同。此時Python為了不覆蓋之前已有的值，就會使用開放尋址技術(shù)重新尋找一個新的位置存放這個新的鍵值對。
2. 當(dāng)字典的鍵值對數(shù)量超過當(dāng)前數(shù)組長度的2/3時，數(shù)組會進(jìn)行擴(kuò)容，8行變成16行，16行變成32行。長度變了以后，原來的余數(shù)位置也會發(fā)生變化，此時就需要移動原來位置的數(shù)據(jù)，導(dǎo)致插入效率變低。

在Python 3.6以后，字典的底層數(shù)據(jù)結(jié)構(gòu)發(fā)生了變化，現(xiàn)在當(dāng)你初始化一個空的字典以后，它在底層是這樣的：

my_dict = {}

'''
此時的內(nèi)存示意圖
indices = [None, None, None, None, None, None, None, None]

entries = []
'''

當(dāng)你初始化一個字典以后，Python單獨生成了一個長度為8的一維數(shù)組。然后又生成了一個空的二維數(shù)組。

現(xiàn)在，我們往字典里面添加一個鍵值對：

my_dict['name'] = 'kingname'

'''
此時的內(nèi)存示意圖
indices = [None, 0, None, None, None, None, None, None]

entries = [[-5954193068542476671, 指向name的指針, 執(zhí)行kingname的指針]]
'''

為什么內(nèi)存會變成這個樣子呢？我們來一步一步地看：

在當(dāng)前運行時，name這個字符串的hash值為-5954193068542476671，這個值對8取余數(shù)是1：

>>> hash('name')
-5954193068542476671
>>> hash('name') % 8
1

所以，我們把indices這個一維數(shù)組里面，下標(biāo)為1的位置修改為0。

這里的0是什么意思呢？0是二位數(shù)組entries的索引。現(xiàn)在entries里面只有一行，就是我們剛剛添加的這個鍵值對的三個數(shù)據(jù)：name的hash值、指向name的指針和指向kinganme的指針。所以indices里面填寫的數(shù)字0，就是剛剛我們插入的這個鍵值對的數(shù)據(jù)在二位數(shù)組里面的行索引。

好，現(xiàn)在我們再來插入兩條數(shù)據(jù)：

my_dict['address'] = 'xxx'
my_dict['salary'] = 999999

'''
此時的內(nèi)存示意圖
indices = [1, 0, None, None, None, None, 2, None]

entries = [[-5954193068542476671, 指向name的指針, 執(zhí)行kingname的指針],
     [9043074951938101872, 指向address的指針，指向xxx的指針],
     [7324055671294268046, 指向salary的指針, 指向999999的指針]
     ]
'''

現(xiàn)在如果我要讀取數(shù)據(jù)怎么辦呢？假如我要讀取salary的值，那么首先計算salary的hash值，以及這個值對8的余數(shù)：

>>> hash('salary')
7324055671294268046
>>> hash('salary') % 8
6

那么我就去讀indices下標(biāo)為6的這個值。這個值為2.

然后再去讀entries里面，下標(biāo)為2的這一行的數(shù)據(jù)，也就是salary對應(yīng)的數(shù)據(jù)了。

新的這種方式，當(dāng)我要插入新的數(shù)據(jù)的時候，始終只是往entries的后面添加數(shù)據(jù)，這樣就能保證插入的順序。當(dāng)我們要遍歷字典的Keys和Values的時候，直接遍歷entries即可，里面每一行都是有用的數(shù)據(jù)，不存在跳過的情況，減少了遍歷的個數(shù)。

老的方式，當(dāng)二維數(shù)組有8行的時候，即使有效數(shù)據(jù)只有3行，但它占用的內(nèi)存空間還是 8 * 24 = 192 byte。但使用新的方式，如果只有三行有效數(shù)據(jù)，那么entries也就只有3行，占用的空間為3 * 24 =72 byte，而indices由于只是一個一維的數(shù)組，只占用8 byte，所以一共占用 80 byte。內(nèi)存占用只有原來的41%。

參考：[ Python-Dev] More compact dictionaries with faster iteration

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，謝謝大家對腳本之家的支持。

最新評論