[python] dict內存是如何擴張的

來自專欄 雲在西湖月在天

python的dict是一個哈希表,隨著插入的增加, 哈希表也跟著擴張.為什麼要研究dict呢?因為我們想知道dict的性能和內存的平衡,以便我們在不同的情況下衡量做出調整,比如常見的就是策劃同學的數據表,初始化以後就不會變動了,這個情況下是不是有辦法優化呢?

那我們看看dict內存擴張的具體規則:

何時擴張呢?

*已經使用的槽(slot),超過哈希表整個大小的2/3,那就需要擴張.

如何擴張呢?

*已使用的大小*4(如果已使用超過50000,那就*2),這個值叫minused.然後從初始大小開始,找一個何時值,要比minused大,如果小於,就乘2.

就是這麼簡單.

來看一眼測試代碼

a = {}last_len = 0last_size = 0for i in xrange(1, 500000): a[i] = i new_len = len(a) new_size = dict.__sizeof__(a) if last_size == new_size: # pass pass else: print "
" print "dict size change: old (%s) new (%s) " % (last_size, new_size) print "dict len : old(%s) new(%s)" % (last_len, new_len) last_size = new_size last_len = new_len

看一下輸出:

dict size change: old (0) new (248) dict len : old(0) new(1)dict size change: old (248) new (1016) dict len : old(5) new(6)dict size change: old (1016) new (3320) dict len : old(21) new(22)dict size change: old (3320) new (12536) dict len : old(85) new(86)dict size change: old (12536) new (49400) dict len : old(341) new(342)dict size change: old (49400) new (196856) dict len : old(1365) new(1366)dict size change: old (196856) new (786680) dict len : old(5461) new(5462)dict size change: old (786680) new (3145976) dict len : old(21845) new(21846)dict size change: old (3145976) new (6291704) dict len : old(87381) new(87382)dict size change: old (6291704) new (12583160) dict len : old(174762) new(174763)dict size change: old (12583160) new (25166072) dict len : old(349525) new(349526)

--------------------------------------------------------------

我們來黑盒分析一下這個過程:(因為沒有辦法直接拿到dict的哈希槽的大小,只能拿到size,size是算了指針大小,具體怎麼算的先不貼源碼了,佔地方)

插入第一個, len是1, size是248. 即初始值, 槽的數量num是初始值8個.

插入第二個,len是2, size是248. num是8. 因為沒有超過2/3, 即 2 < (8*2/3)

......

插入第六個以後, len是6, 這個時候, 6 > (8*2/3), 所以要調整大小了.6 < 50000, 所以*4, 是24. 從8開始找一個大於24的值,依次是16(<24), 32(>24)成立,所以調整以後, num是32, size是1016

.....

插入第22個以後, 22 > (32 * 2/3), 調整. 22 < 50000, 所以 *4, 是 88. 從8開始找大於88的值,依次是 16, 32, 64, 128.那就是128了.num是128, size是3320.

...

插入第86個以後,86>(128*2/3),調整. 86 < 50000, 所以*4, 是344, 從8開始找大於344的值,依次是 16,32,64,128,256,512.那就是512了,num是512, size是12536.

...

插入第342以後,342>(512*2/3),調整,342<50000,所以*4,是1368, 從8開始找大於1368的值,依次是8,16,32,64,128,256,512,1024,2048.就是2048了,num是2048,size是49400.

哎呀,好累.

總之就是這個規則了,只是從50000那裡開始,從*4變成*2.

從前面這裡可以看出len在6,22,86,342,1366,5462, 基本上就是*4,size也基本上*4擴張.這個裡面還是有點區別的,比如一個1366個元素的dict和一個5461個元素的dict,size是一樣的.

這說明了,還是有搞頭的.具體怎麼搞呢?看情況吧,原則還是書上說的,空間換時間,或者時間換空間.

-----------------------------------------------------------------------------------------------------------------------

大腦啊,旋轉吧!

剛開始那個問題,我們來這麼搞吧.

我們的目標是盡量使策劃表佔用的內存小,同時性能犧牲一點也可以.

那麼原則是什麼呢?時間換空間.

導表出來初始結果假設是:

data = {1:{1:2, 2:1, 3:1},2:{1:1, 2:2, 3:3},......999999:{1:99, 2:99, 3:99}}

那麼導表出來,就乾脆不用dict了.換成一個tuple.那麼如何訪問呢?就不能使用key了?那不是沒用么?

有個高人說過:"來來來,我們在中間加一層,就可以解決一切問題"

那麼我們換個方式,把這個dict的內容,拆開兩部分.什麼意思呢? 就是把dict的結構暴漏出來讓我們來搞.也就是用hash(key) % num來做key. num是分配的tuple長度.

比如說,現在有999999個key,我們分配長度110000的一個tuple.然後怎麼辦呢. hash(key) % 110000作為位置.如果衝突了,那就append在一起.那就是把一個鏈式的hash結構暴漏出來:

那麼我們假設999999的位置算出來和1衝突了,那麼導表就變成:

data = [

[{id:1, 1:2, 2:1, 3:1}, {id:999999, 1:99, 2:99, 3:99}]

[{id:2, 1:1, 2:2, 3:3}, ]

]

訪問的時候, 算一下 hash(key)%num, 去訪問了. 這樣相當於是在python層實現了一個hash表.那訪問速度自然就慢了.

這種使用什麼情況呢?

一般來說策劃的表的主鍵編號都是從1往上走的.這種都是很實用的.比如從1到9999999,分配9999999空間一點都不浪費啊!!!如果主鍵編號比較亂,那衝突的可能就比較大.那就難說了.

恩,有道理,讓我來把這篇文章加到公司文檔里去.

推薦閱讀：