如何實(shí)現(xiàn)python dict

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)如何實(shí)現(xiàn)python dict，文章內(nèi)容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

  Python中dict對(duì)象是表明了其是一個(gè)原始的Python數(shù)據(jù)類型，按照鍵值對(duì)的方式存儲(chǔ)，其中文名字翻譯為字典，顧名思義其通過(guò)鍵名查找對(duì)應(yīng)的值會(huì)有很高的效率，時(shí)間復(fù)雜度在常數(shù)級(jí)別O(1).

dict底層實(shí)現(xiàn)

在Python2中，dict的底層是依靠哈希表(Hash Table)進(jìn)行實(shí)現(xiàn)的，使用開放地址法解決沖突.

所以其查找的時(shí)間復(fù)雜度會(huì)是O(1).

Dict的操作實(shí)現(xiàn)原理（包括插入、刪除、以及緩沖池等）

首先介紹：PyDictObject對(duì)象的元素搜索策略：

有兩種搜索策略，分別是lookdict和lookdict_string，lookdict_string就是lookdict在對(duì)于PyStringObject進(jìn)行搜索時(shí)的特殊形式，那么通用的搜索策略lookdict的主要邏輯是：

（1）對(duì)第一個(gè)entry的查找：

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

b)若entry處于unused態(tài)，則搜索結(jié)束；若entry所指向的key與搜索的key相同，則搜索成功

c)若當(dāng)前entry處于dummy態(tài)，則設(shè)置freeslot（這里的freeslot是可以返回作為下一個(gè)立即可用的地址來(lái)存儲(chǔ)entry）

d)檢查Active態(tài)的entry，若其key所指向的值與搜索的值相同，則搜索成功

（2）對(duì)剩余的探測(cè)鏈中的元素的遍歷查找：

a)根據(jù)所采用的探測(cè)函數(shù)，獲得探測(cè)鏈上的下一個(gè)待檢查的entry

b)檢查到一個(gè)unused態(tài)的entry，表明搜索失?。?/p>

如果freeslot不為空，則返回freeslot；否則返回unused態(tài)的entry

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

d)檢查entry的key與所搜索的key的值是否相同，相同則搜索成功，返回entry

e)遍歷過(guò)程中，發(fā)現(xiàn)dummy態(tài)的entry，且freeslot未設(shè)置，則設(shè)置freeslot

接下來(lái)是：PyDictObject對(duì)象的元素插入與刪除的策略：

需要首先用到搜索策略，搜索成功，則直接將值進(jìn)行替換，搜索失敗，返回unused態(tài)或dummy態(tài)的entry，設(shè)置key、value和hash值，并且根據(jù)目前插入的元素情況進(jìn)行ma_table的大小的調(diào)整（調(diào)整的依據(jù)就是裝載率，根據(jù)是否大于2/3來(lái)進(jìn)行調(diào)整）；刪除也是類似，先計(jì)算hash值，然后搜索相應(yīng)的entry，搜索成功，刪除entry中維護(hù)的元素，將entry從Active態(tài)修改為dummy態(tài)

在PyDictObject的實(shí)現(xiàn)過(guò)程中，會(huì)用到緩沖池，在PyDictObject對(duì)象被銷毀的時(shí)候，才開始接納被緩沖的PyDictObject對(duì)象，定義的緩沖池可接納的對(duì)象數(shù)量是80個(gè)，創(chuàng)建新PyDictObject對(duì)象的時(shí)候，如果緩沖池中有，則可以直接從緩沖池中取出使用

上述就是小編為大家分享的如何實(shí)現(xiàn)python dict了，如果剛好有類似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。