Python源码阅读-内建对象(-1)

(Updated: )
,

这是《Python源码剖析 — 深度探索动态语言核心技术》的阅读记录.

Python中的列表对象 - PyDictObject. 这就是我们研究的最后一个内建对象啦.

超级散列表

我们都知道, 在最优的情况下, 散列表可以提供O(1)复杂度的搜索效率. 而dict对象正是使用了散列表这样的数据结构. 其实我个人觉得Python中的字典对象是一个较为复杂的对象了, 不过在后文中, 我打算更经常的称其为关联式容器.

所谓关联就是指字典中的那键值对映射, 那么我们就来看看Python中的这个关联容器的设计吧.

1
2
3
4
5
6
7
8
9
typedef struct {
	/* Cached hash code of me_key.  Note that hash codes are C longs.
	 * We have to use Py_ssize_t instead because dict_popitem() abuses
	 * me_hash to hold a search finger.
	 */
	Py_ssize_t me_hash;
	PyObject *me_key;
	PyObject *me_value;
} PyDictEntry;

看下名字, 没错. 这个就是我们每次去除的一对键值对的实现. 一般都叫做entry, 有的时候也叫做slot. 可以看到, 包含一个键, 一个值, 还有键的hash值. 我们再第一次看Python的对象实现基石的时候就说过了, 所有的对象都可以使用PyObject*指针来引用, 这也就是为啥dict可以容纳所有的对象的原因. 当然, 存储hash的原因不言自明, 就是为了避免重复计算嘛~

为了能够更好的说明接下来的内容, 还是先说一些和散列表有关的话题. 当一个散列表的2/3都已经被填充了的时候, 这个时候的冲突率会大大增加, 而Python选择的冲突解决方法是通过二次定址来寻找下一个可用的位置. 也就是说, 当哈希碰撞发生的时候, Python就会再进行一次计算来寻找下一个位置. 这样就会形成一个可能不是连续的冲突探测链. 通过这个探测链, 我们就可以寻找到冲突的元素的位置.

那么经过上面的, 我们接下来就要来说下这个键值对, 也就是entry 他一共有三种状态:

  • Unused
  • Active
  • Dummy

是不是有点像是进程的三态呢? 哈哈我开玩笑的. 当我们初始化生成一个entry的时候, 这个entry的键和值都是NULL 此时, 我们就说这个键值对是Unused.

接下来, 当我们给这个entry进行了键值对的填充之后, 它就会变成Active状态. 在这个状态下, 我们的key和value都不会是NULL的.

而Dummy态就有趣了, 并且和我们上面说的冲突探测链有关系. 当我们这个entry存储的键值对删除了之后, 这个entry就会变成Dummy态, 而不是直接成为Unused. 为什么? 如果说这个entry是位于我们的探测链上的, 就会直接导致后面的元素将无法被检索到. 也就是说, 这个处理方法就是一种典型的伪删除. 在搜索时, 我们可以得知这个entry已经被删除了, 但是可能后面的entry仍然是有效的, 就可以继续进行搜索.

那么我们实际使用的字典对象, 其实就是这么一堆Entry的集合嘛.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct _dictobject PyDictObject;
struct _dictobject {
	PyObject_HEAD
	Py_ssize_t ma_fill;  /* # Active + # Dummy */
	Py_ssize_t ma_used;  /* # Active */

	/* The table contains ma_mask + 1 slots, and that's a power of 2.
	 * We store the mask instead of the size because the mask is more
	 * frequently needed.
	 */
	Py_ssize_t ma_mask;

	/* ma_table points to ma_smalltable for small tables, else to
	 * additional malloc'ed memory.  ma_table is never NULL!  This rule
	 * saves repeated runtime null-tests in the workhorse getitem and
	 * setitem calls.
	 */
	PyDictEntry *ma_table;
	PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
	PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

这里的ma_fill是指从对象创建开始所处于(或曾经处于)Active状态的Entry数量, 而ma_used就像是前者的子集, 他只包含当前Active状态的entry. 先来最后一个成员, 就是那个smalltable, 一开始就是PyDict_MINSIZE的大小. 这个值在文件中定义的是8:

1
#define PyDict_MINSIZE 8

这个值就是为了避免malloc所带来的效率下降, 而8是Python多次实验之后得到的一个比较理想的值.

而整个对象的核心就是那个ma_table成员了. 它就是Dict的entry的那一大片内存的指针, 但是我们不是还有一个ma_smalltable这个玩意嘛. 对了 只要在没有到8个entry的时候就会指向这个smalltable的内存地址. 有了这样的一个机制, 就相当于是确保了ma_table不会成为NULL. 至于剩下的两个成员我们留在后面说.

创建一个PyDictObject对象

直接祭出代码吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
PyObject *
PyDict_New(void)
{
	register dictobject *mp;
	if (dummy == NULL) { /* Auto-initialize dummy */
		dummy = PyString_FromString("<dummy key>");
		if (dummy == NULL)
			return NULL;
#ifdef SHOW_CONVERSION_COUNTS
		Py_AtExit(show_counts);
#endif
	}
	if (num_free_dicts) {
		mp = free_dicts[--num_free_dicts];
		assert (mp != NULL);
		assert (mp->ob_type == &PyDict_Type);
		_Py_NewReference((PyObject *)mp);
		if (mp->ma_fill) {
			EMPTY_TO_MINSIZE(mp);
		}
		assert (mp->ma_used == 0);
		assert (mp->ma_table == mp->ma_smalltable);
		assert (mp->ma_mask == PyDict_MINSIZE - 1);
	} else {
		mp = PyObject_GC_New(dictobject, &PyDict_Type);
		if (mp == NULL)
			return NULL;
		EMPTY_TO_MINSIZE(mp);
	}
	mp->ma_lookup = lookdict_string;
#ifdef SHOW_CONVERSION_COUNTS
	++created;
#endif
	_PyObject_GC_TRACK(mp);
	return (PyObject *)mp;
}

放眼望去, Python扔了很多assert进去. 眼尖的你可能瞬间就看到了num_free_dicts. 嘿嘿 恭喜你又猜到了后文的标题. 行吧, 废话就不说了, 我们还是来看代码吧.

1
2
3
4
5
6
7
8
9
PyObject *
PyDict_New(void)
{
	register dictobject *mp;
	if (dummy == NULL) { /* Auto-initialize dummy */
		dummy = PyString_FromString("<dummy key>");
        ...
    }
}

你会发现, dummy其实是一个字符串对象, 毕竟 他只是用来作为一个指示标志. 然后就会从系统堆中申请一个Dict的内存空间, 它使用了两个宏, 一个宏套着另一个宏.

来看下:

1
2
3
4
5
6
7
8
9
10
#define INIT_NONZERO_DICT_SLOTS(mp) do {				\
	(mp)->ma_table = (mp)->ma_smalltable;				\
	(mp)->ma_mask = PyDict_MINSIZE - 1;				\
    } while(0)

#define EMPTY_TO_MINSIZE(mp) do {					\
	memset((mp)->ma_smalltable, 0, sizeof((mp)->ma_smalltable));	\
	(mp)->ma_used = (mp)->ma_fill = 0;				\
	INIT_NONZERO_DICT_SLOTS(mp);					\
    } while(0)

先来看上面的, 它就是把table指向那个默认的小table(8个entry), 接着设置我们之前说的mask为最小值-1. 其实, 我们的这个mask也可以被叫做size, 之所以没有这样命名, 我们后面再说.

接下来, 我们看下面的. 其实就是在初始化我们的table之前先初始化table内存和计数器.

最后来关注这么一个东西:

1
mp->ma_lookup = lookdict_string;

这个我们会在下一小节讨论. 这个就是PyDictObject的搜索策略. 这个ma_lookup, 就决定这字典对象在进行搜索entry的时候如果出现冲突的时候, 二次探测函数的具体实现.

在PyDictObject中进行元素搜索

OK, 现在告诉你. 有两种进行搜索的方法:

  • lookdict_string
  • lookdict

而默认的就是我们在上面看到的lookdict_string. 不过从名字也可以看出来, 显然是lookdict更加通用, 而lookdict_string是lookdict的一个特例. 那么就从通用的搜索策略开始看起吧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static dictentry *
lookdict(dictobject *mp, PyObject *key, register long hash)
{
	register size_t i;
	register size_t perturb;
	register dictentry *freeslot;
	register size_t mask = (size_t)mp->ma_mask;
	dictentry *ep0 = mp->ma_table;
	register dictentry *ep;
	register int cmp;
	PyObject *startkey;

	i = (size_t)hash & mask;
	ep = &ep0[i];
	if (ep->me_key == NULL || ep->me_key == key)
		return ep;

	if (ep->me_key == dummy)
		freeslot = ep;
	else {
		if (ep->me_hash == hash) {
			startkey = ep->me_key;
			Py_INCREF(startkey);
			cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
			Py_DECREF(startkey);
			if (cmp < 0)
				return NULL;
			if (ep0 == mp->ma_table && ep->me_key == startkey) {
				if (cmp > 0)
					return ep;
			}
			else {
				/* The compare did major nasty stuff to the
				 * dict:  start over.
				 * XXX A clever adversary could prevent this
				 * XXX from terminating.
 				 */
 				return lookdict(mp, key, hash);
 			}
		}
		freeslot = NULL;
	}
	...
}

我们可以看到, 这个函数返回的值当中存在自己的递归调用, 这就说明在找entry的过程中是, 根据寻找的位置, 是存在不同的处理的. 我们来从变量定义下面来开始看吧.

首先就是一个位与操作, 使用的是带搜索的字典的mask和传入的hash. 这样即可确保最后搜索不会超过这个这个字典对象所维护的entry数量, 而这个代表字典对象entry size的成员经常进行位与操作, 这就是命名为mask的原因.

通过位与操作, 我们就可以定位到冲突探测链的第一个entry. (?) 接着就开始了第一次的比较, 如果巧了比对成功或者遇到了一个Unused的entry, 就直接返回这个entry.

这里 补充一下, 字典对象的搜索策略始终返回的不是NULL或者0或者-1啥的(除非子函数执行失败), 不论是否搜索到, 都会返回一个entry对象, 如果是匹配到了的, 那就会返回搜索需要的, 如果是没有匹配到的, 就会返回一个me_value值为NULL的entry.

接着, 如果这第一个entry的状态是dummy, 我们就要把这个entry记录下, 让freeslot来指向它. 接下来为了能够更好的理解后面, 我们先来讨论下这里的相等是个什么意思:

1
2
3
4
>>> l = {}
>>> l[9876] = "Python"
>>> print(l[9876])
Python

有了前面的基础, 我们知道这里的两个9876肯定是两个不同的对象, 但是他们的值是相同的, 所以这里依然能够找到就是因为值相同, 这就是说如果仅仅就到我们分析的那个地方:

1
2
if (ep->me_key == NULL || ep->me_key == key)
    return ep;

这里是不会相等的, 因为两个9876的引用是不一样的. 那么仍然能够正确返回的秘密就在后面了.

先来看下如果不是一个dummy状态的entry, 而是一个Active状态的entry的话是什么效果. 最先当然是检查hash是否相同, 如果hash不一致, 显然值也不可能是相同的了.

如果hash一致, 我们就继续进行比较, 这里调用了一个Python的比较函数, 并且使用Py_EQ宏来使得快速进行同类对象比较. 如果出现一些脏东西, 那么没办法了, 只能从头开始, 至于这个脏东西到底是什么, 什么情况下会发生, 我没搞清楚.

找到了, 在这里有说明: Issue14205 大概的意思就是说在比较中如果出现值的变化会导致问题的出现. 另外会出现C的无限递归出现.

那行了. 到目前为止, 我们已经摸清楚了搜索时deal with第一个entry的做法. 如果说第一个entry搞完了还是没有结果我们就要继续向后了. 来继续看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* In the loop, me_key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
    i = (i << 2) + i + perturb + 1;
    ep = &ep0[i & mask];
    if (ep->me_key == NULL)
        return freeslot == NULL ? ep : freeslot;
    if (ep->me_key == key)
        return ep;
    if (ep->me_hash == hash && ep->me_key != dummy) {
        startkey = ep->me_key;
        Py_INCREF(startkey);
        cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
        Py_DECREF(startkey);
        if (cmp < 0)
            return NULL;
        if (ep0 == mp->ma_table && ep->me_key == startkey) {
            if (cmp > 0)
                return ep;
        }
        else {
            /* The compare did major nasty stuff to the
				 * dict:  start over.
				 * XXX A clever adversary could prevent this
				 * XXX from terminating.
 				 */
            return lookdict(mp, key, hash);
        }
    }
    else if (ep->me_key == dummy && freeslot == NULL)
        freeslot = ep;
}
assert(0);	/* NOT REACHED */
return 0;

这里就要继续沿着冲突探测链继续向前进了. 首先还是要获得探测链下一个entry的位置, 如果是一个Unused的entry, 说明已经结束了, 把freeslot返回, 或者是返回Unused的entry, 总之返回的那个总是可以使用的, 键值对为NULL的.

接着就是分别检查引用和值是否相同 最后, 如果发现当前是个Dummy态的并且freeslot没有设置, 就把freeslot设置成这个Dummy态的entry. 直到搜索完, 这样 全部的搜索过程就结束了.

通用的逻辑看完了, 接下来来看下特例lookdict_string吧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static dictentry *
lookdict_string(dictobject *mp, PyObject *key, register long hash)
{
	register size_t i;
	register size_t perturb;
	register dictentry *freeslot;
	register size_t mask = (size_t)mp->ma_mask;
	dictentry *ep0 = mp->ma_table;
	register dictentry *ep;

	/* Make sure this function doesn't have to handle non-string keys,
	   including subclasses of str; e.g., one reason to subclass
	   strings is to override __eq__, and for speed we don't cater to
	   that here. */
	if (!PyString_CheckExact(key)) {
#ifdef SHOW_CONVERSION_COUNTS
		++converted;
#endif
		mp->ma_lookup = lookdict;
		return lookdict(mp, key, hash);
	}
	i = hash & mask;
	ep = &ep0[i];
	if (ep->me_key == NULL || ep->me_key == key)
		return ep;
	if (ep->me_key == dummy)
		freeslot = ep;
	else {
		if (ep->me_hash == hash && _PyString_Eq(ep->me_key, key))
			return ep;
		freeslot = NULL;
	}

	/* In the loop, me_key == dummy is by far (factor of 100s) the
	   least likely outcome, so test for that last. */
	for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
		i = (i << 2) + i + perturb + 1;
		ep = &ep0[i & mask];
		if (ep->me_key == NULL)
			return freeslot == NULL ? ep : freeslot;
		if (ep->me_key == key
		    || (ep->me_hash == hash
		        && ep->me_key != dummy
			&& _PyString_Eq(ep->me_key, key)))
			return ep;
		if (ep->me_key == dummy && freeslot == NULL)
			freeslot = ep;
	}
	assert(0);	/* NOT REACHED */
	return 0;
}

当所有的键都是字符串类型的时候, 就会调用这个玩意. 自一开始就开始了类型检测, 如果发现不是严格等于字符串对象的话, 就会返回使用通用搜索策略.

基本的逻辑还是很相像的, 先获得第一个entry的位置, 接着开始分别比对Unused态, Dummy态, Active态, 并且设置恰当的freeslot. 接着就按照散列函数的定义这么一直比对下去就好了. 在这里就省略掉了大量错误捕获的代码, 因为我们不需要处理不明确的PyObject* 而是确定的字符串对象了.

插入和删除元素

在Python字典对象的设计中, 插入元素(或者更好的应该说是设置元素, 因为有可能会触发update[键相同])的函数是PyDict_SetItem. 这个函数调用了两个子函数: insertdict, dictresize.所以我们就先看下这两个.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
static int
insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
{
	PyObject *old_value;
	register dictentry *ep;
	typedef PyDictEntry *(*lookupfunc)(PyDictObject *, PyObject *, long);

	assert(mp->ma_lookup != NULL);
	ep = mp->ma_lookup(mp, key, hash);
	if (ep == NULL) {
		Py_DECREF(key);
		Py_DECREF(value);
		return -1;
	}
	if (ep->me_value != NULL) {
		old_value = ep->me_value;
		ep->me_value = value;
		Py_DECREF(old_value); /* which **CAN** re-enter */
		Py_DECREF(key);
	}
	else {
		if (ep->me_key == NULL)
			mp->ma_fill++;
		else {
			assert(ep->me_key == dummy);
			Py_DECREF(dummy);
		}
		ep->me_key = key;
		ep->me_hash = (Py_ssize_t)hash;
		ep->me_value = value;
		mp->ma_used++;
	}
	return 0;
}

首先我们执行上一节的搜索函数, 这样要么就是获得了Active状态的entry, 即将replace, 或者是Dummy以及Unused的, 对于前者, 我们直接改变value就可以了, 后者我们还要重新的设置一遍. 这就是后面主要做的事情.

现在我们回到SetItem身上, 来看看他是如何调用insertdict的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
int
PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
{
	register dictobject *mp;
	register long hash;
	register Py_ssize_t n_used;

	if (!PyDict_Check(op)) {
		PyErr_BadInternalCall();
		return -1;
	}
	assert(key);
	assert(value);
	mp = (dictobject *)op;
	if (PyString_CheckExact(key)) {
		hash = ((PyStringObject *)key)->ob_shash;
		if (hash == -1)
			hash = PyObject_Hash(key);
	}
	else {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	assert(mp->ma_fill <= mp->ma_mask);  /* at least one empty slot */
	n_used = mp->ma_used;
	Py_INCREF(value);
	Py_INCREF(key);
	if (insertdict(mp, key, hash, value) != 0)
		return -1;
	/* If we added a key, we can safely resize.  Otherwise just return!
	 * If fill >= 2/3 size, adjust size.  Normally, this doubles or
	 * quaduples the size, but it's also possible for the dict to shrink
	 * (if ma_fill is much larger than ma_used, meaning a lot of dict
	 * keys have been * deleted).
	 *
	 * Quadrupling the size improves average dictionary sparseness
	 * (reducing collisions) at the cost of some memory and iteration
	 * speed (which loops over every possible entry).  It also halves
	 * the number of expensive resize operations in a growing dictionary.
	 *
	 * Very large dictionaries (over 50K items) use doubling instead.
	 * This may help applications with severe memory constraints.
	 */
	if (!(mp->ma_used > n_used && mp->ma_fill*3 >= (mp->ma_mask+1)*2))
		return 0;
	return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);
}

再调用插入之前发生了什么了? 其实很简单嘛, 就是在计算出哈希值好来调用插入字典函数, 接着如果出现了当前fill >= 2/3 size的时候, 就要开始重新调整大小了, 这就是为了避免出现碰撞.

我们先简单看下字典resize的签名:

1
2
static int
dictresize(dictobject *mp, Py_ssize_t minused)

主要就是后者, 这个就是保证字典正常的大小的最小值. 而这个值被设定成:

1
(mp->ma_used > 50000 ? 2 : 4) * mp->ma_used

2倍或者是4倍, 当Active状态的entry很大的时候(50000), Python就开始限制自己索取的内存量了. 具体是怎么改变的呢 我们来阅读下这个函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
static int
dictresize(dictobject *mp, Py_ssize_t minused)
{
	Py_ssize_t newsize;
	dictentry *oldtable, *newtable, *ep;
	Py_ssize_t i;
	int is_oldtable_malloced;
	dictentry small_copy[PyDict_MINSIZE];

	assert(minused >= 0);

	/* Find the smallest table size > minused. */
	for (newsize = PyDict_MINSIZE;
	     newsize <= minused && newsize > 0;
	     newsize <<= 1)
		;
	if (newsize <= 0) {
		PyErr_NoMemory();
		return -1;
	}

	/* Get space for a new table. */
	oldtable = mp->ma_table;
	assert(oldtable != NULL);
	is_oldtable_malloced = oldtable != mp->ma_smalltable;

	if (newsize == PyDict_MINSIZE) {
		/* A large table is shrinking, or we can't get any smaller. */
		newtable = mp->ma_smalltable;
		if (newtable == oldtable) {
			if (mp->ma_fill == mp->ma_used) {
				/* No dummies, so no point doing anything. */
				return 0;
			}
			/* We're not going to resize it, but rebuild the
			   table anyway to purge old dummy entries.
			   Subtle:  This is *necessary* if fill==size,
			   as lookdict needs at least one virgin slot to
			   terminate failing searches.  If fill < size, it's
			   merely desirable, as dummies slow searches. */
			assert(mp->ma_fill > mp->ma_used);
			memcpy(small_copy, oldtable, sizeof(small_copy));
			oldtable = small_copy;
		}
	}
	else {
		newtable = PyMem_NEW(dictentry, newsize);
		if (newtable == NULL) {
			PyErr_NoMemory();
			return -1;
		}
	}

	/* Make the dict empty, using the new table. */
	assert(newtable != oldtable);
	mp->ma_table = newtable;
	mp->ma_mask = newsize - 1;
	memset(newtable, 0, sizeof(dictentry) * newsize);
	mp->ma_used = 0;
	i = mp->ma_fill;
	mp->ma_fill = 0;

	/* Copy the data over; this is refcount-neutral for active entries;
	   dummy entries aren't copied over, of course */
	for (ep = oldtable; i > 0; ep++) {
		if (ep->me_value != NULL) {	/* active entry */
			--i;
			insertdict_clean(mp, ep->me_key, (long)ep->me_hash,
					 ep->me_value);
		}
		else if (ep->me_key != NULL) {	/* dummy entry */
			--i;
			assert(ep->me_key == dummy);
			Py_DECREF(ep->me_key);
		}
		/* else key == value == NULL:  nothing to do */
	}

	if (is_oldtable_malloced)
		PyMem_DEL(oldtable);
	return 0;
}

一开始就是获得更改之后的大小, 具体的方法就是一直翻倍, 只要没有超过那个minsize就一直这么做. 接着, 我们先备份就的table, 并且要知道此时是否还在使用smalltable. 接着, 如果获得的newsize就是8, 也就是说不需要继续分配内存了, 直接继续使用smalltable就可以了.然后就是直接进行一次memcpy就可以了. 否则我们就需要分配新的空间, 接着我们统一进行初始化操作, 另外设置内存, 使得这个字典对象变成一个全新的对象. 接着我们就可以把entry插回来, 如果是Active状态的 就使用一个精简版的insertdict来搞定. 如果是Dummy状态, 就直接把它的键值抹杀掉就好了, 因为他存在的意义就是保持探测链的连续. 最后, 为了防止内存泄露, 就清空那个外部table的内存了.

这就是全部的插入过程了.

接下来我们来看下删除操作, 删除操作要比插入操作简单清晰多了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int
PyDict_DelItem(PyObject *op, PyObject *key)
{
	register dictobject *mp;
	register long hash;
	register dictentry *ep;
	PyObject *old_value, *old_key;

	if (!PyDict_Check(op)) {
		PyErr_BadInternalCall();
		return -1;
	}
	assert(key);
	if (!PyString_CheckExact(key) ||
	    (hash = ((PyStringObject *) key)->ob_shash) == -1) {
		hash = PyObject_Hash(key);
		if (hash == -1)
			return -1;
	}
	mp = (dictobject *)op;
	ep = (mp->ma_lookup)(mp, key, hash);
	if (ep == NULL)
		return -1;
	if (ep->me_value == NULL) {
		set_key_error(key);
		return -1;
	}
	old_key = ep->me_key;
	Py_INCREF(dummy);
	ep->me_key = dummy;
	old_value = ep->me_value;
	ep->me_value = NULL;
	mp->ma_used--;
	Py_DECREF(old_value);
	Py_DECREF(old_key);
	return 0;
}

首先就是获取Hash值, 接着根据获得的hash进行搜索, 如果没搜索到, 自然就是删除失败了, 如果搜索到了, 那就拿到了entry了, 这就好办了, 直接删除entry所维护的键值对, 并且通过减掉引用计数来抹杀掉他们. 另外一件重要的事情就是, 将这个entry标记成Dummy态.

缓冲..池 (怎么还来?!

OK, Python同样为字典对象设置了缓冲池, 我们之前在看创建函数的时候也注意到了那个缓冲池对象.

1
2
3
#define MAXFREEDICTS 80
static PyDictObject *free_dicts[MAXFREEDICTS];
static int num_free_dicts = 0;

如果你记忆力足够好的话 你会发现:

1
2
3
#define MAXFREELISTS 80
static PyListObject *free_lists[MAXFREELISTS];
static int num_free_lists = 0;

没错, 这根本就和列表对象的缓冲池一模一样嘛. 其实就连实现机制都是差不多的, 那就是在析构函数中将这个字典对象所维护的所有键值对销毁之后将这个字典对象本身加入到缓冲池之中. 来看代码吧:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static void
dict_dealloc(register dictobject *mp)
{
	register dictentry *ep;
	Py_ssize_t fill = mp->ma_fill;
 	PyObject_GC_UnTrack(mp);
	Py_TRASHCAN_SAFE_BEGIN(mp)
	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);
	if (num_free_dicts < MAXFREEDICTS && mp->ob_type == &PyDict_Type)
		free_dicts[num_free_dicts++] = mp;
	else
		mp->ob_type->tp_free((PyObject *)mp);
	Py_TRASHCAN_SAFE_END(mp)
}

把这个字典每一个entry的键值对引用释放, 接着释放内存归还给系统堆, 接着就把这一只丢到缓冲池之中了. 另外在创建的时候, 如果这个缓冲池中有, 就直接拿来用了:

1
2
3
4
5
6
7
8
9
10
11
12
if (num_free_dicts) {
    mp = free_dicts[--num_free_dicts];
    assert (mp != NULL);
    assert (mp->ob_type == &PyDict_Type);
    _Py_NewReference((PyObject *)mp);
    if (mp->ma_fill) {
        EMPTY_TO_MINSIZE(mp);
    }
    assert (mp->ma_used == 0);
    assert (mp->ma_table == mp->ma_smalltable);
    assert (mp->ma_mask == PyDict_MINSIZE - 1);
}

实验

最后还是惯例的结论验证时间, 这一次我们在字典每次插入的时候打印出当前的字典状态, 并且尝试体验下dummy状态.为了防止大量的输出(因为Python自己就会有大量的字典插入操作), 所以我们只打印拥有特殊ID的字典(我自己定义的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
>>> d = {"ID":1}
>>> d[9] = 9
insert 9
  key : NULL	9	NULL	NULL	NULL	'ID'	NULL	NULL
value : NULL	9	NULL	NULL	NULL	'1'	NULL	NULL
>>> d[17] = 17
insert 17
  key : NULL	9	NULL	NULL	NULL	'ID'	NULL	17
value : NULL	9	NULL	NULL	NULL	'1'	NULL	17
>>> del d[9]
>>> d[17] = 16
insert 17
  key : NULL	dummy	NULL	NULL	NULL	'ID'	NULL	17
value : NULL	NULL	NULL	NULL	NULL	'1'	NULL	16
>>> del d[17]
>>> d[17] = 17
insert 17
  key : NULL	17	NULL	NULL	NULL	'ID'	NULL	dummy
value : NULL	17	NULL	NULL	NULL	'1'	NULL	NULL

这就是实验的效果, 这里9和17是会出现哈希碰撞的, 从实验结果也可以看出来的.