Python解释器实现:dict类型
目录

Python dict的数据结构为散列表(hash table),最优情况下查找效率为O(1)。

object and type

Python dict 数据结构定义如下:

#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 */

/* 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];
};

虽然我们通过len(dictobject)可以获得dict包含对象的个数,但是PyDictObject的头部并不是 可变类型头部PyObject_VAR_HEAD,并不包含ob_size字段。ma_used字段记录了包含对象的 个数。

dict中每个对象都是这样的键值对,用PyDictEntry结构表示。 key必须是immutable类型对象,因为要计算hash。

/* Object used as dummy key to fill deleted entries */
static PyObject *dummy = NULL; /* Initialized by first call to newPyDictObject() */

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;

PyDictEntry的三种状态:

  • Unused: me_hash==me_key==me_value==NULL
  • Acitve: me_hash!=NULL, me_key!=NULL&dummy, me_value!=NULL
  • Dummy: me_hash!=NULL, me_key==dummy, me_value==NULL

Dummy状态为了解决冲突链中断问题,后面小节会提到。

Unused  -->  Active  <-->  Dummy

ma_table字段保存了PyDictEntry数组作为哈希表, ma_lookup为哈希表查找方法, ma_mask表示了哈希表大小减1,因为哈希表大小为2的幂,所以ma_mask是个低位全为1高位全为0掩码, 用于计算键hash的有效位。

PyTypeObject PyDict_Type = {
PyVarObject_HEAD_INIT(&amp;PyType_Type, 0)
"dict",
sizeof(PyDictObject),
0,
(destructor)dict_dealloc,                   /* tp_dealloc */
(printfunc)dict_print,                      /* tp_print */
0,                                          /* tp_getattr */
0,                                          /* tp_setattr */
(cmpfunc)dict_compare,                      /* tp_compare */
(reprfunc)dict_repr,                        /* tp_repr */
0,                                          /* tp_as_number */
&amp;dict_as_sequence,                          /* tp_as_sequence */
&amp;dict_as_mapping,                           /* tp_as_mapping */
(hashfunc)PyObject_HashNotImplemented,      /* tp_hash */
0,                                          /* tp_call */
0,                                          /* tp_str */
PyObject_GenericGetAttr,                    /* tp_getattro */
0,                                          /* tp_setattro */
0,                                          /* tp_as_buffer */
Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
Py_TPFLAGS_BASETYPE | Py_TPFLAGS_DICT_SUBCLASS,         /* tp_flags */
dictionary_doc,                             /* tp_doc */
dict_traverse,                              /* tp_traverse */
dict_tp_clear,                              /* tp_clear */
dict_richcompare,                           /* tp_richcompare */
0,                                          /* tp_weaklistoffset */
(getiterfunc)dict_iter,                     /* tp_iter */
0,                                          /* tp_iternext */
mapp_methods,                               /* tp_methods */
0,                                          /* tp_members */
0,                                          /* tp_getset */
0,                                          /* tp_base */
0,                                          /* tp_dict */
0,                                          /* tp_descr_get */
0,                                          /* tp_descr_set */
0,                                          /* tp_dictoffset */
dict_init,                                  /* tp_init */
PyType_GenericAlloc,                        /* tp_alloc */
dict_new,                                   /* tp_new */
PyObject_GC_Del,                            /* tp_free */
};

查找与散列冲突

散列冲突的解决方法:

  • 开链法(chaining):CPP STL hast table,需要大量内存操作
  • 开放定址法(open addressing): Python dict

Python使用后者,因为不需要再次申请内存。 针对查找操作,Python提供lookdict(PyDictObject *mp, PyObject *key, register long hash) 这个通用函数,并且如果查找不成功,则返回key对应的空闲entry。 Python针对key为string的查找有一个特殊函数lookdict_string(PyDictObject *mp, PyObject *key, register long hash), 这个函数对key为string类型的查找进行了优化。因为Python内部大量使用dict维护变量名和变量值之间的关系, 这个特殊函数加快了Python的执行速度。

需要注意的是,Python在查找时,首先key的hash值比较,再次key的值比较,而不是内存引用地址比较。

当散列表的装载率超过2/3时,散列冲突的概率就会大大增加,此时应扩大哈希表。 Python中的扩大策略是:

  • ma_used > 5000,扩大2倍
  • ma_used <= 5000,扩大4倍

ma_smalltable

PyDictObjectsmalltable字段所包含的大小为8的数组是伴随dict对象创建就生成的小哈希表, 在初始化完成后ma_table首先指向这个数组。 这是一个优化,8也是一个经验值。 因此当dict对象中成员小于8个时,就不必再次申请内存。

缓冲池

PyListObject一样,PyDictObject也使用缓冲池来减少内存申请。

/* Dictionary reuse scheme to save calls to malloc, free, and memset */
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;

发表评论