在Python2中，dict的底層用哈希表實現，用開放地址的方法解決沖突。
因此，搜索時間復雜度將為O(1)。
Dict的運行原理(包括插入、刪除、緩沖池等。)
首先介紹PyDictObject的元素搜索策略:
有兩種搜索策略，lookdict和lookdict_string，lookdict _ string是在搜索PyStringObject時lookdict的壹種特殊形式，所以壹般搜索策略lookdict的主要邏輯是:
(1)搜索第壹個條目:
a)根據哈希值獲得條目的索引
b)如果條目處於未使用狀態，則搜索結束；如果條目指向的鍵與搜索到的鍵相同，則搜索成功。
c)如果當前條目處於虛擬狀態，則設置freeslot(這裏的freeslot可以作為存儲條目的下壹個立即可用的地址返回)。
d)檢查活動條目，如果其鍵指向的值與搜索到的值相同，則搜索成功。
(2)在剩余檢測鏈中遍歷搜索元素:
a)根據所采用的檢測函數，獲得檢測鏈上的下壹個待檢查條目
b)檢查未使用的條目，指示搜索失敗:
如果freeslot不為空，則返回free slot；否則，返回未使用狀態的條目。
c)檢查條目的關鍵字和被搜索關鍵字的引用是否相同，如果相同，則搜索成功並返回條目。
d)檢查條目的關鍵字是否與被搜索關鍵字的值相同，如果相同，則搜索成功並返回條目。
e)在遍歷的過程中，如果找到了dummy state的入口並且沒有設置freeslot，則設置freeslot。
接下來是:PyDictObject對象的元素插入和刪除策略:
妳需要首先使用搜索策略。如果搜索成功，您將直接替換該值。如果搜索失敗，則返回到未使用或啞元狀態的條目，設置key、value和hash值，根據當前插入的元素調整ma_table的大小(調整是基於加載速率的，根據是否大於2/3進行調整)。刪除類似，先計算哈希值，再搜索對應的條目。如果搜索成功，則刪除條目中維護的元素，並將條目從活動狀態更改為虛擬狀態。
在實現PyDictObject的過程中，會用到緩沖池。當PyDictObject被銷毀時，緩沖的PyDictObject將被接受。定義的緩沖池可以接受的對象數量是80。創建新的PyDictObject時，如果緩沖池中有，可以直接從緩沖池中取出來使用。
更多Python相關技術文章，請訪問Python教程部分學習！以上是邊肖分享的python dict如何實現的詳細內容。希望對大家有幫助。更多python教程請關註環球常春藤其他相關文章！