python 字典底層實現原理
python字典底層是通過哈希表來實現的，也就是所字典底層也是一個列表，當我們用字典當中的`key`去獲取對應的`value`時，會將`key`轉換為列表當中的`index`，通過`index`去準確快速的獲取到`value`，哈希表的時間複雜度為O(1)。
哈希表（散列表）
哈希表是一種以 `key-value`存儲數據的結構，我們只需要輸入需要查找數據的`key`,就能查找到對應的`value`
哈希表思路是如果`key`是整數，那麼就將`key`作為列表中的下標，存儲到該位置。例如`{2:'a'}`，實際存儲到列表當中就是`dictList[2]='a'`。如果`key`不是整數，那麼就通過一個函數來將`key`轉為數字，並存儲到數組中，這個函數就是哈希函數，這個列表就是哈希表
使用哈希查找有兩個步驟:
1. 使用哈希函數將被查找的鍵轉換為數組的索引。在理想的情況下，不同的鍵會被轉換為不同的索引值，但是在有些情況下我們需要處理多個鍵被哈希到同一個索引值的情況。所以哈希查找的第二個步驟就是處理衝突
2. 處理哈希衝突。有很多處理哈希碰撞衝突的方法，通常有兩種，一種是鏈接法，另外一種是開放尋址法。python採用的是開放尋址法
開放尋址法
開放尋址法通常有兩種實現方式:
1. 線性尋址
當產生哈希衝突時，就查詢該列表的相鄰的下一個位置，如果下一個位置已經存入了數據，那麼就不斷的通過探測函數往下尋找，直到找到一個空槽來存放待插入的元素
2. 二次探測（python 採用的方法）
當產生哈希衝突時，通過一個探測函數計算出下一個候選位置，如果下一個候選位置還是又衝突，那麼就不斷的通過探測函數往下尋找，直到找到一個空槽來存放待插入的元素
鏈接法
當產生哈希衝突時，將產生哈希衝突的數據通過鏈表的形式，鏈接在一起，當查詢數據時，通過哈希函數會定位到這個鏈表，然後通過比較`key`來找到對應的數據
閱讀更多 熱衷python和前端 的文章
