五、DICT对象
1、散列表概述
2、PyDictObject
3、PyDictObject的创建与维护
4、PyDictObject 对象缓冲池
5、Hack PyDictObject
这篇篇幅较长，难点在字典搜索。
1、散列表概述
python中的dict并没有采用map中的红黑树结构做关联，而是使用效率更高的散列表。
散列表通过一个函数将键值映射为一个整数，再将整数作为索引值访问内存。用于映射的函数称为散列函数，映射后的值为散列值。散列会发生冲突，解决散列冲突的方法有很多，python使用的是开放定址法，当发生冲突再次探测可用位置，形成探测链，探测链如果要删掉中间一个元素，会使用伪删除处理，防止链断开搜索失败。
2、PyDictObject
后面将把关联容器中的一个(key, value)元素对称为一个entry或slot。一个entry定义：
[dictobject.h]
typedef struct {
long me_hash; /* cached hash code of me_key */
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
me_hash域 存储me_key的散列值，entry分为三种状态：Unused态、Active态、Dummy态，切换如下：
PyDictObject实际是一堆entry的集合：
[dictobject.h]
#define PyDict_MINSIZE 8
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
int ma_fill; /* # Active + # Dummy */
int ma_used; /* # Active */
int ma_mask;
PyDictEntry *ma_table;
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
ma_fill 维护处于Active态和Dummy态的entry数；
ma_used维护处于Active态的entry数；
ma_mask指PyDictObject中所有entry数；
ma_table域 指向PyDictObject中的entry，当其数量小于等于PyDict_MINSIZE(8)时，指向ma_smalltable，否者申请内存指向该内存；
ma_lookup后面说；
3、PyDictObject的创建与维护
3.1.1、PyDictObject对象创建
[dictobject.c] typedef PyDictEntry dictentry; typedef PyDictObject dictobject;
#define INIT_NONZERO_DICT_SLOTS(mp) do { \
(mp)->ma_table = (mp)->ma_smalltable; \
(mp)->ma_mask = PyDict_MINSIZE - ; \
} while()
memset((mp)->ma_smalltable, , sizeof((mp)->ma_smalltable)); \
(mp)->ma_used = (mp)->ma_fill = ; \
INIT_NONZERO_DICT_SLOTS(mp); \
} while()
PyObject* PyDict_New(void)
{
register dictobject *mp;
if (dummy == NULL) { /* Auto-initialize dummy */
dummy = PyString_FromString("<dummy key>");
if (dummy == NULL)
return NULL;
}
if (num_free_dicts)
{
…… //使用缓冲池
}
else
{
mp = PyObject_GC_New(dictobject, &PyDict_Type);
if (mp == NULL)
return NULL;
EMPTY_TO_MINSIZE(mp);
}
mp->ma_lookup = lookdict_string;
_PyObject_GC_TRACK(mp);
return (PyObject *)mp;
}
创建PyDictObject时，会先创建一个字符串对象dummy，用作指示标志，表面entry曾被使用，也用于探测序列；
num_free_dicts是dict的缓冲池，后面讲；
然后开始创建，将ma_smalltable、ma_used、ma_fill清0，然后ma_table指向ma_smalltable，设置ma_mash，最后将lookdict_string 赋予 ma_lookup。
3.1.2、元素搜索
PyDictObject有两种搜索策略，lookdict和lookdict_string，lookdict_string是lookdict对PyStringObject的特化。其中lookdict_string：
[dictobject.c]
static dictentry* lookdict_string(dictobject *mp, PyObject *key, register long hash)
{
register int i;
register unsigned int perturb;
register dictentry *freeslot;
register unsigned int mask = mp->ma_mask;
dictentry *ep0 = mp->ma_table;
register dictentry *ep;
if (!PyString_CheckExact(key)) {
mp->ma_lookup = lookdict;
return lookdict(mp, key, hash);
}
//[1]
i = hash & mask;
ep = &ep0[i];
//[2]
//if NULL or interned
if (ep->me_key == NULL || ep->me_key == key)
return ep;
//[3]
if (ep->me_key == dummy)
freeslot = ep;
else
{
//[4]
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 << ) + i + perturb + ;
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;
}
}
其中关键步骤标注[1][2][3][4]，后面讲。
lookdict_string是在key为PyStringObject的情况下使用，否则使用lookdict：
[dictobject.c]
static dictentry* lookdict(dictobject *mp, PyObject *key, register long hash)
{
register int i;
register unsigned int perturb;
register dictentry *freeslot;
register unsigned int mask = mp->ma_mask;
dictentry *ep0 = mp->ma_table;
register dictentry *ep;
register int restore_error;
register int checked_error;
register int cmp;
PyObject *err_type, *err_value, *err_tb;
PyObject *startkey;
//[1]
i = hash & mask;
ep = &ep0[i];
//[2]
if (ep->me_key == NULL || ep->me_key == key)
return ep;
//[3]
if (ep->me_key == dummy)
freeslot = ep;
else
{
//[4]
if (ep->me_hash == hash)
{
startkey = ep->me_key;
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
if (cmp < )
PyErr_Clear();
if (ep0 == mp->ma_table && ep->me_key == startkey)
{
//只有key相等才会返回已有位置，否者会寻找下一个位置
if (cmp > )
goto Done;
}
else
{
/* The compare did major nasty stuff to the
* dict: start over.
* XXX A clever adversary could prevent this
* XXX from terminating.
*/
ep = lookdict(mp, key, hash);
goto Done;
}
}
freeslot = NULL;
}
。。。。。。
Done:
return ep;
}
由于PyDictObject中维护dict数量是有限的（ma_table的长度），而计算出的hash值可能超过此范围，故需要与ma_mask进行与操作获得下标，因此ma_mask 名字 不是 ma_size。
其中freeslot用来指向第一次搜索序列中的Dummy态entry，如果搜索失败返回freeslot指向的Dummy态entry，如果没有Dummy态entry，返回Unused态entry（都可指示搜索失败）。
下面是lookdict中进行第一次检查时需要注意的动作：
[1]：根据hash值获得entry的序号。
[2]：如果ep->me_key为NULL，且与key相同，搜索失败。
[3]：若当前entry处于Dummy态，设置freeslot。
[4]：检查当前Active的entry中的key与待查找的key是否相同，如果相同，则立即返回，搜索成功。
在[4]中，需要注意那个PyObject_RichCompareBool，它的函数原形为：
int PyObject_RichCompareBool(PyObject *v, PyObject *w, int op)
当(v op w)成立时，返回1；当(v op w)不成立时，返回0；如果在比较中发生错误，则返回-1。
在lookdict中，当第一次hash值获得的entry与待查找元素比较发现不一样时，会继续在探测序列上查找：
[dictobject.c]
static dictentry* lookdict(dictobject *mp, PyObject *key, register long hash)
{
register int i;
register unsigned int perturb;
register dictentry *freeslot;
register unsigned int mask = mp->ma_mask;
dictentry *ep0 = mp->ma_table;
register dictentry *ep;
register int restore_error;
register int checked_error;
register int cmp;
PyObject *err_type, *err_value, *err_tb;
PyObject *startkey;
。。。。。。
for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
{
//[5]
i = (i << ) + i + perturb + ;
ep = &ep0[i & mask];
//[6]
if (ep->me_key == NULL)
{
if (freeslot != NULL)
ep = freeslot;
break;
}
if (ep->me_key == key)//[7]
break;
if (ep->me_hash == hash && ep->me_key != dummy)
{
startkey = ep->me_key;
cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);
if (cmp < )
PyErr_Clear();
if (ep0 == mp->ma_table && ep->me_key == startkey) {
if (cmp > )
break;
}
else {
ep = lookdict(mp, key, hash);
break;
}
}
//[8]
else if (ep->me_key == dummy && freeslot == NULL)
freeslot = ep;
}
Done:
return ep;
}
[5]：获得探测序列中的下一个待探测的entry。
[6]：ep到达一个Unused态entry，表明搜索结束。这是如果freeslot不为空，则返回freeslot所指entry。
[7]：entry与待查找的key匹配，搜索成功。
[8]：在探测序列中发现Dummy态entry，设置freeslot。
比较lookdict_string与lookdict可发现，lookdict_string是lookdict针对PyStringObject的简化版，而且效率要高很多。Python自身也大量使用PyDictObject对象，大都使用PyStringObject作为key，故lookdict_string对Python整理运行效率都有重要影响。
搜索部分内容比较多，代码比较长，有兴趣好好琢磨。lookdict_string相当于在hash值相同的探索链上找，调用一次可以找到；lookdict差不多，不过里面key对象不一定是PyStringObject，所以多了一些检查、判断函数，还多了一个递归找的逻辑（判断逻辑：只有key相等才返回已有位置，否者会寻找下一个位置）。
***标记一下有一点不太理解：
if (ep0 == mp->ma_table && ep->me_key == startkey)
啥意思。。
***
3.1.3、插入与删除
PyDictObject插入建立在搜索上：
[dictobject.c]
static void
insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
{
PyObject *old_value;
register dictentry *ep;
ep = mp->ma_lookup(mp, key, hash);
//[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);
}
//[2]
else {
if (ep->me_key == NULL)
mp->ma_fill++;
else
Py_DECREF(ep->me_key);
ep->me_key = key;
ep->me_hash = hash;
ep->me_value = value;
mp->ma_used++;
}
}
搜索结果可能是Active态的entry，也可能是Dummy或Unused态的entry；对于前者只需替换me_value，对于后者要设置其他值：
[1] ：搜索成功，返回处于Active的entry，直接替换me_value。
[2] ：搜索失败，返回Unused或Dummy的entry，完整设置me_key，me_hash和me_value。
在调用insertdict前会调用PyDict_SetItem：
[dictobject.c]
int PyDict_SetItem(register PyObject *op, PyObject *key, PyObject *value)
{
register dictobject *mp;
register long hash;
register int n_used;
mp = (dictobject *)op;
//计算hash值
if (PyString_CheckExact(key)) {
hash = ((PyStringObject *)key)->ob_shash;
if (hash == -)
hash = PyObject_Hash(key);
}
else {
hash = PyObject_Hash(key);
if (hash == -)
return -;
}
n_used = mp->ma_used;
Py_INCREF(value);
Py_INCREF(key);
insertdict(mp, key, hash, value);
if (!(mp->ma_used > n_used && mp->ma_fill* >= (mp->ma_mask+)*))
return ;
return dictresize(mp, mp->ma_used*(mp->ma_used> ? : ));
}
首先会获得key的hash值，在插入元素后会判断是否需要改变ma_table大小。判断条件为装载率大于2/3（(mp->ma_fill)/(mp->ma_mask+1) >= 2/3）而且使用了Unused态的entry（mp->ma_used > n_used）。在改变table时可能是增加也可能是减少，新增大小为table中Active态的entry数的2或4倍（看数量是否超过50000）。
改变table大小则由dictresize负责：
[dictobject.c]
static int dictresize(dictobject *mp, int minused)
{
int newsize;
dictentry *oldtable, *newtable, *ep;
int i;
int is_oldtable_malloced;
dictentry small_copy[PyDict_MINSIZE];
//[1]
for(newsize = PyDict_MINSIZE; newsize <= minused && newsize > ; newsize <<= )
;
oldtable = mp->ma_table;
assert(oldtable != NULL);
is_oldtable_malloced = oldtable != mp->ma_smalltable;
//[2]
if (newsize == PyDict_MINSIZE) {
newtable = mp->ma_smalltable;
if (newtable == oldtable) {
if (mp->ma_fill == mp->ma_used) {
//没有任何Dummy态entry,直接返回
return ;
}
//将oldtable拷贝，进行备份
assert(mp->ma_fill > mp->ma_used);
memcpy(small_copy, oldtable, sizeof(small_copy));
oldtable = small_copy;
}
}
else {
newtable = PyMem_NEW(dictentry, newsize);
}
//[3]
assert(newtable != oldtable);
mp->ma_table = newtable;
mp->ma_mask = newsize - ;
memset(newtable, , sizeof(dictentry) * newsize);
mp->ma_used = ;
i = mp->ma_fill;
mp->ma_fill = ;
//[4]
for (ep = oldtable; i > ; ep++) {
if (ep->me_value != NULL) { /* active entry */
--i;
insertdict(mp, ep->me_key, 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);
}
}
if (is_oldtable_malloced)
PyMem_DEL(oldtable);
return ;
}
[1] ：dictresize首先会确定新的table的大小，很显然，这个大小一定要大于传入的参数minused，这也是在原来的table中处于Active态的entry的数量。dictresize从8开始，以指数方式增加大小，直到超过了minused为止。所以实际上新的table的大小在大多数情况下至少是原来table中Active态entry数量的4倍。
[2] ：如果在[1]中获得的新的table大小为8，则不需要在堆上分配空间，直接使用ma_smalltable就可以了；否则，则需要在堆上分配空间。
[3] ：对新的table进行初始化，并调整原来PyDictObject对象中用于维护table使用情况的变量。
[4] ：对原来table中的非Unused态entry进行处理。对于Active态entry，显然需要将其插入到新的table中，这个动作由前面考察过的insertdict完成；而对于Dummy态的entry，则略过，不做任何处理，因为我们知道Dummy态entry存在的唯一理由就是为了不使搜索时的探测序列中断。现在所有Active态的entry都重新依次插入新的table中，它们会形成一条新的探测序列，不再需要这些Dummy态的entry了。
从PyDictObject中删除一个元素：
[dictobject.c]
int PyDict_DelItem(PyObject *op, PyObject *key)
{
register dictobject *mp;
register long hash;
register dictentry *ep;
PyObject *old_value, *old_key;
//获得hash值
if (!PyString_CheckExact(key) ||
(hash = ((PyStringObject *) key)->ob_shash) == -) {
hash = PyObject_Hash(key);
if (hash == -)
return -;
}
//搜索entry
mp = (dictobject *)op;
ep = (mp->ma_lookup)(mp, key, hash);
//删除entry所维护的元素
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 ;
}
先获取hash值，取到entry后将entry从Active态转为Dummy态，再调整相关变量。
4、PyDictObject 对象缓冲池
PyDictObject和PyListObject一样也使用缓冲池技术：
[dictobject.c] #define MAXFREEDICTS 80 static PyDictObject *free_dicts[MAXFREEDICTS]; static int num_free_dicts = ;
而且和PyListObject的缓冲池类似，在PyDictObject对象被销毁时才把内存加入缓冲池：
[dictobject.c]
static void dict_dealloc(register dictobject *mp)
{
register dictentry *ep;
int fill = mp->ma_fill;
PyObject_GC_UnTrack(mp);
Py_TRASHCAN_SAFE_BEGIN(mp)
//调整dict中对象的引用计数
for (ep = mp->ma_table; fill > ; 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);
//将被销毁的PyDictObject对象放入缓冲池
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)
}
缓冲池中只保留了PyDictObject对象，里面从堆上申请的table则会被销毁，归还系统。如果被销毁的PyDictObject对象只是用了固有的ma_smalltable，那只需调整ma_smalltable中对象的引用计数。
在创建PyDictObject对象时，缓冲池有则直接从缓冲池取：
[dictobject.c]
PyObject* PyDict_New(void)
{
register dictobject *mp;
…………
if (num_free_dicts) {
mp = free_dicts[--num_free_dicts];
_Py_NewReference((PyObject *)mp);
if (mp->ma_fill) {
EMPTY_TO_MINSIZE(mp);
}
}
…………
}
5、Hack PyDictObject
python内部大量使用PyDictObject，每个小小调用都会对insertdict频繁调用，故打印的话可用特征串，打印：
static void ShowDictObject(dictobject* dictObject)
{
dictentry* entry = dictObject->ma_table;
int count = dictObject->ma_mask+;
int i;
for(i = ; i < count; ++i)
{
PyObject* key = entry->me_key;
PyObject* value = entry->me_value;
if(key == NULL)
{
printf("NULL");
}
else
{
(key->ob_type)->tp_print(key, stdout, );
}
printf("\t");
if(value == NULL)
{
printf("NULL");
}
else
{
(key->ob_type)->tp_print(value, stdout, );
}
printf("\n");
++entry;
}
}
static void
insertdict(register dictobject *mp, PyObject *key, long hash, PyObject *value)
{
……
{
dictentry *p;
long strHash;
PyObject* str = PyString_FromString("Python_Robert");
strHash = PyObject_Hash(str);
p = mp->ma_lookup(mp, str, strHash);
if(p->me_value != NULL && (key->ob_type)->tp_name[] == 'i')
{
PyIntObject* intObject = (PyIntObject*)key;
printf("insert %d\n", intObject->ob_ival);
ShowDictObject(mp);
}
}
}
调用print的时候也会调用到dealloc，所以num_free_dicts的值变化可能和想象的不一样。