python dict怎麼實現的

Python中dict物件是表明了其是一個原始的Python資料類型，按照鍵值對的方式存儲，其中文名字翻譯為字典，顧名思義其透過鍵名查找對應的值會有很高的效率，時間複雜度在常數等級O(1).

#dict底層實作（推薦學習：Python影片教學）

在Python2中，dict的底層是依靠哈希表(Hash Table)進行實現的，使用開放位址法解決衝突.

所以其查找的時間複雜度會是O(1).

Dict的操作實作原理（包含插入、刪除、以及緩衝池等）

首先介紹：PyDictObject物件的元素搜尋策略：

有兩種搜尋策略，分別是lookdict和lookdict_string，lookdict_string就是lookdict在對PyStringObject搜尋時的特殊形式，那麼通用的搜尋策略lookdict的主要邏輯是：

（1）對第一個entry的查找：

a)根據hash值獲得entry的索引

b)若entry處於unused態，則搜尋結束；若entry所指向的key與搜尋的key相同，則搜尋成功

c)若目前entry處於dummy態，則設定freeslot（這裡的freeslot是可以傳回為下一個立即可用的位址來儲存entry）

#d)檢查Active態的entry，若其key所指向的值與搜尋的值相同，則搜尋成功

（2）對剩餘的探測鏈中的元素的遍歷查找：

##a )根據所採用的探測函數，得到探測鏈上的下一個待檢查的entry

b)檢查到一個unused態的entry，表示搜尋失敗：

如果freeslot不為空，則返回freeslot；否則返回unused態的entry

c)檢查entry的key與所搜尋的key的引用是否相同，相同則搜尋成功，返回entry

d)檢查entry的key與搜尋的key的值是否相同，相同則搜尋成功，傳回entry

e)遍歷過程中，發現dummy態的entry，且freeslot未設定，則設定freeslot

#接下來是：PyDictObject物件的元素插入與刪除的策略：

需要先用到搜尋策略，搜尋成功，則直接將值替換，搜尋失敗，傳回unused態或dummy態的entry，設定key、value和hash值，並且根據目前插入的元素情況進行ma_table的大小的調整（調整的依據就是裝載率，根據是否大於2/3來進行調整）；刪除也是類似，先計算hash值，然後搜尋對應的entry，搜尋成功，刪除entry中維護的元素，將entry從Active態修改為dummy態

 

在PyDictObject的實作過程中，會用到緩衝池，在PyDictObject物件被銷毀的時候，才開始接納被緩衝的PyDictObject對象，定義的緩衝池可接納的物件數量是80個，創建新PyDictObject物件的時候，如果緩衝池中有，則可以直接從緩衝池中取出使用

更多Python相關技術文章，請造訪

Python教學欄位進行學習！

以上是python dict怎麼實現的的詳細內容。更多資訊請關注PHP中文網其他相關文章！