本系列作为本人@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 != NULLandme_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 -}}