6.0 序
元素和元素之间可能存在着某种关系，比如学生姓名和成绩。我希望能够通过学生的姓名找到这个学生的成绩，那么只需要将两者关联起来即可。字典正是这么做的，字典中的每个元素就是一个key:value键值对，通过指定的key可以找到value。首先我们在前面的章节中说过，字典这种数据结构，python底层也在大量的使用，比如每一个类都有自己的属性字典，这就意味着python对字典这种数据结构的性能要求是极其苛刻的。所以在python底层，对字典这种数据结构进行了高度的优化。理论上，字典查找元素的时间复杂度是O(1)。
字典底层对应的结构体是PyDictObject，其实我不说，也能猜出来。再比如set，那么底层对应的结构体显然是PySetObject。我们先不看PyDictObject，我们来想一想为什么字典的查找效率是O(1)，它底层是使用了什么原理。
6.1 哈希表
我们在tuple那一章中提到了哈希，还说tuple可以作为字典的key，list不可以，就是因为list是不可哈希的。没错，dict底层正是使用了哈希表，哈希表也叫做散列表。它是将值通过hash运算转为一个数值，这个数值来充当索引。这样解释可能会让人很迷，我们来具体看一张图。
我们发现除了key、value之外，还有一个index。其实hash表本质上也是使用了索引的思想，会把这个key通过函数映射成一个数值，作为索引。至于是怎么映射的，可以的话后面再谈，现在我们就假设是按照我们接下来说的方法映射的。
比如我们这里有一个能容纳10个元素的字典，我们先设置d["satori"]=82，那么会对satori这个字符串进行一个哈希运算，然后再对10、也就是当前的总容量取模，这样的是不是能够得到一个小于10的数呢？假设是5，那么就存在索引为5地方。然后又进行d["koishi"]=83，那么按照同样的规则运算得到8，那么就存在索引为8的位置，同理第三次设置d["mashiro"]=80，对mashiro进行哈希、取模，得到2，那么存储在索引为2的地方。
同理，当我们取值的时候，取d["satori"]，那么同样会对satori进行哈希、取模，得到索引，发现是5，直接把索引为5的value给取出来。当然这种说法肯定是不严谨的，为什么我们来想一个问题。
哈希、取模运算之后得到的结果一定是不同的吗？在运算得到索引的时候，发现这个位置已经有人占了怎么办？取值的时候，索引为5，可如果索引为5对应的key和我们指定获取的key不一致怎么办？
哈希值是有冲突的，如果一旦冲突，那么python底层会改变算法继续映射，直到映射出来的索引没有人用。比如我们设置一个新的key、value，d["tomoyo"]=88，可是我们对tomoyo这个key进行映射之后得到的结果也是5，而索引为5的地方已经被key=satori的键值对给占了，那么python就会换一种规则来对tomoyo进行hash运算，然后添加进去。但如果我们再次设置d["satori"]=100，那么对satori进行映射得到的结果也是5，而key是一致的，那么就会把对应的值进行修改。
同理，当我们获取值的时候，d["tomoyo"]，对key进行映射，得到索引，但是发现key不是我们指定的key，于是改变规则(这个规则跟设置值冲突时，采用的规则是一样的)，重新映射，得到索引，然后发现key是一致的，于是将值取出来。
但如果我们指定了一个不存在的key，那么哈希映射，找到对应索引，发现没有key，证明我们指定的key是不存在的。但如果有的话，发现key和我们指定的key不相等，说明我们只是碰巧撞上了，但由于key不一样，因此会改变规则重新运算，得到新的索引，发现没有对应的key，于是报错：指定的key不存在。
所以从这里就已经能说明问题了，就是把key转换成类似列表的索引。可能有人问，这些值貌似不是连续的啊，对的，肯定不是连续的。并不是说你先存，你的索引就小、就在前面，这是由key进行hash映射之后的结果决定的。而且容量有10个，目前我们只存了4个元素，那么哈希表、或者说字典会不会扩容呢？当然，既然是可变对象，当然会扩容。并且它还不是像列表那样，容量不够才扩容，而当元素个数达到容量的三分之二的时候就会扩容。
我们可以认为字典底层还是使用了索引的思想，字典不可能会像列表那样，元素之间是连续的，一个一个挨在一起的。既然是哈希运算，得到的值肯定是随机的。容量为10，尽管有6个是空着的，但是没关系，我只要保证我设置的元素整体上是有序的即可。就好比有10张桌椅，小红坐在第3张，小明坐在第8张，尽管有空着的，但是没关系，就让它空着。只要我到第3张桌椅能够找到小红、第8张可以找到小明即可。这些桌椅就可以看成是索引，只要我通过索引能够找到对应的元素即可。但是容量为10，为什么不能全部占满之后再扩容呢？试想一下，既然是随机的，那么肯定会出现哈希值碰撞，并且当元素个数到达三分之二之后，这种碰撞的概率非常大。因此当容量到达三分之二的时候，就会申请一份更大的空间，以便来容纳新的元素。
所以我们发现哈希表实际上就是一种空间换时间的方法，如果容量为100，那么就相当于有100个位置，每个元素都进行哈希映射，找到自己的位置。各自的位置都是不固定的，也许会空出来很多元素，但是无所谓，只要保证这些元素在100个位置上是相对有序、通过哈希运算得到索引之后，可以在相应的位置找到它即可。
所以相信应该所有人都能明白为什么哈希表的时间复杂度是O(1)了，就实际因为转化成了索引，每一个索引都是连续的，只不过一部分索引没有相应的key、value罢了。但这无所谓，因为索引和key、value是一一对应的，通过索引我们能瞬间定位到指定的key，再来检测key是否存在以及和我们指定的key是否一致。如果不存在，那么不好意思，证明这个地方根本没有key、value，说明我们指定了一个不存在的key。而且由于元素个数达到容量的三分之二的时候，碰撞的概率非常大，因此几乎不可能出现容量正好都排满的情况，否则那要改变规则、重复映射多少次啊。
一句话总结：哈希表就是一种空间换时间的方法
关于哈希表设置元素、和获取元素用流程图表示的话，就是：
6.2 PyDictObject对象
字典中的一个key、value，我们在底层会把它称之为一个entry，至于为什么？我们后面在源码中可以看到
typedef struct _dictkeysobject PyDictKeysObject;
/* The ma_values pointer is NULL for a combined table
* or points to an array of PyObject* for a split table
对于一张combined table，ma_values指针为NULL
对于一张split table，则指向一个数组，数组里面都是PyObject *
*/
typedef struct {
//注意这是PyObject_HEAD,不是PyObject_VAR_HEAD
//PyObject_HEAD只有引用计数和类型，没有ob_size
PyObject_HEAD
//字典里面元素的个数，active
Py_ssize_t ma_used;
/* Dictionary version: globally unique, value change each time
the dictionary is modified
字典版本：全局唯一，每一次value的变动，都会导致其改变
*/
uint64_t ma_version_tag;
/*
如果ma_values为NULL，这是一张combined table，所有的key和value都存在ma_keys里面
*/
PyDictKeysObject *ma_keys;
/*
如果ma_values不为NULL，这是一张split table，那么key都存在ma_keys里
所有的values都存在ma_values这个数组里
*/
PyObject **ma_values;
} PyDictObject;
//不管装在设么地方，我们看到存储的都是PyObject *
//说明字典是什么都可以装的(不可变类型)
但是说实话，直接这么看是很难看懂的，然而我们发现有一个PyDictKeysObject *，而这个家伙就是_dictkeysobject，从最上面的typedef struct也能看出来，我们来看看这个_dictkeysobject是什么吧
//Objects/dict-common.h
struct _dictkeysobject {
//引用计数
Py_ssize_t dk_refcnt;
/* Size of the hash table (dk_indices). It must be a power of 2. */
/* 哈希表的大小，必须是2的倍数 */
Py_ssize_t dk_size;
/* 与哈希表有关的函数 */
dict_lookup_func dk_lookup;
/* Number of usable entries in dk_entries. */
/* dk_entries中可用的entries数量 */
Py_ssize_t dk_usable;
/* Number of used entries in dk_entries. */
/* dk_entries中已经使用的entries数量 */
Py_ssize_t dk_nentries;
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
The size in bytes of an indice depends on dk_size:
Dynamically sized, SIZEOF_VOID_P is minimum. */
//最终的哈希表，它存储了dk_entries的索引
//里面的类型是会随着dk_size的大小而变化的
/*
- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)
*/
char dk_indices[]; /* char is required to avoid strict aliasing. */
/* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
see the DK_ENTRIES() macro */
};
//我们一直提到了dk_entries，这又是个啥？
//dk_entries是一个数组，里面的元素类型是PyDictKeyEntry，就是一个一个的键值对
//所以我们把某个键值对称之为一个entry，它的大小可以用USABLE_FRACTION这个宏来获取
typedef struct {
/* me_key的哈希值，避免每次查询的时候都要重新建立 */
Py_hash_t me_hash;
//字典的key
PyObject *me_key;
//这个字段只对combined table有意义
/*
还记得ma_values吗？上面说了如果是combined table，那么key和value都会存在PyDictKeysObject *ma_keys里面，但如果是split table，那就只有key会存在PyDictKeysObject *ma_keys里面，也就是这里me_key，所以这里注释了：me_value这个字段只对combined table有意义。因为是split table的话，value都会存储在ma_values里面，而不是这里的me_value
*/
PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;
因此可以看到字典的定义还是蛮复杂的，但是仔细分析还是可以看懂的。PyDictObject里面有一个ma_values，如果是combined table，那么这个值是为NULL，key和value是放在PyDictKeyEntry里面的，由me_key和me_value存储，这当然也是一个PyObject *指针类型。如果是split table，那么ma_values则是一个数组，存储所有value，当然这里的value也是指针，PyDictKeyEntry则只存储key。而哈希表还要对应一个索引啊，这个索引都是放在PyDictKeysObject里面的。
6.2.1 再谈哈希表
从6.1中，我们知道了哈希表的基本思想，就是通过某个函数将需要搜索的键值映射为一个索引，然后通过索引去访问连续的内存区域。而对于哈希表这种数据结构，最终目的就是加速键的搜索过程。而用于映射的函数就是哈希函数，映射之后的值就是哈希值。因此在哈希表的实现中，哈希函数的优劣将直接决定实现的哈希表的搜索效率的高低。
并且我们知道，当元素到达容量的三分之二的时候，会很容易出现哈希值冲突，我们之前说如果冲突了，就改变规则重新映射。事实上，python也确实是这么做的，这种方法叫做开放寻址法。
当发生哈希值冲突时，python会通过一个二次探测函数f，计算下一个候选位置addr，如果可用就插入进去。如果不可用，会继续使用探测函数，直到找到一个可用的位置。
通过多次使用探测函数f，从一个位置可以到达多个位置，我们认为这些位置形成了一个"冲突探测链(探测序列)"，比如当我们插入一个key="satori"的键值对，在a位置发现不行，又走b位置，发现也被人占了，于是到达c位置，发现没有key，于是就占了c这个位置。但是问题来了，如果我此时把b位置上键值对给删掉会引发什么后果？首先我们知道，b位置上的key和我们指定的值为"satori"的key通过哈希函数映射出来的索引是一样的，当我们直接获取d["satori"]，肯定会先走a位置，发现有人但key又不是"satori"，于是重新映射，走到b，发现还不对，再走到c位置，发现key是"satori"，于是就把值取出来了。但是，我要说但是了，如果我们把b位置上的元素删掉呢？那么老规矩，获取、映射、走到a发现坑被占、走到b结果发现居然没有内容，那么直接就报出了一个KeyError。继续寻找的前提是，这个地方要存储了key、value，并且存在的key和指定的key不相同，但如果没有的话，就说明根本没有这个key。然而呢？"satori"这个key确实是存在的，因此发生这种情况我们就说探测链断裂。本来应该走到c的，但是由于b没有元素，因此探测函数在b处就停止了
因此我们发现，当一个元素只要位于任何一条探测链当中，在删除元素时都不能真正意义上的删除，而是一种"伪删除"操作
6.2.2 entry的三种状态
还记得这个entry吗？对于字典里面的一个键值对就叫做一个entry
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;
在python中，当一个PyDictObject对象发生变化时，其中的entry会在三种不同的状态之间进行切换：unused态、active态、dummy态。
当一个entry的me_key和me_value都是NULL的时候，entry处于unused态。unused态表明该entry中并没有存储key、value，并且在此之前也没有存储过它们。每一个entry在初始化的时候都会处于这个状态，me_value不管何时都可能会NULL，这取决于到底是combined table、还是split table，但是对于me_key，只可能在unused的时候才可能会NULL。当entry存储了key时，那么此时entry便从unused态变成了active态当entry中的key(value)被删除后，状态便从active态变成dummy态，注意：这里是dummy，删除了并不代表就能够回到unused态，来存储其他key了。我们也说了，unused态是指当前没有、并且之前也没有存储过。key被删除后，会变成dummy。否则就会发生我们之前说的探测链断裂，至于这个dummy到底是啥，我们后面说。总是entry进入dummy态，就是我们刚才提到的伪删除技术，当python沿着某条探测链搜索时，如果发现一个entry处于dummy态，就会明白虽然当前的entry是无效的，但是后面的entry可能是有效的，而不会直接就停止搜索、报错，这样就保证了探测链的连续性。至于报错，是在找到了unused状态的entry时才会报错，因为这里确实一直都没有存储过key，但是索引确实是这个位置，这说明当前指定的key就真的不存在哈希表中，此时才会报错。
6.3 PyDictObject的创建与维护
6.3.1 PyDictObject的创建
python内部通过PyDict_New来创建一个新的dict对象。
PyObject *
PyDict_New(void)
{
//new_keys_object表示创建PyDictKeysObject*对象
//里面传一个数值，表示entry的容量
//#define PyDict_MINSIZE 8，从宏定义我们能看出来为8
//表示默认初始化能容纳8个entry的PyDictKeysObject
//为什么是8，这是通过大量的经验得来的。
PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
if (keys == NULL)
return NULL;
//这一步则是根据PyDictKeysObject *创建一个新字典
return new_dict(keys, NULL);
}
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
PyDictKeysObject *dk;
Py_ssize_t es, usable;
//检测，size是否>=PyDict_MINSIZE
assert(size >= PyDict_MINSIZE);
assert(IS_POWER_OF_2(size));
usable = USABLE_FRACTION(size);
//es：哈希表中的每个索引占多少字节
if (size <= 0xff) {
es = 1;
}
else if (size <= 0xffff) {
es = 2;
}
#if SIZEOF_VOID_P > 4
else if (size <= 0xffffffff) {
es = 4;
}
#endif
else {
es = sizeof(Py_ssize_t);
}
//注意到，字典里面也有缓冲池，当然这里指定是字典的key
//如果有的话，直接从里面取
if (size == PyDict_MINSIZE && numfreekeys > 0) {
dk = keys_free_list[--numfreekeys];
}
else {
//否则malloc重新申请
dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
+ es * size
+ sizeof(PyDictKeyEntry) * usable);
if (dk == NULL) {
PyErr_NoMemory();
return NULL;
}
}
//设置引用计数、可用的entry个数等信息
DK_DEBUG_INCREF dk->dk_refcnt = 1;
dk->dk_size = size;
dk->dk_usable = usable;
//dk_lookup很关键，里面包括了哈希函数和冲突时的二次探测函数的实现
dk->dk_lookup = lookdict_unicode_nodummy;
dk->dk_nentries = 0;
//哈希表的初始化
memset(&dk->dk_indices[0], 0xff, es * size);
memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
return dk;
/*
keys.entries和values按照顺序
*/
}
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
//这是一个字典的缓冲池
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
}
//系统堆中申请内存
else {
mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
if (mp == NULL) {
DK_DECREF(keys);
free_values(values);
return NULL;
}
}
//设置key、value等等
mp->ma_keys = keys;
mp->ma_values = values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
assert(_PyDict_CheckConsistency(mp));
return (PyObject *)mp;
}
6.3.2 PyDictObject的元素搜索
python为哈希表搜索提供了多种函数，lookdict、lookdict_unicode、lookdict_index，一般通用的是lookdict，lookdict_unicode则是专门针对key为unicode的entry，lookdict_index针对key为int的entry，可以把lookdict_unicode、lookdict_index看成lookdict的特殊实现，只不过这两种可以非常的常用，因此单独实现了一下。
注意:我们无论是对字典设置值还是获取值，都需要进行搜索策略。我们来看看lookdict的底层实现
static Py_ssize_t _Py_HOT_FUNCTION
lookdict(PyDictObject *mp, PyObject *key,
Py_hash_t hash, PyObject **value_addr)
{
size_t i, mask, perturb;
//keys数组的首地址
PyDictKeysObject *dk;
//entries数组的首地址
PyDictKeyEntry *ep0;
top:
dk = mp->ma_keys;
ep0 = DK_ENTRIES(dk);
mask = DK_MASK(dk);
perturb = hash;
//哈希，定位探测链冲突的第一个entry的索引
i = (size_t)hash & mask;
for (;;) {
// dk->indecs[i]
Py_ssize_t ix = dk_get_index(dk, i);
//如果ix == DKIX_EMPTY，说明没有存储值
//理论上是报错的，但是在底层是将值的指针设置为NULL
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return ix;
}
if (ix >= 0) {
//拿到指定的entry的指针
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
//如果两个key一样，那么直接将值的地址设置为ep->me_value
/*
但是注意这里的一样，相当于在python中，两个地址一样的对象
也就是说，a is b是为True
*/
if (ep->me_key == key) {
*value_addr = ep->me_value;
return ix;
}
//如果两个对象不一样，那么就比较它们的哈希值是否相同
//比如33和33是一个对象，但是3333和3333却不是，但是它们的值是一样的
//因此先判断id是否一致，如果不一致再比较值是否一样，当然这里是哈希值
if (ep->me_hash == hash) {
PyObject *startkey = ep->me_key;
Py_INCREF(startkey);
int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
Py_DECREF(startkey);
if (cmp < 0) {
*value_addr = NULL;
return DKIX_ERROR;
}
if (dk == mp->ma_keys && ep->me_key == startkey) {
if (cmp > 0) {
*value_addr = ep->me_value;
return ix;
}
}
else {
/* The dict was mutated, restart */
goto top;
}
}
}
//如果条件均不满足，调整姿势，进行下一次探索
perturb >>= PERTURB_SHIFT;
i = (i*5 + perturb + 1) & mask;
}
Py_UNREACHABLE();
}
6.3.4 插入元素
我们对PyDictObject对象的操作都是建立在搜索的基础之上的，插入和删除也不例外。
static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;
//增加对key和value的引用计数
Py_INCREF(key);
Py_INCREF(value);
//类型检查
if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
if (insertion_resize(mp) < 0)
goto Fail;
}
Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
goto Fail;
assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
MAINTAIN_TRACKING(mp, key, value);
/* 检查共享key，可能扩容哈希表
*/
if (_PyDict_HasSplitTable(mp) &&
((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
(ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
if (insertion_resize(mp) < 0)
goto Fail;
ix = DKIX_EMPTY;
}
//搜索成功
if (ix == DKIX_EMPTY) {
/* 插入一个新的slot，这个slot可以直接看成是entry */
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
/* 需要resize */
if (insertion_resize(mp) < 0)
goto Fail;
}
//寻找值的插入位置，就是我们之前说的将key这个值通过哈希函数映射为索引
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
//拿到PyDictKeyEntry *指针
ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
//设置
dk_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
ep->me_key = key; //设置key
ep->me_hash = hash;//设置哈希
//如果ma_values数组不为空
if (mp->ma_values) {
assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
//设置进去，还记得这是什么表吗？对，这是一张split table
mp->ma_values[mp->ma_keys->dk_nentries] = value;
}
else {
//ma_values数据为空的话，那么value就设置在PyDictKeyEntry对象的me_value里面
ep->me_value = value;
}
mp->ma_used++;//使用个数+1
mp->ma_version_tag = DICT_NEXT_VERSION();//版本数+1
mp->ma_keys->dk_usable--;//可用数-1
mp->ma_keys->dk_nentries++;//里面entry数量+1
assert(mp->ma_keys->dk_usable >= 0);
assert(_PyDict_CheckConsistency(mp));
return 0;
}
//判断key是否存在，存在即替换
if (_PyDict_HasSplitTable(mp)) {
mp->ma_values[ix] = value;
if (old_value == NULL) {
/* pending state */
assert(ix == mp->ma_used);
mp->ma_used++;
}
}
else {
assert(old_value != NULL);
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
}
mp->ma_version_tag = DICT_NEXT_VERSION();
Py_XDECREF(old_value); /* which **CAN** re-enter (see issue #22653) */
assert(_PyDict_CheckConsistency(mp));
Py_DECREF(key);
return 0;
Fail:
Py_DECREF(value);
Py_DECREF(key);
return -1;
}
以上是插入元素，我们看到无论是插入元素、还是设置元素，insertdict都是可以胜任。但是请注意一下参数，有一个hash参数，这个hash是从什么地方获取的呢？答案是，在调用这个insertdict之前其实会首先调用PyDict_SetItem
int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
PyDictObject *mp;
Py_hash_t hash;
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(value);
mp = (PyDictObject *)op;
//计算hash值
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
{
//
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
/* 调用insertdict，必要时调整元素 */
return insertdict(mp, key, hash, value);
}
我们说如果entry个数达到容量的三分之二，那么会调整容量，如何调整呢？
//增长率
#define GROWTH_RATE(d) ((d)->ma_used*3)
static int
insertion_resize(PyDictObject *mp)
{
//本质上调用了dictresize，传入PyDictObject * 和增长率
return dictresize(mp, GROWTH_RATE(mp));
}
static int
dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
//新的容量，entry的个数
Py_ssize_t newsize, numentries;
//老的keys
PyDictKeysObject *oldkeys;
//老的values
PyObject **oldvalues;
//老的entries，新的entries
PyDictKeyEntry *oldentries, *newentries;
/* 确定table的大小*/
for (newsize = PyDict_MINSIZE;
newsize < minsize && newsize > 0;
newsize <<= 1)
;
if (newsize <= 0) {
PyErr_NoMemory();
return -1;
}
//获取原来的所有keys
oldkeys = mp->ma_keys;
/* 创建能够容纳newsize个entry的内存空间 */
mp->ma_keys = new_keys_object(newsize);
if (mp->ma_keys == NULL) {
//把以前的key拷贝过去。
/*
扩容并不是在本地扩容的，我们知道python存储的都是指针
当扩容之后，会在另一个地方申请更大的内存，然后会把之前的内容都拷贝过去
还是那句话，存储的是指针，不管拷贝到什么地方去，指针是不会变的，当然指针指向的值也是不会变的
但是指针的地址会变，因为指针也是一个变量，存储的是指针， 所以叫做指针变量
但不管咋样，总归是变量，自然也是有地址的，指针的指针就是我们所说的二级指针
可以承认的是， 拷贝之后，这些二级指针肯定会变。
然而在python中是体现不出来的，因为python里面没有二级指针的概念，甚至指针也没有。
你只能通过id查看内存地址，比如列表，虽然列表里面存储的本身就是地址，但是获取的时候确实个指针指向的值。
当然使用id查看地址，其实查看的就是列表里面的指针指向的值的地址，对，说白了就是列表里面的元素(指针)本身。
因此地址的地址你在python中是看不到的。
*/
mp->ma_keys = oldkeys;
return -1;
}
//必须满足 可用 >= 已用
assert(mp->ma_keys->dk_usable >= mp->ma_used);
if (oldkeys->dk_lookup == lookdict)
mp->ma_keys->dk_lookup = lookdict;
//获取已用entries
numentries = mp->ma_used;
//获取旧信息
oldentries = DK_ENTRIES(oldkeys);
newentries = DK_ENTRIES(mp->ma_keys);
oldvalues = mp->ma_values;
//如果oldvalues不为NULL，这应该是一个combined table
//split table的特点是key是能是unicode、
//那么需要把split table转换成combined table
if (oldvalues != NULL) {
for (Py_ssize_t i = 0; i < numentries; i++) {
assert(oldvalues[i] != NULL);
//将ma_values数组里面的元素统统都设置到PyDictKeyEntry对象里面去
PyDictKeyEntry *ep = &oldentries[i];
PyObject *key = ep->me_key;
Py_INCREF(key);
newentries[i].me_key = key;
newentries[i].me_hash = ep->me_hash;
newentries[i].me_value = oldvalues[i];
}
//减少原来对oldkeys的引用计数
DK_DECREF(oldkeys);
//将ma_values设置为NULL，因为所有的value都存在了PyDictKeyEntry对象的me_value里面
mp->ma_values = NULL;
if (oldvalues != empty_values) {
free_values(oldvalues);
}
}
else { // 否则的话说明这本身就是一个combined table
if (oldkeys->dk_nentries == numentries) {
//将就得entries拷贝到新的entries里面去
memcpy(newentries, oldentries, numentries * sizeof(PyDictKeyEntry));
}
else {
//处理旧的entries
//active态的entry搬到新table中
//dummy态的entry，调整key的引用计数，丢弃该entry
PyDictKeyEntry *ep = oldentries;
for (Py_ssize_t i = 0; i < numentries; i++) {
while (ep->me_value == NULL)
ep++;
newentries[i] = *ep++;
}
}
//字典缓冲池的操作，后面介绍
assert(oldkeys->dk_lookup != lookdict_split);
assert(oldkeys->dk_refcnt == 1);
if (oldkeys->dk_size == PyDict_MINSIZE &&
numfreekeys < PyDict_MAXFREELIST) {
DK_DEBUG_DECREF keys_free_list[numfreekeys++] = oldkeys;
}
else {
DK_DEBUG_DECREF PyObject_FREE(oldkeys);
}
}
//建立哈希表索引
build_indices(mp->ma_keys, newentries, numentries);
mp->ma_keys->dk_usable -= numentries;
mp->ma_keys->dk_nentries = numentries;
return 0;
}
我们再来看一下改变dict内存空间的一些动作
首先要确定table的大小，很显然这个大小一定要大于minsize，这个minsize通过我们已经看到了，是通过宏定义的，是已用entry的3倍根据新的table，重新申请内存将原来的处于active状态的entry拷贝到新的内存当中，而对于处于dummy状态的entry则直接丢弃。之所以可以丢弃，是因为，dummy状态的entry存在是为了保证探测链不断裂，但是现在所有的active都拷贝到新的内存当中了，它们会形成一条新的探测链，因此也就不需要这些dummy态的entry了建立的新的索引，并且如果之前的table指向了一片系统堆的内存空间，那么我们还需要释放，以防止内存泄漏。
6.3.5 删除元素
插入元素(设置元素)如果明白了，删除元素我觉得都可以不需要说了。
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
//这显然和dictresize一样，是先获取hash值
Py_hash_t hash;
assert(key);
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
//真正来删除是下面这个函数
return _PyDict_DelItem_KnownHash(op, key, hash);
}
int
_PyDict_DelItem_KnownHash(PyObject *op, PyObject *key, Py_hash_t hash)
{
Py_ssize_t ix;
PyDictObject *mp;
PyObject *old_value;
//类型检测
if (!PyDict_Check(op)) {
PyErr_BadInternalCall();
return -1;
}
assert(key);
assert(hash != -1);
mp = (PyDictObject *)op;
//获取对应entry的index
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
if (ix == DKIX_ERROR)
return -1;
if (ix == DKIX_EMPTY || old_value == NULL) {
_PyErr_SetKeyError(key);
return -1;
}
// split table不支持删除操作，如果是split table，需要转换成combined table
if (_PyDict_HasSplitTable(mp)) {
if (dictresize(mp, DK_SIZE(mp->ma_keys))) {
return -1;
}
ix = (mp->ma_keys->dk_lookup)(mp, key, hash, &old_value);
assert(ix >= 0);
}
//传入hash和ix，又调用了delitem_common
return delitem_common(mp, hash, ix, old_value);
}
static int
delitem_common(PyDictObject *mp, Py_hash_t hash, Py_ssize_t ix,
PyObject *old_value)
{
PyObject *old_key;
PyDictKeyEntry *ep;
//找到对应的hash索引
Py_ssize_t hashpos = lookdict_index(mp->ma_keys, hash, ix);
assert(hashpos >= 0);
//已经entries个数-1
mp->ma_used--;
//版本-1
mp->ma_version_tag = DICT_NEXT_VERSION();
//拿到entry的指针
ep = &DK_ENTRIES(mp->ma_keys)[ix];
//将其设置为dummy状态
dk_set_index(mp->ma_keys, hashpos, DKIX_DUMMY);
ENSURE_ALLOWS_DELETIONS(mp);
old_key = ep->me_key;
//将其key、value都设置为NULL
ep->me_key = NULL;
ep->me_value = NULL;
//减少引用计数
Py_DECREF(old_key);
Py_DECREF(old_value);
assert(_PyDict_CheckConsistency(mp));
return 0;
}
流程非常清晰，也很简单。先使用PyDict_DelItem计算hash值，再使用_PyDict_DelItem_KnownHash计算出索引，最后使用delitem_common获取相应的entry，删除维护的元素，并将entry从active态设置为dummy态，同时还会调整ma_used(已用entry)的数量
6.4 PyDictObject对象缓冲池
从介绍PyLongObject的小整数对象池的时候，我们就说过，不同的对象都有自己的缓冲池，比如list，当然dict也不例外。
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
PyDictObject的缓冲池机制其实和PyListObject的缓冲池是类似的，开始时，这个缓冲池什么也没有，直到第一个PyDictObject对象被销毁时，这个PyDictObject缓冲池里面才开始接纳被缓冲的PyDictObject对象。
static void
dict_dealloc(PyDictObject *mp)
{
//获取ma_values指针
PyObject **values = mp->ma_values;
//获取所有的ma_keys指针
PyDictKeysObject *keys = mp->ma_keys;
//两个整型
Py_ssize_t i, n;
//追踪、调试
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_SAFE_BEGIN(mp)
//调整引用计数
if (values != NULL) {
if (values != empty_values) {
for (i = 0, n = mp->ma_keys->dk_nentries; i < n; i++) {
Py_XDECREF(values[i]);
}
free_values(values);
}
DK_DECREF(keys);
}
else if (keys != NULL) {
assert(keys->dk_refcnt == 1);
DK_DECREF(keys);
}
//将被销毁的对象放到缓冲池当中
if (numfree < PyDict_MAXFREELIST && Py_TYPE(mp) == &PyDict_Type)
free_list[numfree++] = mp;
else
Py_TYPE(mp)->tp_free((PyObject *)mp);
Py_TRASHCAN_SAFE_END(mp)
}
和PyListObject对象的缓冲池机制一样，缓冲池中只保留了PyDictObject对象。如果维护的维护的是从系统堆中申请的内存空间，那么python将释放这份内存空间，归还给系统堆。如果不是，那么仅仅只需要调整维护的对象的引用计数即可
其实在创建一个PyDictObject对象时，如果缓冲池中有可用的对象，也会直接从缓冲池中取，而不需要再重新创建。
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
PyDictObject *mp;
assert(keys != NULL);
if (numfree) {
mp = free_list[--numfree];
assert (mp != NULL);
assert (Py_TYPE(mp) == &PyDict_Type);
_Py_NewReference((PyObject *)mp);
}
...
...
...