python中字典的內部實現原理是什么

這期內容當中小編將會給大家帶來有關python中字典的內部實現原理是什么，文章內容豐富且以專業的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

python 的字典內部使用的數據結構是 hash 表

一、hash 表相關概念

哈希表其實是一個稀疏數組（總是有空白元素的數組稱為稀疏數組）。它是一種根據關鍵碼值（Key-value）直接訪問在內存存儲位置的數據結構。

哈希函數：也稱為是散列函數，是Hash表的映射函數，它可以把任意長度的輸入變換成固定長度的輸出，該輸出就是哈希值。通過使用哈希函數來確定元素在哈希表的存儲位置，哈希函數能使對一個數據序列的訪問過程變得更加迅速有效，通過哈希函數，數據元素能夠被很快的進行定位。

散列表里的單元通常叫作表元（bucket）。在 dict 的散列表當中，每個鍵值對都占用一個表元，每個表元都有兩個部分，一個是對鍵的引用，另一個是對值的引用。因為所有表元的大小一致，所以可以通過偏移量來讀取某個表元。

二、字典dict查找值的原理

通過字典的 key 來獲取其 value值可以通過 dict.get(key) 或者 dict[key]來查找，但是其內部實現原理是怎樣的呢？

Python 首先會調用hash(search_key)來計算 search_key 的散列值，把這個值最低的幾位數字當作偏移量，在散列表里查找表元（具體取幾位，得看當前散列表的大小）。若找到的表元是空的，則拋出KeyError 異常。若不是空的，則表元里會有一對 found_key:found_value。這時候 Python 會檢驗 search_key == found_key 是否為真，如果它們相等的話，就會返回 found_value。

如果 search_key 和 found_key 不匹配的話，這種情況稱為散列沖突。發生這種情況是因為，散列表所做的其實是把隨機的元素映射到只有幾位的數字上，而散列表本身的索引又只依賴于這個數字的一部分。為了解決散列沖突，算法會在散列值中另外再取幾位，然后用特殊的方法處理一下，把新得到的數字再當作索引來尋找表元。若這次找到的表元是空的，則同樣拋出 KeyError；若非空，或者鍵匹配，則返回這個值；或者又發現了散列沖突，則重復以上的步驟。

三、字典dict新增和修改

字典添加新元素和更新現有鍵值的操作幾乎跟查找操作一樣。只不過對于新增，在發現空表元的時候會放入一個新元素；對于更新操作，在找到相對應的表元后，原表里的值對象會被替換成新值。

另外在插入新值時，Python 可能會按照散列表的擁擠程度來決定是否要重新分配內存為它擴容。如果增加了散列表的大小，那散列值所占的位數和用作索引的位數都會隨之增加，這樣做的目的是為了減少發生散列沖突的概率。

四、字典dict的特點總結

由于字典使用了散列表，而散列表又必須是稀疏的，這導致它在空間上的效率低下。舉例而言，如果你需要存放數量巨大的記錄，那么放在由元組或是具名元組構成的列表中會是比較好的選擇；最好不要根據 JSON 的風格，用由字典組成的列表來存放這些記錄。用元組取代字典就能節省空間的原因有兩個：

其一是避免了散列表所耗費的空間，

其二是無需把記錄中字段的名字在每個元素里都存一遍。

dict 的實現是典型的空間換時間：字典類型有著巨大的內存開銷，但它們提供了無視數據量大小的快速訪問——只要字典能被裝在內存里。

無論何時往字典里添加新的鍵，Python 解釋器都可能做出為字典擴容的決定。擴容導致的結果就是要新建一個更大的散列表，并把字典里已有的元素添加到新表里。這個過程中可能會發生新的散列沖突，導致新散列表中鍵的次序變化。

上面提到的這些變化是否會發生以及如何發生，都依賴于字典背后的具體實現，因此你不能很自信地說自己知道背后發生了什么。如果你在迭代一個字典的所有鍵的過程中同時對字典進行修改，那么這個循環很有可能會跳過一些鍵——甚至是跳過那些字典中已經有的鍵。

上述就是小編為大家分享的python中字典的內部實現原理是什么了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。