dict底層實現

在Python中，字典是依靠散列表或說哈希表(Hash Table)進行實現的，使用開放地址法解決沖突。所以其查找的時間復雜度會是O(1)，下文會具體講解哈希表的工作原理和解決沖突時的具體方法。

也就是說，字典也是一個數組，但數組的索引是鍵經過哈希函數處理后得到的散列值。哈希函數的目的是使鍵均勻地分布在數組中，并且可以在內存中以O(1)的時間復雜度進行尋址，從而實現快速查找和修改。哈希表中哈希函數的設計困難在于將數據均勻分布在哈希表中，從而盡量減少哈希碰撞和沖突。由于不同的鍵可能具有相同的哈希值，即可能出現沖突，高級的哈希函數能夠使沖突數目最小化。

通常情況下建立哈希表的具體過程如下：

數據添加：把key通過哈希函數轉換成一個整型數字，然后就將該數字對數組長度進行取余，取余結果就當作數組的下標，將value存儲在以該數字為下標的數組空間里。

數據查詢：再次使用哈希函數將key轉換為對應的數組下標，并定位到數組的位置獲取value

哈希函數就是一個映射，因此哈希函數的設定很靈活，只要使得任何關鍵字由此所得的哈希函數值都落在表長允許的范圍之內即可。本質上看哈希函數不可能做成一個一對一的映射關系，其本質是一個多對一的映射，這也就引出了下面一個概念–哈希沖突或者說哈希碰撞。哈希碰撞是不可避免的，但是一個好的哈希函數的設計需要盡量避免哈希碰撞。

Python2中使用使用開放地址法解決沖突。

CPython使用偽隨機探測(pseudo-random probing)的散列表(hash table)作為字典的底層數據結構。由于這個實現細節，只有可哈希的對象才能作為字典的鍵

哈希表

哈希表是key-value類型的數據結構，通過關鍵碼值直接進行訪問。通過散列函數進行鍵和數組的下標映射從而決定該鍵值應該放在哪個位置，哈希表可以理解為一個鍵值需要按一定規則存放的數組，而哈希函數就是這個規則。此處提出幾個專業名詞后面會一一進行介紹。

哈希函數

裝填因子

沖突

1.哈希表產生的原因假設我們存在一個簡單的鍵值對結構，鍵-員工號，值-是否在崗。現在需要這樣一個功能，輸入員工號，返回該員工是否在崗，理想的方法是創建一個長度為Max(員工號)的數組，數組下標就是員工號，數組中的值用0和1對是否在崗進行區分，這樣只需要O(1)的時間復雜度就可以完成操作，但是擴展性不強，存在以下問題。

假設新進員工的員工號比Max(員工號)還要大，這就需要重新申請數組進行遷移操作。

假設一種極端的情況，存在兩個員工，員工號分別是1和100000000001，這樣子的話按照先前的設計思路，是會浪費很大的存儲空間的。

上面兩點，第一點是因為數組的固定申請大小的屬性所決定，而第二點就是引入哈希表的原因，會不會存在一個方法，讓一個大員工號變小而而且沒有標記，哈希函數便產生，假設此處的哈希規則是除3取模，則員工1得到的哈希值是1，員工100000000001得到的哈希值是

這樣的話按照設計思路，只需要一個大小為2的數組便可以覆蓋了，這就是哈希思想。

算法中時間和空間是不能兼得的，哈希表就是一種用合理的時間消耗去減少大量空間消耗的操作，這取決于具體的功能要求。

2. 哈希函數

上面的例子中哈希函數的設計很隨意，但是從這個例子中我們也可以得到信息：

哈希函數就是一個映射，因此哈希函數的設定很靈活，只要使得任何關鍵字由此所得的哈希函數值都落在表長允許的范圍之內即可；

并不是所有的輸入都只對應唯一一個輸出，也就是哈希函數不可能做成一個一對一的映射關系，其本質是一個多對一的映射，這也就引出了下面一個概念–沖突。

3. 沖突

只要不是一對一的映射關系，沖突就必然會發生，還是上面的極端例子，這時新加了一個員工號為2的員工，先不考慮我們的數組大小已經定為2了，按照之前的哈希函數，工號為2的員工哈希值也是2，這與100000000001的員工一樣了，這就是一個沖突，針對不同的解決思路，提出三個不同的解決方法。

4.沖突解決方法

4.1 開放地址

開放地址的意思是除了哈希函數得出的地址可用，當出現沖突的時候其他的地址也一樣可用，常見的開放地址思想的方法有線性探測再散列，二次探測再散列，這些方法都是在第一選擇被占用的情況下的解決方法。

4.2 再哈希法

這個方法是按順序規定多個哈希函數，每次查詢的時候按順序調用哈希函數，調用到第一個為空的時候返回不存在，調用到此鍵的時候返回其值。

4.3 鏈地址法

將所有關鍵字哈希值相同的記錄都存在同一線性鏈表中，這樣不需要占用其他的哈希地址，相同的哈希值在一條鏈表上，按順序遍歷就可以找到。

4.4公共溢出區

其基本思想是：所有關鍵字和基本表中關鍵字為相同哈希值的記錄，不管他們由哈希函數得到的哈希地址是什么，一旦發生沖突，都填入溢出表。

5.裝填因子α

一般情況下，處理沖突方法相同的哈希表，其平均查找長度依賴于哈希表的裝填因子。哈希表的裝填因子定義為表中填入的記錄數和哈希表長度的壁紙，也就是標志著哈希表的裝滿程度。直觀看來，α越小，發生沖突的可能性就越小，反之越大。一般0.75比較合適，涉及數學推導

原文：https://blog.csdn.net/shouting3901/article/details/80468735