# dict
# 内部结构
# 概述
Python 虚拟机的运行重度依赖
dict对象，包括 名字空间 以及 对象属性空间 等概念底层都是由 dict 对象实现的。因此， Python 对 dict 对象的效率要求极为苛刻。
dict最小长度为8并且dict拓展时是直接长度乘2，因此哈希表的大小永远是 2 的幂次方。也因此，对于任何一个键的哈希值，只需要使用哈希表的长度对其取模即可得到该键在哈希表中的索引位置。
dict对象真正的实现在PyDictKeysObject中，其内部维护两个关键数组，一个是键值对数组dk_entries，一个是哈希索引数组dk_indices。dict所维护的键值对，按照先来后到的顺序保存于键值对数组中，而哈希索引数组对应槽位保存着键值对在数组中的位置。
因此当我们向空dict对象插入新键值对
('jim',70)时，Python会执行以下步骤：将键值对保存于
dk_entries数组末尾，即下标为 0 的位置；计算键对象
‘jim’ 的哈希值并取右3 位，得到该键在哈希索引数组中的下标 5 ；默认长度为8
将键值对在数组中的下标 0 ，保存于哈希索引数组中编号为 5 的槽位中。
查找操作步骤为：
- 计算键对象
‘jim’ 的哈希值并取右3位，得到该键在哈希索引数组中的下标 5 ； - 找到哈希索引数组下标为 5 的槽位，取出其中保存的下标 0 ；
- 找到键值对数组第 0 个位置，并取出 值对象 ；
- 计算键对象
# PyDictObject
typedef struct {
PyObject_HEAD
/* Number of items in the dictionary */
Py_ssize_t ma_used; // 对象当前所保存的键值对个数
/* Dictionary version: globally unique, value change each time
the dictionary is modified */
uint64_t ma_version_tag; // 对象当前版本号，每次修改时更新
PyDictKeysObject *ma_keys; // 指向键对象映射的哈希表结构
/* If ma_values is NULL, the table is "combined": keys and values
are stored in ma_keys.
If ma_values is not NULL, the table is splitted:
keys are stored in ma_keys and values are stored in ma_values */
PyObject **ma_values; // 分离模式下指向由所有值对象组成的数组
} PyDictObject;
# PyDictKeysObject
struct _dictkeysobject {
Py_ssize_t dk_refcnt; //引用计数，与映射视图的实现有关
/* Size of the hash table (dk_indices). It must be a power of 2. */
Py_ssize_t dk_size; // 哈希表大小，必须是2^n-可以将模运算优化为按位与运算
/* Function to lookup in the hash table (dk_indices):
- 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 <dummy> value.
- lookdict_split(): Version of lookdict() for split tables. */
dict_lookup_func dk_lookup; // 哈希查找函数指针 根据dict当前状态选用最优函数版本
/* Number of usable entries in dk_entries. */
Py_ssize_t dk_usable; // 键值对数组可用个数
/* Number of used entries in dk_entries. */
Py_ssize_t dk_nentries; // 键值对数组已用个数
/* Actual hash table of dk_size entries. It holds indices in dk_entries,
or DKIX_EMPTY(-1) or DKIX_DUMMY(-2).
Indices must be: 0 <= indice < USABLE_FRACTION(dk_size).
The size in bytes of an indice depends on dk_size:
- 1 byte if dk_size <= 0xff (char*)
- 2 bytes if dk_size <= 0xffff (int16_t*)
- 4 bytes if dk_size <= 0xffffffff (int32_t*)
- 8 bytes otherwise (int64_t*)
Dynamically sized, SIZEOF_VOID_P is minimum. */
// 哈希表起始地址
char dk_indices[]; /* char is required to avoid strict aliasing. */
// 后面紧跟着键值对数组 dk_entries
/* "PyDictKeyEntry dk_entries[dk_usable];" array follows:
see the DK_ENTRIES() macro */
};
# PyDictKeyEntry
typedef struct {
/* Cached hash code of me_key. */
Py_hash_t me_hash; // 键的hash值，避免重复计算
PyObject *me_key; // 键对象指针
/* This field is only meaningful for combined tables */
PyObject *me_value; // 值对象指针
} PyDictKeyEntry;
# dict行为
# 预分配机制
dict内部哈希表最小长度为8，因此向空dict插入元素实际上并不会使得dict占用的内存空间变大。
哈希表必须是一种稀疏的表结构，根据实践经验，一个
1/2到2/3 满的哈希表，性能较为理想，较好地平衡了 内存开销 与 搜索效率 ；因此Python通过USABLE_FRACTION宏将哈希表内元素控制在2/3 以内。以长度为 8 的哈希表为例，最多可以保持 5 个键值对，超出则需要扩容。#define USABLE_FRACTION(n) (((n) << 1)/3)哈希表规模一定是2^n，即Python对于dict采用翻倍扩容的策略。
对于一个空dict占用的内存空间分析：
>>> sys.getsizeof({}) 240- 可收集对象链表节点，共 24 字节；
- PyDictObject 结构体，6 个字段，共 48 字节；
- PyDictKeysObject 结构体，除两个数组外有 5 个字段，共 40 字节；
- 哈希索引数组，长度为 8 ，每个槽位 1 字节，共 8 字节；
- 键值对数组，长度为 5 ，每个 PyDictKeyEntry 结构体 24 字节，共 120 字节。
# 哈希值
Python内置函数hash返回对象哈希值，哈希表依赖哈希值索引元素。
可hash对象
根据哈希表性质，键对象必须满足如下两个条件：
第一点：哈希值在对象整个声明周期内不可改变
第二点：可比较、比较相等的对象哈希值必须相同。
因此内建对象中的不可变对象都是可哈希对象（tuple可哈希），而list、dict等可变对象则不可哈希。
>>> dic = {(1,2,3):"tuple"} >>> print(dic) {(1, 2, 3): 'tuple'}用户自定义对象默认时是哈希对象-哈希值由对象地址计算而来。可以覆写
__hash__魔术方法来实现自定义的哈希值计算，这个方法存储在类型对象的tp_hash函数指针中。PyTypeObject PyUnicode_Type = { PyVarObject_HEAD_INIT(&PyType_Type, 0) "str", /* tp_name */ sizeof(PyUnicodeObject), /* tp_size */ // ... (hashfunc) unicode_hash, /* tp_hash*/ // ... unicode_new, /* tp_new */ PyObject_Del, /* tp_free */ };
哈希值使用频率较高，并且在对象生命周期内保持不变，因此可以在对象内部对哈希值进行缓存，避免重复计算-例如str对象的
hash字段。/* ASCII-only strings created through PyUnicode_New use the PyASCIIObject structure. state.ascii and state.compact are set, and the data immediately follow the structure. utf8_length and wstr_length can be found in the length field; the utf8 pointer is equal to the data pointer. */ typedef struct { PyObject_HEAD Py_ssize_t length; /* Number of code points in the string */ Py_hash_t hash; /* Hash value; -1 if not set */ struct { unsigned int interned:2; unsigned int kind:3; unsigned int compact:1; unsigned int ascii:1; unsigned int ready:1; unsigned int :24; } state; wchar_t *wstr; /* wchar_t representation (null-terminated) */ } PyASCIIObject;
# 哈希冲突
由于哈希表本质是将一个无限集合映射到有限集合的函数，因此发生哈希冲突可以说是必然的事。
解决哈希冲突的两种常用方法：
分离链接法
- 分离链接法 为每个哈希槽维护一个链表，所有哈希到同一槽位的键保存到对应的链表中
开放地址法
Python 采用 开放地址法 ( open addressing )，将数据直接保存于哈希槽位中，如果槽位已被占用，则按照算法尝试另一个。
如上图，key3 哈希到槽位 3 ，但已被 key1 占用了；接着尝试槽位 5 并成功保存。一般而言，第 i次尝试在首槽位基础上加上一定的偏移量di。因此，探测方式因函数 di 而异。常见的方法有 线性探测 ( linear probing )以及 平方探测 ( quadratic probing )。
线性探测
- 顾名思义， di 是一个线性函数，例如di=2∗i
- 如果哈希表存在局部热点，线性探测很难快速跳过热点区域
平方探测
- 顾名思义， di是一个平方函数，例如 di=i^2
- 平方探测解决了线性探测无法快速走出热点区域的问题
貌似平方探测相比线性探测会优秀一些，但实际上两种这样固定的探测序列都会加大冲突的概率，因此Python对此进行了优化，探测函数参考对象哈希值，生成不同的探测序列，进一步降低哈希冲突的可能性。Python键探测方法在
lookdit函数中实现：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; for (;;) { Py_ssize_t ix = dk_get_index(dk, i); // 省略键比较部分代码 // 计算下个槽位 // 由于参考了对象哈希值，探测序列因哈希值而异 perturb >>= PERTURB_SHIFT; i = (i*5 + perturb + 1) & mask; } Py_UNREACHABLE(); }
# 哈希攻击
- Python 在 3.3 以前， 哈希算法 只根据对象本身计算哈希值。因此，只要 Python 解释器相同，对象哈希值也肯定相同，这就导致了受到哈希攻击的可能性。例如向一台 Python 2 Web 服务器 post 一个 json 数据，数据包含大量的 key ，所有 key 的哈希值相同。这意味着哈希表将频繁发生哈希冲突，性能由O(1) 急剧下降为 O(N)，被活生生打垮！
- 但Python3.3之后哈希算法将同时参考对象本身以及Python解释器运行时生成的一个随机数-salt，这样一来，攻击者无法获悉解释器内部的随机数，也就杜绝了 哈希攻击 的可能性。
# 删除操作
例如场景：
key1 最先插入，使用了哈希槽位 5 以及存储单元 0 ；紧接着插入 key2 ，使用了哈希槽位 1 以及存储单元 1 ；最后插入 key3 时，由于哈希槽位被 key2 占用，改用槽位 6 。
如果删除key2时直接将哈希表位置置空则会影响key3的查询，因此在删除时需要位对应的哈希槽设置一个特殊的标识DUMMY，避免中断哈希探测链。
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2) /* Used internally */
#define DKIX_ERROR (-3)
对于键值对中被删除的单元则不会做容量调整操作，而是直接不管，之后新插入的时候依旧是插入在键值对数组的最后-造成了一些空间浪费但无伤大雅。
分离链接法查找效率更高，但空间开销较大（链表指针）；而开放地址法比较节约内存，但哈希冲突会更频繁。Python选择后者，然后哈希表只写不删，满了之后就重新分配哈希表，保证数据不会太满，冲突被控制在一定范围内。
当存储单元已经用完时则进行以此容量调整，重新分配哈希表并将所有元素搬过去。
# 优化
# 分离模式
在Python早期，哈希表并没有分成两个数组来实现，而是由一个键值对数组实现，同时这个数组也承担哈希索引的角色。
但是由于哈希表必须保证稀疏的特性（至少浪费
1/3的空间），而一个PyDictKeyEntry 大小达 24 字节，对此会造成大量的内存空间浪费。因此最后分成了索引数组和键值对数组两个数组的实现方式。
- 索引数组可以根据哈希表规模选择尽可能小的整数类型，例如规模小于256，选择8位整数即可。
哈希表规模 | 条目表规模 | 旧方案 | 新方案 | 节约内存 |
|---|---|---|---|---|
| 8 | 8 * 2 / 3 = 5 | 24 * 8 = 192 | 1 * 8 + 24 * 5 = 128 | 64 |
| 256 | 256 * 2 / 3 = 170 | 24 * 256 = 6144 | 1 * 256 + 24 * 170 = 4336 | 1808 |
| 65536 | 65536 * 2 / 3 = 43690 | 24 * 65536 = 1572864 | 2 * 65536 + 24 * 43690 = 1179632 | 393232 |
# 保持插入序
而且引入第二层数组之后，字典变得有序了。字典内键值对的顺序变得可依赖
# 删除key不复用空间
# QA
# 为什么使用PyObject_HEAD而不是PyObject_VAR_HEAD