如何實現python dict

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

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

dict底層實現

在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 dict了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業資訊頻道。