本系列作为本人@takooctopus深入学习python机制的记录,这个博客遵照着栖迟于一丘的博客上面的流程进行的,也包含我在实际查看源码时的感想,特此列出,表示感谢。
关于Dict对象
python中的dict
对象也即PyDictObject
对象,因为对搜索的效率要求很高,所以选择了散列表(hash table),因为在最优情况下,散列表能够提供O(1)的搜索效率。
散列表的基本思想是:通过一定的函数将需要搜索的键值映射为一个整数,根据这个整数作为索引去访问某片连续的内存区域。用于映射的函数称为映射函数,映射所产生的值称为散列值(hash value
)。散列函数对搜索效率有直接的决定性作用。在使用散列函数将不同的值可能映射到相同的散列值,这个时候就需要冲突解决(装载率大于2/3时,冲突的概率就会大大增加)
冲突解决在python中使用的是开放定址法「闭散列法」,就是通过一个二次探测函数f,计算下一个位置,一直到找到下一个可用的位置为止,在这个过程中会到达多个位置,这些位置就形成了一个“冲突探测链”,这个冲突探测链在查找某个元素的时候起到重要作用,所以在删除某个位置上的元素,不能直接将这个位置的内容删除,如果删除的话,则导致后续依赖于这个位置的其他值就都无法寻找到了,所以只能进行“伪删除”(通过给元素设置状态,dummy态,表示没有存储具体的值但是还会用到的废弃态)
先列出PyDictObject
的定义:
{{- code -}}
我们看到其中属性中除了对象类型、Active
元素个数,全局唯一idma_version_tag
,还有一个类PyDictKeys
,以及一个PyObject
的指针。我们去看一看它的定义:
{{- code -}}
我们看见_dictkeysobject
的属性中包含了引用数dk_refcnt
,键数dk_size = 2^n
,以及哈希表寻找的函数dk_lookup
「包含了4种函数」,Active + Dummy
的元素个数dk_usable
,Active
的元素个数dk_nentries
,以及哈希表的索引dk_indices[]
「其中每个单元的大小与dk_size
的大小有关」
{{- code -}}
我们可以看见在这里设立了三个宏,表示了entry
键值对的对象状态。
那么什么是entry
键值对呢,其被称为关联容器,即PyDictKeyEntry
{{- code -}}
在dict_lookup_func()
中会返回键值对的index
「主键」,我们可以像DK_ENTRIES(dk)[index]
的方式使用主键,其三个值-1
代表没有找到这个关联容器,-3
代表当其比较时返回错误,-2
的dummy
代表了一种伪删除状态。
当然上面那个是在寻找键值对关联容器时的返回值,但关联容器本身也是有三种状态的。
- Unused(未使用):
index == DKIX_EMPTY
- Active(活动):
index >= 0
,me_key != NULL
andme_value != NULL
- Dummy(删除状态):
index == DKIX_DUMMY
之所以不能直接转成Unused状态是因为这要会导致冲突探测链中断
新的PyPyDict
在其文档中提到现在其使用了新的PyPy字典结构
在此简单的提一下其两者的差别:
原来的字典结构:
{{- code -}}
其dict
由一大块内存区组成,并伴有指向数组的指针。这些关联容器数组实际上是一个稀疏数组「其中大约1/3到1/2的空间是NULL
」,形成大量的空间浪费。
相比之下新的字典结构:
{{- code -}}
其dict
的实现使用了两个数组,一个用于存储索引的sparse_array[]
,其中只存储有符号的整数「+
」用作hash的索引以及KIX_EMPTY「-1」
或DKIX_DUMMY「-2」
。另一个compact_array []
按照插入顺序储存所有的关联容器。
因为在sparse_array[]
中存储的其实是在compact_array[]
中item
所在的插入序号,当改变sparse_array[]
中的排列时,只是索引变化,不需要改动我们实际上存储的关联容器的储存顺序。
这个设计不仅减少了操作量,更重要的是其节省内存的功能。因为sparse_array[]
中存储的都是int
,其内存占用量极小。举例来说,在64位系统下,我们最多,虽然几乎用不到,能储存大约40亿个元素。对于一个100个元素的字典,原来的字典设计会占用大约100 * 12/7 * WORD * 3 =~ 4100 bytes
,而新的字典设计仅需要100 * 12/7 + 3 * WORD * 100 =~ 2600 bytes
,内存使用大大减少。
PyDictObject的创建操作
简单的,其通过PyDict_New()
来新建一个dict
对象
{{- code -}}
其默认#define PyDict_MINSIZE 8
,即会附带创建8个关联容器PyDictKeyEntry
{{- code -}}
其分配的大小随size
的大小分成了几个区间。
我们看其最后分配的内存空间,当没有使用缓冲池时,其分配的内存为
{{- code -}}
包含了三个部分,第一个sizeof(PyDictKeysObject)
是这个空对象的内存大小,第二个是hash索引表的大小,第三个sizeof(PyDictKeyEntry) * usable
是申请的关联容器数组的大小,这里usable
一般取在1/2
到2/3
就比较合适。
{{- code -}}
在创建完主键对象后,再继续创建关联容器对象组,即dict
的对象。
PyDictObject的获取操作
获取Dict对象时我们调用的是PyDict_GetItem()
{{- code -}}
我们在进行了类型检查和字符检查后,在确定其状态不为empty「-1」
后,我们调用其属性中的dk_lookup
,这个是查找方法,在类的初始化时被定义,有四种可能性:
-
lookdict(): general-purpose, and may return DKIX_ERROR if (and only if) a comparison raises an exception.
-
lookdict_unicode(): specialized to Unicode string keys, comparison of which can never raise an exception; that function can never return DKIX_ERROR.
-
lookdict_unicode_nodummy(): similar to lookdict_unicode() but further specialized for Unicode string keys that cannot be the
value. -
lookdict_split(): Version of lookdict() for split tables.
一般来说,lookdict()
是通用的方法,我们去看一下其具体内容:
{{- code -}}
首先mask
值是2^(dk->dk_size)-1
,i
相当于对其取模。
在循环中,在取出第dict表中的稀疏数组parse_array[]
即dk_indices[]
,直接取出对应位置i的关联容器储存位置「即我们在前面新PyPyDict中提到的compact_array[]
」的id:ix
。
再依次判断其是否非空,是否来自同一个引用。
经过了上两步后,还需考虑因为hash导致的重复冲突,我们对两个对象进行相等性的比较「其中涉及了简单比较和完整比较(完整比较中返回1
为相等,0
为不等,还有一个-1
视为出错)」,根据比较的结果,如果相等就返回;如果不相等,我们对hash值做位平移,并修改我们的hash探测函数值i
,然后重新循环,继续下一次的探测。
注意:我们这里简单比较中采用了值比较
==
而不是引用相同is
,因为要考虑非小整数对象的影响。
其中关联容器entry
两种状态Unuse
以及Dummy
态,函数会分别以冲突弹窗结束搜索,或者设置为freeslot
继续探测。
关于冲突函数i
,当遇到hash冲突时,i = ((i << 2) + i + perturb + 1) & mask
,很神奇,其化简为i = (i * 5 + i) % dk_size
刚好能遍历所有元素。
#PyDictObject的插入操作
插入操作在PyDict_SetItem()
方法中:
{{- code -}}
最后调用了insertdict()
方法:
{{- code -}}
其最重要的还是基于搜索出来返回的ix
值,如果其返回的是拥有Active
的关联容器,可以直接对value_addr
赋值value
。而如果是Unuse
或者Dummy
,就需要完整的设置dict_entry
结构体了。
当空间达到一个阈值时,会调用insertion_resize()
方法,即dictresize()
方法。将空间扩大2倍并迁移数据。
{{- code -}}