起步
python中PyDictObject采用了散列表,平均状况是O(1)复杂度的搜索效率.
散列表是通过一定的函数将需搜索的键值映射为一个整数,将这个整数视为索引去访问某片连续的内存区域. 一般情况下,hash table会申请一块较大的连续内存通过映射函数f(n)得到所对应的索引.
在使用散列表过程中,随着需要存储的数据增多,hash冲突的概率就越高.会直接影响到hash的效率和性能.
在python中采用闭散列法来解决冲突,闭散列法也称为开放定址法.当产生冲突时,python会通过一个二次探测函数f,计算下一个候选索引, 如果索引不可用,就再次用f探测.直到找到一个可用的位置.
之所以叫做闭散列法，就是因为冲突的元素没有开辟额外的存储空间，还是在原先hash表的空间范围之内。
关联容器
假如我们将具有某种关系的两个数组成一组,例如(3, 6), (4, 8),他们具有2倍关系, 组成一组的好处就是找到3就能立马找到6.
因此关联容器常以(key, value)存在.Python中定义这样的关联容器Entry:
[dict-common.h]
typedef struct {
Py_hash_t me_hash;
PyObject *me_key;
PyObject *me_value;
} PyDictKeyEntry;在PyDictKeyEntry中,me_hash表示me_key的散列值, 保存这个值是为了避免重复计算. 在PyDictObject对象发生变化时, 其中的entry也会在不同的状态间切换.关联容器存在3中状态:
- Unused(未使用):
index == DKIX_EMPTY - Active(活动):
index >= 0, me_key != NULL and me_value != NULL - Dummy(删除状态):
index == DKIX_DUMMY之所以不能直接转成Unused状态是因为这要会导致冲突测链中断
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) /* Used internally */
#define DKIX_ERROR (-3)关联容器的实现
[dictobject.h]
typedef struct {
PyObject_HEAD
// Active元素个数
Py_ssize_t ma_used;
// 全局唯一, 值会随着dict的修改而改变
uint64_t ma_version_tag;
PyDictKeysObject *ma_keys;
// 如果ma_values == NULL 表示哈希表是结合的, 如果ma_values != NULL 则表被拆分
PyObject **ma_values;
} PyDictObject;PyDictKeysObject是这样定义的:
[dict-common.h]
struct _dictkeysobject {
Py_ssize_t dk_refcnt;
// hash表允许容纳元素的个数 必定是2的指数
Py_ssize_t dk_size;
// 与hash table有关的函数
dict_lookup_func dk_lookup;
// 元素个数 Active + Dummy
Py_ssize_t dk_usable;
// 元素个数 Active
Py_ssize_t dk_nentries;
union {
int8_t as_1[8];
int16_t as_2[4];
int32_t as_4[2];
} dk_indices;
};“PyDictKeyEntry dk_entries [dk_usable];” 数组如下,参阅DK_ENTRIES()宏:
#define DK_ENTRIES(dk) \
((PyDictKeyEntry*)(&(dk)->dk_indices.as_1[DK_SIZE(dk) * DK_IXSIZE(dk)]))从python3.6开始,借鉴 PyPy 字典设计，采用更紧凑的存储结构.内存效率更高, 更多信息可以查看https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html
key可以分布如下:
+---------------+
| dk_refcnt |
| dk_size |
| dk_lookup |
| dk_usable |
| dk_nentries |
+---------------+
| dk_indices |
| |
+---------------+
| dk_entries |
| |
+---------------+dk_indices 是实际的哈希表。它在条目中保存索引，或KIX_EMPTY（-1）或DKIX_DUMMY（-2）。哈希表能容纳元素的个数 dk_size .dk_entries是一个PyDictKeyEntr的数组。它的大小是USABLE_FRACTION（dk_size）。
可以使用DK_ENTRIES（dk）来获取指向条目的指针。注意：由于负值用于DKIX_EMPTY和DKIX_DUMMY，所以键入
dk_indices条目是有符号整数，int16用于表大小dk_size == 256。
为什么说更省空间呢?
比如需要一个字典d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'},那其结构在旧模式下是:
entries = [['--', '--', '--'],
[-8522787127447073495, 'barry', 'green'],
['--', '--', '--'],
['--', '--', '--'],
['--', '--', '--'],
[-9092791511155847987, 'timmy', 'red'],
['--', '--', '--'],
[-6480567542315338377, 'guido', 'blue']]而使用新的为:
indices = [None, 1, None, None, None, 0, None, 2]
entries = [[-9092791511155847987, 'timmy', 'red'],
[-8522787127447073495, 'barry', 'green'],
[-6480567542315338377, 'guido', 'blue']]indices就是哈希表,改变的只是布局, 哈希表算法将不变.例子中节省了得58%的内存。据说能节省30%~95~的空间(取决表的完整程度). 除了节省空间, 新的布局迭代更快, keys() values() items(),直接在关联容器entries获取, 无需判断['--', '--', '--']空关联容器. 移动或者复制hash表,只需操作indices即可.
请注意，sizeof（index）可以小到单个小字节的字节，大字节的两个字节直到sizeof（Py_ssize_t）为巨大的dict。因此可以看到PyDictKeyObject中的dk_indices是个联合体.为了是更省内存. 作者很抠内存的, 巴不得一个字节当两个字节用.
PyDictObject 对象的创建
python内部通过PyDict_New来创建一个新的dict对象:
[dictobject.h]
PyObject * PyDict_New(void)
{
PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
if (keys == NULL)
return NULL;
return new_dict(keys, NULL);
}PyDict_MINSIZE 值为8, 默认情况下, PyDict_New会创建8个entry
static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
PyDictKeysObject *dk;
Py_ssize_t es, usable;
usable = USABLE_FRACTION(size);
es = 4;
if (size == PyDict_MINSIZE && numfreekeys > 0) {
// 使用缓冲池
dk = keys_free_list[--numfreekeys];
}
else {
dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
- Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
+ es * size
+ sizeof(PyDictKeyEntry) * usable);
}
DK_DEBUG_INCREF dk->dk_refcnt = 1;
dk->dk_size = size;
dk->dk_usable = usable;
dk->dk_lookup = lookdict_unicode_nodummy;
dk->dk_nentries = 0;
// hash table 初始化
memset(&dk->dk_indices.as_1[0], 0xff, es * size);
memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
return dk;
}keys.entries 和 values 用数组按添加顺序存储主键和值引用。实际哈希表由 keys.indices 数组承担，通过计算主键哈希值找到合适位置，然后在此存储主键在 keys.entries 的实际索引。如此，只要通过 indices 获取实际索引后，就可读取主键和值信息。
dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
- Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
+ es * size // hash索引表
+ sizeof(PyDictKeyEntry) * usable); // PyDictKeyEntry 的数组, 申请大小为表size的2/3也就是说 PyDictKeysObject 中成员 dk_indices 有两个重要的成分, 一个是前半部分的hash table索引. 另一个是后半部分的关联容器数组
元素搜索
无论是字典的设置d["aaa"] = 3 还是获取 a = d["aaa"] 都需要对hash table进行搜索.
python位hash表搜索提供了多种函数, 通用的lookdict, 针对字符串类型的lookdict_unicode, 针对数字的 lookdict_index. 但他们的算法是相同的.
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;
PyDictKeysObject *dk;
PyDictKeyEntry *ep0;
top:
dk = mp->ma_keys;
ep0 = DK_ENTRIES(dk);
mask = DK_MASK(dk);
perturb = hash;
i = (size_t)hash & mask; // mask是2的指数-1, 因此相当于取模
for (;;) {
Py_ssize_t ix = dk_get_index(dk, i);// dk->indecs[i]
if (ix == DKIX_EMPTY) {
*value_addr = NULL;
return ix;
}
if (ix >= 0) {
PyDictKeyEntry *ep = &ep0[ix];
assert(ep->me_key != NULL);
if (ep->me_key == key) { // 同一个引用
*value_addr = ep->me_value;
return ix;
}
if (ep->me_hash == 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; // 哈希探测函数
}
assert(0); /* NOT REACHED */
return 0;
}dk_get_index(dk, i) 简单理解为->dk_indices.as_1[i] 即可, 对于不同规模的hash表, 用as_1或as_2有所不同而已. 对于lookdict来说, 永远不会返回NULL, 如果搜索不到待查找的key, 同样会返回一个空的关联容器的索引.
在python的字典中,"相同"这个概念包含了两个含义:
- 引用相同
- 值相同
在
lookdict中ep->me_key == key就意味着他们的值相同, 在其判断体内加printf("key is same\n");可以看到:
>>> a = {}
>>> a[2] = "python"
>>> a[2]
key is same
'python'
>>> a[999] = "php"
>>> a[999]
'php'
>>>小整数对象是共享的, 因此他们key都是指向同一个地址. 大整数对象并不是共享, 但是999明明在key中是存在的,因此"值相同"规则就有存在的意义.
总结搜索过程入下:
- 根据
PyObject *key的哈希值获得entry索引, 这是冲突探测链上第一个entry索引. - 两种情况下,搜索结束:
- entry处于Unuse状态,表示冲突弹窗搜索结束, 搜索失败
ep->me_key == key表示entry的key与待搜索key是同一个PyObject对象, 搜索成功
- 若当前的entry处于Dummy态, 设置为freeslot
- 检查Active态中的entry中的key是否与待查找的key"值相同", 若找到, 搜索成功. 若不匹配, 则沿着探测链查找.探测链检测到DUMMY状态是,设置freeslot
当entry中的key与待查找的key不匹配时, 拦着探测链顺藤摸瓜.
探测链上的过程与前面的过程基本一致, 总之,lookdict 如果搜索成功, 返回一定是有效的entry索引.如果搜索失败,则返回一个Unused状态的entry索引.因为dummy状态的entry实际也是一个空闲的entry, 当遍历到Dummy状态的entry,便会设置freeslot,freeslot是下一个被inserted的索引.
其他搜索策略都差不多. 哦对了, 默认的搜索策略是 lookdict_unicode_nodummy 介绍说比lookdict_unicode快,不清楚为什么搜索出来的entry不含dummy的.
python内部也大量使用的PyDictObject对象, 如维护一个名字空间的变量名与值的关系, 函数传递参数时参数名与参数值的关系.
hash冲突时采用 i = ((i << 2) + i + perturb + 1) & mask; 即 i = (i * 5 + i) % dk_size; 因为dk_size是2的指数, 所以这个探测正好能遍历所有元素.
插入
关于dict的操作基本都是建立在搜索的基础上的.
static int insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;
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;
// 检查...
// 检查共享key, 必要时进行hash表扩容
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) {
/* Insert into new slot. */
assert(old_value == NULL);
if (mp->ma_keys->dk_usable <= 0) {
/* Need to resize. */
if (insertion_resize(mp) < 0)
goto Fail;
}
Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
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;
ep->me_hash = hash;
if (mp->ma_values) {
assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
mp->ma_values[mp->ma_keys->dk_nentries] = value;
}
else {
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++; // 关联容器数量+1
assert(mp->ma_keys->dk_usable >= 0);
assert(_PyDict_CheckConsistency(mp));
return 0;
}
// ...
DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
mp->ma_version_tag = DICT_NEXT_VERSION();// 版本号+1
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;
}在搜索的lookup函数中, 返回的关联容器状态有两个结果:搜索成功是,返回的是Active的entry,这种情况下直接替换即可*value_addr = value;. 搜索不成功是, 返回的是Unuse或Dummy状态的关联容器,需要完整设置me_key,me_hash,me_value. python代码中 d["aaa"] = 4 其实是调用 PyDict_SetItem 的:
int PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
PyDictObject *mp;
Py_hash_t hash;
mp = (PyDictObject *)op;
if (!PyUnicode_CheckExact(key) ||
(hash = ((PyASCIIObject *) key)->hash) == -1)
{
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
/* insertdict() handles any resizing that might be necessary */
return insertdict(mp, key, hash, value);
}如果key只是替换现有的值,也就是当搜索成功时. 是不改变hash table大小的. 这就意味着 PyDict_Next() 循环使用字典是安全的了.
insertdict中会重新resize哈希表:
// 增长率
#define GROWTH_RATE(d) (((d)->ma_used*2)+((d)->ma_keys->dk_size>>1))
static int insertion_resize(PyDictObject *mp)
{
return dictresize(mp, GROWTH_RATE(mp));
}改变table的大小交到了dictresize身上.
static int dictresize(PyDictObject *mp, Py_ssize_t minsize)
{
Py_ssize_t i, newsize;
PyDictKeysObject *oldkeys;
PyObject **oldvalues;
PyDictKeyEntry *ep0;
/* Find the smallest table size > minused. */
for (newsize = PyDict_MINSIZE;
newsize < minsize && newsize > 0;
newsize <<= 1)
;
oldkeys = mp->ma_keys;
oldvalues = mp->ma_values;
// 申请新空间
mp->ma_keys = new_keys_object(newsize);
if (oldkeys->dk_lookup == lookdict)
mp->ma_keys->dk_lookup = lookdict;
mp->ma_values = NULL;
ep0 = DK_ENTRIES(oldkeys);
/* Main loop below assumes we can transfer refcount to new keys
* and that value is stored in me_value.
* Increment ref-counts and copy values here to compensate
* This (resizing a split table) should be relatively rare */
if (oldvalues != NULL) {
// 搬迁list
for (i = 0; i < oldkeys->dk_nentries; i++) {
if (oldvalues[i] != NULL) {
Py_INCREF(ep0[i].me_key);
ep0[i].me_value = oldvalues[i];
}
}
}
// 旧hash表到新hash表搬迁, hash值不会重新计算, 但关联容器索引会重新计算
for (i = 0; i < oldkeys->dk_nentries; i++) {
PyDictKeyEntry *ep = &ep0[i];
if (ep->me_value != NULL) {
insertdict_clean(mp, ep->me_key, ep->me_hash, ep->me_value);
}
}
...
return 0;
}resize将hash表容量扩大两倍, 然后搬迁数据, 表hash索引不需要重新计算.
