python 的 dict真的不會隨著key的增加而變慢嗎？

01-05

廖雪峰python教程上看到:
和list比較，dict有以下幾個特點：
查找和插入的速度極快，不會隨著key的增加而變慢；
需要佔用大量的內存，內存浪費多。
鏈接:http://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/00143167793538255adf33371774853a0ef943280573f4d000

感覺不合常理，所以來問。

你問的問題其實很有價值。這是很多初學數據結構的人的困擾，因為它沒邏輯。憑什麼我多大的數據量，訪問速度都是一樣的？這根本不符合常理。

很多人會告訴你，這是Hash Table，而Hash Table的訪問速度是O(1)的，而對於你來說，這就和沒說一樣。這個答案既不算精確，也沒能回答你的問題。

首先如果你真的想搞清楚這個問題的來龍去脈，你需要搞懂Hash Table到底是什麼東西。Hash Table首先默認了一件事情，在電腦中，讀取或者寫入一個已知地址的內存需要的最大時間是固定的，和有可能寫入內存的長度無關的。

舉個例子，你在家有一個柜子，柜子上有一堆抽屜，你把這些抽屜分別編號為1-10。這時候我和你說，找10號抽屜，你可以立刻找到10號。我說找6號，你可以立刻找到6號。現在你的柜子擴大了，抽屜有100個，我說找56號，你還是可以立刻找到56號。你柜子又大了，變成了1000個抽屜，我說找729號，你依然可以立刻找到729號。

對於人類來說，這是不可能的。隨著抽屜數量的增加，我們找對應抽屜的速度會下降。但是對於現在的計算機來說，這個假設是成立的。這是你要理解的第一點計算機和人類的不同。無論有多少抽屜，只要你說找這個號碼的抽屜，不管是第一個，最後一個，還是中間任何抽屜，計算機的反應速度都一樣。

好，現在假設我們有1000個抽屜，我們有4份文件。每一份文件有一個唯一且不重複的文件編碼，這個編碼是8位碼，比如01303457。我們需要把這四份文件保存到抽屜里，並且希望下次有人來要這些文件的時候，我們可以立刻找到。

我們可以把這四份文件都放到第一個抽屜，然後人來的時候把四個文件找出來，逐一對比文件編碼。這是一種線性數據結構，他的搜索速度和文件的數量是線性關係。我們有100份文件，速度大概是10份的10倍。我們管他叫O(N)。我們可以按照文件編碼先把文件排序，然後都放第一個抽屜里。這樣搜的時候，我們可以利用二分法來找文件。這時候我們的速度提高到了log(N)。隨著文件的增加，我們的搜索時間還是在增加，但是增加的緩慢了。

然而還有一個方法。我們可以看文件的尾號，把他們放進和尾號對應的抽屜里。比如01303457號文件，我們就給他放到457號抽屜。我們可以想像，在文件比較少的時候，我們的每個抽屜很可能只有一份文件。這時候有個人來說我要01303457號文件，我們就可以直接去457號抽屜給她拿。由於我們找一個抽屜的速度時固定的，所以隨著文件的增加，我們搜索文件的時間是沒有增加的。

下面才是重點，也是兩種邏輯產生衝突的地方。如果文件多了，肯定會有抽屜不止兩個文件。最理想的情況下，在有1001份文件的時候，也會有一個抽屜有兩份文件。而最差的情況，所有的文件尾號都一樣，那我們不是回到了第一種方法么？

沒錯！你想的是完全正確的。相信自己的判斷。

很多課在入門數據結構的時候會盡量迴避這個地方，或者一筆帶過，留下莫名其妙的學生們，背下來Hash Table的access是O(1)。而事實上這裡的O(1)是有很多先決條件的。

第一，這是一個平均值，不是最差值。在Worst case下，Hash Table的access時間並非O(1)，是會隨著數據的增長而增長的。也就是說，我們常理上看，雖然有著每一份來的文件編號尾號都一樣的可能性，但是平均上說，他們應該是分的比較開的。而如何把文件盡量分散地對應到相應的抽屜，也是一個學問，這裡不贅言（思考一下如果按照常規的文件編號方法，順序編號，用尾數和用開頭的三位會有什麼不同？）。

第二，你抽屜的數量要遠大於文件的數量。如果你只有10個抽屜，有100份文件，那當然會隨著文件數量的增加，找文件的速度變慢。對於Hash Table也是一個道理，你準備好的內存需要遠大於實際使用的內存。如果你準備迎接100個數據，你可能就要準備400個以上的空位。隨著數據量的增加，為了保證你的讀寫速度還在O(1)，你的內存開銷也會變大。換言之，一個理想Hash Table的讀寫速度確實是O(1)，但是佔用內存是無限大（因此理想Hash Table不存在）。

回到你的問題，在我們正常寫程序的時候，所用到的數據量都不算太大（相對於可支配內存），所以我們可以把dict看作一個理想Hash Table。這時候隨著key的增加，它確實不會變慢（佔用內存變多）。但是到了極端情況，當你的key非常非常非常多的時候（這時候要看他Hash Table的具體實現），他的速度是有可能隨著key的增加而減慢的。

題主這個問題很好，一個簡單的問題，卻能引出許多思考！

其實這個問題應該分開來回答。題主作為初學者，很多基礎概念不明白，所以這裡提到的東西都只是點到為止。隨著你自己學習的深入，可以加深理解。

首先dict是什麼？翻譯過來叫字典。這個概念不值存在於計算機，所以就拿新華字典舉例。新華字典的作用是對每個字，做出解釋。比如「啊」：語氣詞，可表示驚嘆。那這裡的「啊」我們稱之為「key」；「語氣詞。。。。」這部分稱之為「value」。那麼其實字典就是由很多這樣的鍵值對構成的。

接著來看你的問題，隨著鍵值對的增加，訪問會變慢嗎？答案是會也不會！答主可能並沒有接觸過演算法基礎課，所以對時間複雜度沒有概念，這裡不詳細解釋，簡單理解為，"邏輯上的步數，而不是實際的時間"。比如現在要你念兩句詩，因為字數是固定的，所以邏輯時間不管是誰都是一樣；但每個人說話速度不同，所以實際執行時間不同。

繼續回到問題，現在我們有了這麼多鍵值對，要怎麼查找呢？新華字典大家都用過，最前面有一個叫索引的東西，沒錯，我們需要的就是他。

第一種方法，按照拼音順序從頭查到尾，直到找到我們需要的字，我們說這是遍歷，那麼隨著值的增多，查找時間必然變慢。

第二種方法，根據部首，一個字我們可以按照部首順序拆分，往往通過部首組合能更快速的定位一個字。其實這個就有點類似其他答主說的哈希表。通過某種計算方式使用邏輯時間1的速度定位到一個字。

其實還有許多其他方法，但都不是關鍵。索引的構建方式與字典本身沒有關係，這只是一種查找鍵值對的方法。那麼再來看你的問題，如果索引是通過第一種方法，類似list的方式構建，那麼時間會增加，與list相同。如果是第二種，邏輯時間永遠為1，所以不會增加。如果採用其他方法，那麼也有其對應的時間複雜度。

通常為了效率考慮，dict採用的是哈希表的實現方式，然而這裡還可以繼續展開。哈希表需要存儲在內存中，繼續剛才的比喻，由於字太多了，你需要一個非常大的索引表，大到你無法一次性拿到手裡。機智的你想了個辦法，把表分成很多小塊，需要某個小塊時從桌子上拿起來，不需要的就暫時放在桌子上。這就是操作系統的內存分頁，桌子就是虛擬內存，你手上拿著的就是內存中的數據，甚至你腦子裡剛才的瞬時記憶就是cpu緩存！這之間數據的交換都會帶來實際運行時間的損失。

所以你看，一個簡單的問題，引發了數據結構，演算法，操作系統，存儲等等方面的思考，不點個贊嗎？

你需要的是系統性地學習演算法時間複雜度和數據結構的知識，而不是看大V們講一些碎片化的東西

當然會啊。不管你用什麼數據結構，只要你內存用的越來越多，肯定會導致的cache miss增大的，從而讓整體性能下降。如果用的更多，就會開始用硬碟來做內存，那就更慢了（逃。如果還繼續用，你就得修改你的程序的架構，做分散式的東西了。現在內存匯流排變成了網線，慢的一比。

相比起不會數據結構的，我覺得那些學了數據結構然後就覺得係數無所謂的，更不能要。

當然會。雖說理論訪問速度都是O(1)，不過字典大小不同，有得能裝進L1 cache那就和放在main memory的訪問速度不一樣，只是很多應用場景不計較這點損失罷了。

並不是不合常理，這裡的常理是：空間換時間。

例如，你開闢一個大小為100的數組，而且有10個100以內不同的數字。

對於50這個數字，直接將其存到下標為50的位置，讀取時也可以直接作為下標讀取，插入和讀取複雜度都是O(1)。

如果不用空間換時間，你開闢的數組大小為10則足以，但是插入和讀取的複雜度就不是O(1)了。

嚴格的從時間來講，肯定會。

從演算法複雜度上講，不會。

總結來說，相比與列表的數量增加帶來的時間影響，dict數量增加對於時間的影響可以忽略不計。沒有必要那麼咬文嚼字

Python中的dict是使用hash table實現的，hash table的特點高票答案深入淺出的講明白了。作為一個補充，我貼一個在Python的dict中使用key訪問value的流程圖作為補充（出自「流暢的Python」一書）

所謂表元，就是hash table的單元，每個表元有兩個部分，一個是對鍵的引用，一個是對值的引用。Python在處理hash 衝突的時候，會在散列值中再取幾位（最初的時候是通過取hash(search_key)的最低幾位作為偏移量），然後用特殊的方法處理一下，把新得到的數字作為索引來尋找表元。

Python會設法保證大概還有三分之一的表元是空的，在將快達到這個閾值的時候，原有的散列表會被複制到一個更大的空間。

用hash table做查找屬於典型空間換時間的做法。

---

如果看了上面的東西都還不是很清楚，可以看看「老馬說編程」關於集合類的一些博文，講得深入淺出，推薦閱讀。和這個問題掛鉤的博文可以查看下面的鏈接，可以看到java在動態擴容方面和python有異曲同工之妙，在處理hash衝突方面就不一樣了(下面源碼基於jdk1.7)

計算機程序的思維邏輯 (40) - 剖析HashMap

回去找本數據結構的書去看吧。

話說問出這種問題的人，你跟他講L1、虛擬內存、哈希碰撞，聽得懂見鬼了…

哈希表(Hash table，也叫散列表)，是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。例如：給定表M，存在函數f(key)，對任意給定的關鍵字值key，代入函數後若能得到包含該關鍵字的記錄在表中的地址，則稱表M為哈希(Hash)表，函數f(key)為哈希(Hash) 函數。

Python 字典是一種hash table 的實現。

看字典方法時間複雜度。

樓上各位，你們這樣解釋會把小朋友嚇到的。題主只是不理解為什麼字典的查詢時間不會隨著內容的增加而延長。你們解釋一堆原理反而把題主給繞進去了。

其實字典這個東西，你就用現實中查字典去類比就能理解了。

比如delicious，先找d開頭的單詞，在d開頭的單詞裡面找第二個字母為e的單詞，再在所有前兩個字母為de的單詞裡面找第三個字母為l的單詞。如此反覆，直到找到位置。

字典的key經過hash以後，會得到一串很長的類似於a1f3cb42edf97 這樣的hash值。Python首先去找第一個字母為a的所有值，再找在第一個字母為a的情況下的第二個為1的所有值，就跟查字典一樣。

而所有這些key的hash的位數是固定的，假設是32位，那麼不論是任何key，Python都只需要找32次就能找到。

所以查找的時間是固定的。

其實查找和插入可以是兩種優化方向，某種程度上來說還是相互矛盾的，優化了查找，就不能保證插入，優化了插入，就不能保證查找。

關於查找的優化，請自行搜索 Robin-Hood Hashing。

肯定會……你用過c就知道。

SYNOPSIS

#include &

int hcreate(size_t nel);

DESCRIPTION

First a hash table must be created using hcreate(). The argument nel specifies the maximum number of entries in the table. (This maximum cannot be changed later, so choose it wisely.) The implementation may adjust this value upward to improve the performance of the resulting hash table.

不過從數據結構的角度講確實是O(1)的，這就是工程和學術的區別~~

value越多，碰撞概率越大。應該是變慢的。我瞎說的。

段子手表示不懂數據結構，直覺上數據量大了，搜索不會消耗更多能量違反物理定律

上面多位高人都從數據存儲理論方面做出了回答，我就給一個主觀感官型的回答。

把內存看做白幕，當數據足夠大，就會超出你滴視野，這時候你就需要轉頭，去搜尋第二片視野區。這個轉頭的過程是需要時間滴，那麼key增加肯定在變慢

寫一個不一樣一點的答案

當 dict 存的數據的結構稍微複雜一點的時候，當 key 增加到30w~40w，在 Windows 下的 Python 性能已經無法忍受。插入一個 key 的時間是已經能感覺得到了。

在 Linux 下的 Python 沒有這個問題，上 google 搜了一下說是 windows 下的 Python 有這個 bug。

想不慢就消耗更多的內存，沒有免費的午餐

dict中元素的保存位置並不是按照賦值先後按序定的，而是根據key值算出的保存位置來保存數據，不同的key算出的dict中的保存地址是必然不一樣的。可以說key就相當於保存地址的別名了，和數組這種完全不一樣概念。

所以不管什麼key都是運行一個同樣的演算法然後直接根據算出結果就確定了位置去讀取就行了。

～

PS:我不會寫Python，不懂數據結構，也不懂hash，所以上面的話都是胡謅的。

@黃哥如果dict足夠大，二次hash無法定位，後面的定址就不是數組的o(1)了，而是o(