Python 源碼閱讀：dict
（點擊
上方藍字
，快速關注我們）
來源：伯樂在線 - wklken
如有好文章投稿，請點擊 → 這裡了解詳情
源碼位置 Include/dictobject.h | Objects/dictobject.c
PyDictObject的存儲策略
1.
使用散列表進行存儲
2.
使用開放定址法處理衝突
2.1
插入
,
發生衝突
,
通過二次探測演算法
,
尋找下一個位置
,
直到找到可用位置
,
放入
(
形成一條衝突探測鏈)
2.2
查找
,
需要遍歷衝突探測鏈
2.3
刪除
,
如果對象在探測鏈上
,
不能直接刪除
,
否則會破壞整個結構
(
所以不是真的刪)
關於 hash表的 wiki
基本鍵值PyDictEntry
typedef
struct
{
Py_ssize_t
me_hash
;
PyObject *
me_key
;
PyObject *
me_value
;
}
PyDictEntry
;
說明
1.
PyDictEntry
用於存儲鍵值對信息
2.
Py_ssize_t
me
_
hash存儲了
me
_
key計算得到的hash
值,
不重複計算
結構
PyDictEntry的三個狀態(圖片引自-Python源碼剖析)
PyDictObject定義
定義
typedef
struct
_dictobject
PyDictObject
;
struct
_dictobject
{
PyObject_HEAD
Py_ssize_t
ma_fill
;
Py_ssize_t
ma_used
;
Py_ssize_t
ma_mask
;
PyDictEntry *
ma_table
;
PyDictEntry *
(
*
ma_lookup
)(
PyDictObject *
mp
,
PyObject *
key
,
long
hash
);
PyDictEntry
ma_smalltable
[
PyDict_MINSIZE
];
};
說明
1.
PyObject
_
HEAD反而聲明為定長對象
,
因為
ob
_
size在這裡用不上,
使用
ma
_
fill和ma
_
used計數
2.
Py_ssize_t
ma_fill
;
Py_ssize_t
ma_used
;
ma_fill
=
# Active + # Dummy
ma_used
=
# Active
3.
Py_ssize_t
ma_mask
;
散列表
entry
容量=
ma_mask
+
1
,
初始值
ma_mask
=
PyDict_MINSIZE
-
1
=
7
ma_mask
+
1
=
# Unused + # Active + # Dummy
4.
PyDictEntry *
ma_table
;
指向散列表內存
,
如果是小的
dict
(
entry
數量結構
結論
1.
PyDictObject
在生命周期內,
需要維護
ma_fill
/
ma_used
/
ma
_
mask三個計數值
2.
初始化創建是
ma_smalltable
,
超過大小後
,
會使用外部分配的空間
構造過程
定義
PyObject *
PyDict_New
(
void
)
{
register PyDictObject *
mp
;
// 初始化dummy
if
(
dummy
==
NULL
)
{
dummy
=
PyString_FromString
(
""
);
if
(
dummy
==
NULL
)
return
NULL
;
// 暫時忽略
#ifdef SHOW_CONVERSION_COUNTS
Py_AtExit
(
show_counts
);
#endif
#ifdef SHOW_ALLOC_COUNT
Py_AtExit
(
show_alloc
);
#endif
#ifdef SHOW_TRACK_COUNT
Py_AtExit
(
show_track
);
#endif
}
// 如果PyDictObject緩衝池可用
if
(
numfree
)
{
// 取緩衝池最後一個可用對象
mp
=
free_list
[
--
numfree
];
assert
(
mp
!=
NULL
);
assert
(
Py_TYPE
(
mp
)
== &
PyDict_Type
);
_Py_NewReference
((
PyObject *
)
mp
);
// 初始化
if
(
mp
->
ma_fill
)
{
// 1. 清空 ma_smalltable
// 2. ma_used = ma_fill = 0
// 3. ma_table -> ma_smalltable
// 4. ma_mask = PyDict_MINSIZE - 1 = 7
EMPTY_TO_MINSIZE
(
mp
);
}
else
{
// 1. ma_table -> ma_smalltable
// 2. ma_mask = PyDict_MINSIZE - 1 = 7
INIT_NONZERO_DICT_SLOTS
(
mp
);
}
assert
(
mp
->
ma_used
==
0
);
assert
(
mp
->
ma_table
==
mp
->
ma_smalltable
);
assert
(
mp
->
ma_mask
==
PyDict_MINSIZE
-
1
);
#ifdef SHOW_ALLOC_COUNT
count_reuse
++
;
#endif
}
else
{
// 創建一個
mp
=
PyObject_GC_New
(
PyDictObject
,
&
PyDict_Type
);
if
(
mp
==
NULL
)
return
NULL
;
// 初始化 1/2/3/4
EMPTY_TO_MINSIZE
(
mp
);
#ifdef SHOW_ALLOC_COUNT
count_alloc
++
;
#endif
}
// 搜索方法, 關注這個
mp
->
ma_lookup
=
lookdict_string
;
#ifdef SHOW_TRACK_COUNT
count_untracked
++
;
#endif
#ifdef SHOW_CONVERSION_COUNTS
++
created
;
#endif
// 返回
return
(
PyObject *
)
mp
;
}
簡化步驟
1.
如果
PyDictObject
對象緩衝池有,
從裡面直接取
,
初始化
2.
否則
,
創建一個
,
初始化
3.
關聯搜索方法
lookdict
_
string
4.
返回
結論
1.
關注對象緩衝池
2.
關注
lookdict_string
銷毀過程
方法定義
static
void
dict_dealloc
(
register PyDictObject *
mp
)
{
register PyDictEntry *
ep
;
Py_ssize_t
fill
=
mp
->
ma_fill
;
PyObject_GC_UnTrack
(
mp
);
Py_TRASHCAN_SAFE_BEGIN
(
mp
)
// 遍歷銷毀ma_table中元素 (ma_table可能指向small_table 或 外部)
for
(
ep
=
mp
->
ma_table
;
fill
>
0
;
ep
++
)
{
if
(
ep
->
me_key
)
{
--
fill
;
Py_DECREF
(
ep
->
me_key
);
Py_XDECREF
(
ep
->
me_value
);
}
}
// 如果指向外部, 銷毀整個(上面一步只銷毀內部元素)
if
(
mp
->
ma_table
!=
mp
->
ma_smalltable
)
PyMem_DEL
(
mp
->
ma_table
);
// 如果對象緩衝池未滿且是PyDict_Type, 放入
if
(
numfree tp_free
((
PyObject *
)
mp
);
Py_TRASHCAN_SAFE_END
(
mp
)
}
PyDictObject對象緩衝池
定義
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static
PyDictObject *
free_list
[
PyDict_MAXFREELIST
];
static
int
numfree
=
0
;
對象緩衝池的結構(跟PyListObject對象緩衝池結構基本一樣)
結論
1.
最多會緩存
80
個對象
2.
只緩存
PyDictObject
本身
,
其
PyDictEntry
全部會被回收
3.
緩存對象進去
,
舊有的值沒有變化
,
取出來用的時候初始化時才改變
本系列
《Python 源碼閱讀：類型》
《Python 源碼閱讀：對象》
《Python 源碼閱讀：String》
《Python 源碼閱讀：int》
《Python 源碼閱讀：list》
《Python 源碼閱讀：tuple》
看完本文有收穫？請轉
發分享給更多人
關注「P
ython開發者」，提升Python技能
※Python 源碼閱讀：tuple
※Flask 中模塊化應用的實現
※編程零基礎，如何變身年薪百萬的機器學習工程師？
※讓你的 Python 代碼優雅又地道，15篇 Python 技術熱文
TAG:Python開發者 |