python __new__原理，【python-dict】dict的使用及實現原理

以下內容是針對：python源碼剖析中的第五章——python中Dict對象 的讀書筆記（針對書中講到的內容進行了自己的整理，并且針對部分內容根據自己的需求進行了擴展）

?

一、Dict的用法

Dict的對象在使用到了所謂的關聯關系的時候，就是通過key-value的形式，能夠通過key值快速定位到某個value值；

?

Dict的相關操作如下：

class mydict(object):

??? def __init__(self):

??????? self.d = {}

???

??? def fuzhi(self):

??????? self.d = {'2':23, '3':'34'}

???

??? def fuzhi2(self):

??????? self.d[1] = 1

??????? self.d['str'] = 123

??????? self.d['may'] = 234

??????? self.d['may'] = 789

???????

??? def delkey(self):?????????????

??????? del(self.d[1])?? ??????#刪除key時，key值必須存在于dict中，否則會報出 KeyError

??????? self.d.pop('str')

???????

??? def bianli(self):

??????? for (k,v) in self.d.items():

??????????? print k, v

???

??? def getkeysandv(self):

??????? print self.d.keys()????????????? #獲取當前dict中的所有key值

?

? ??????#獲取某個元素值：

??????? print self.d.get('345')???????? #若key不存在，則返回默認返回值None

??????? print self.d.get('123', -1)?? #若key不存在，則返回自定義的返回值-1

??????? print self.d.get('may')??? #若key值存在，則返回對應的value

???????

??? def setkeyexcept(self):

??????? self.d[[1,2,3]] =123?????? #可變對象不能作為key，會提示：TypeError: unhashable type: 'list' 的類似錯誤

?

二、Dict的存儲實現原理

python中的dict對象也即PyDictObject對象，因為對搜索的效率要求很高，所以選擇了散列表（hash table），因為在最優情況下，散列表能夠提供O(1)的搜索效率

因此：這里就能想到在leetcode上面刷的題目中，很多通過list形式可以實現的，為了降低時間復雜度，可以用hash的方式，選擇dict對象存儲（當然具體問題要具體分析）

散列表的基本思想是：通過一定的函數將需要搜索的鍵值映射為一個整數，根據這個整數作為索引去訪問某片連續的內存區域。用于映射的函數稱為映射函數，映射所產生的值稱為散列值（hash value）。散列函數對搜索效率有直接的決定性作用。在使用散列函數將不同的值可能映射到相同的散列值，這個時候就需要沖突解決（裝載率大于2/3時，沖突的概率就會大大增加）

沖突解決在python中使用的是開放定址法，就是通過一個二次探測函數f，計算下一個位置，一直到找到下一個可用的位置為止，在這個過程中會到達多個位置，這些位置就形成了一個“沖突探測鏈”，這個沖突探測鏈在查找某個元素的時候起到重要作用，所以在刪除某個位置上的元素，不能直接將這個位置的內容刪除，如果刪除的話，則導致后續依賴于這個位置的其他值就都無法尋找到了，所以只能進行“偽刪除”（通過給元素設置狀態，dummy態，表示沒有存儲具體的值但是還會用到的廢棄態）

?

?

具體的PyDictObject對象中，會存在每一個元素，元素的定義是：

typedef struct{

??? Py_ssize_t me_hash;

??? PyObject *me_key;

??? PyObject *me_value;

??? }PyDictEntry;

每一個元素有三種狀態，分別是：unused、active、dummy

狀態	具體含義
unused	me_key=Null,me_value=Null
active	me_key!=Null,me_value!=Null
dummy	me_key=dummy,me_value=Null

?

PyDictObject對象的定義：

#define PyDict_MINSIZE 8

typedef struct _dictobject PyDictObject;

struct _dictobject{

??? PyObject_HEAD

??? Py_ssize_t ma_fill;? //元素個數: active+dummy

??? Py_ssize_t ma_used;? //元素個數: Active

??? Py_ssize_t ma_mask;

??? PyDictEntry *ma_table;

??? PyDictEntry *(*ma_lookup) (PyDictEntry *mp, PyObject *key, long hash);

??? PyDictEntry ma_smalltable[PyDict_MINSIZE];

??? }

其中各個字段的含義如下：ma_fill域中維護著從PyDictObject對象創建開始直到現在為止所有曾經及正在處于active態的entry個數；ma_used域中維護著當前正處于Active態的entry個數；ma_smalltable的PyDictEntry的數組，表示的是當創建一個PyDictObject對象的時候，至少創建PyDict_MINISIZE個entry被創建（這個數量在程序中定義是8個，這個數量是經過長期的經驗所得來的值）；ma_table是指向一塊區域的，如果entry的數量不超過8個，那么這個指針就指向了ma_smalltable的地址，如果超過了8個，就需要申請一塊大的內存，并且ma_table指向這塊大的內存

?

三、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對象的時候，如果緩沖池中有，則可以直接從緩沖池中取出使用

?