[python源码分析] 8.dict,关联式容器

内部结构#

C++ 标准模板库中的 map 是一种关联式容器，内部基于 红黑树 实现。红黑树是一种 平衡 二叉树，插入、删除、查找 等关键操作的时间复杂度均为 O(logn)。

Python 虚拟机的运行依赖 dict 对象，包括 名字空间 以及 对象属性空间 等底层都由 dict 实现的。因此Python 中的 dict 对象基于查找效率更高的 hash table 实现的。

PyDictObject#

首先来看看dict的结构，PyDictObject 在头文件 Include/dictobject.h 中定义：

dict 对象 理论上应该是一种变长对象，但从 PyObject_HEAD 可以看出，它是基于 不可变长对象实现。 除了PyObject_HEAD外， PyDictObject 还包括以下几个字段：

• Py_ssize_t ma_used ，对象当前所保存的 键值对个数 ；
• uint64_t ma_version_tag ，对象当前 版本号 ，每次 修改时更新；
• PyDictKeysObject *ma_keys ，指向按键对象映射的 哈希表 结构；
• PyObject ** ma_values ， split table模式下指向由所有 值对象 组成的数组。

_dictkeysobject#

然后我们再看看 PyDictKeysObject 的源码，在Objects/dict-common.h 头文件中的 **_dictkeysobject**:

• Py_ssize_t dk_refcnt ，引用计数，跟 映射视图 的实现有关，有点类似对象引用计数；
• Py_ssize_t dk_size ，哈希表大小，必须是 \(2^n\)，这样可将模运算优化成 按位与 运算；
• dict_lookup_func dk_lookup ， 哈希查找函数 指针，可根据 dict 当前状态选用最优函数版本；
• Py_ssize_t dk_usable ，键值对数组 可用个数 ；
• Py_ssize_t dk_nentries ，键值对数组 已用个数 ；
• char dk_indices[] ，哈希表 起始地址 ，哈希表后紧接着 键值对数组 dk_entries。 char is required to avoid strict aliasing.

PyDictKeyEntry#

键值对结构体 PyDictKeyEntry 就非常直白了，除了保存键对象和值对象的指针外，缓存着键对象的哈希值：

typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;   /* 键对象的 哈希值 ，避免重复调用 __hash__ 计算哈希值*/
    PyObject *me_key;    /* 键对象指针*/
    PyObject *me_value; /* 值对象指针 This field is only meaningful for combined tables */
} PyDictKeyEntry;

#### indices and entries dk_indices 是PyDictKeyEntry的数组，它的大小是 USABLE_FRACTION(dk_size)。

#define USABLE_FRACTION(n) (((n) << 1)/3)  /*line 413 in bjects/dictobjetc.c*/

DK_ENTRIES(dk)可用于获取指向entries的指针。

PyDictKeyEntry *ep0 = DK_ENTRIES(mp->ma_keys);    /*PyDictObject *mp*/

在 Objects/dictobjetc.c中，我们可以看到关于 DK_ENTRIES 的宏定义

/*line 312 in bjects/dictobjetc.c*/

#define DK_ENTRIES(dk) \
    ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)]))

重写DK_ENTRIES宏:

// assume int8_t can fit into the indices array
size_t indices_offset = DK_SIZE(dk) * DK_IXSIZE(dk);
int8_t *pointer_to_indices = (int8_t *)(dk->dk_indices);
int8_t *pointer_to_entries = pointer_to_indices + indices_offset;
PyDictKeyEntry *entries = (PyDictKeyEntry *) pointer_to_entries;

因此，PyDictKeysObject结构就很清晰了:

容量策略#

split table和combined table#

在介绍PyDictObjet的ma_values时，我们曾提到 split table模式下才使用。那么，什么是plit table和combined table呢？ ##### 两者区别：

/*
The DictObject can be in one of two forms.

Either:
  A combined table:
    ma_values == NULL, dk_refcnt == 1.   
    Values are stored in the me_value field of the PyDictKeysObject.
Or:
  A split table:
    ma_values != NULL, dk_refcnt >= 1
    Values are stored in the ma_values array.
    Only string (unicode) keys are allowed.
    All dicts sharing same key must have same insertion order.
*/

##### 什么情况下，不同的dict对象共享相同的键但值不同 只包含 unicode键而不包含伪键（没有删除的对象），并保持 相同的插入顺序。 如果 同一类有多个实例，split table实现 可以节省大量内存。有关更多详细信息，请参阅 PEP 412

预分配机制#

dict 对象也有一种类似 list 对象的 预分配机制 。那么， dict 对象容量管理策略是怎样的呢？

由 Objects/dictobject.c 源文件中的 PyDict_MINSIZE 宏定义，我们知道 dict 内部哈希表最小长度为 8 ：

#define PyDict_MINSIZE 8

哈希表越密集，哈希冲突则越频繁，性能也就越差。因此，哈希表必须是一种 稀疏 的表结构，越稀疏则性能越好。由于 内存开销 的制约，哈希表不可能无限度稀疏，需要在时间和空间上进行权衡。实践经验表明，1/2至2/3满的哈希表，较好地平衡了 内存开销 与 搜索效率 。

为保证哈希表的稀疏程度，进而控制哈希冲突频率， Python 通过 USABLE_FRACTION 宏将哈希表内元素控制在2/3以内。USABLE_FRACTION 宏根据哈希表规模 n ，计算哈希表 可存储元素个数，也就是 键值对数组 的长度。以长度为 8 的哈希表为例，最多可以保持 5 个键值对，超出则需要扩容。USABLE_FRACTION 在indices and entries小节已经展示过了。

哈希表规模一定是 \(2^n\) (熟悉C++ unordered_map的都知道，哈希扩容时只是 近似翻倍的质数) ，也就是说 Python 采用 翻倍扩容 策略。

为什么python3.7中空dict占用了240字节？#

Python 3.7.6 (default, Jan  8 2020, 20:23:39) [MSC v.1916 64 bit (AMD64)] :: Anaconda, Inc. on win32
>>> import sys
>>> empty_dict = {}
>>> sys.getsizeof(empty_dict)
240

从以上分析，可以看出 Python 为空 dict 对象分配了一个 长度为 8 的哈希表，因而也要占用相当多的内存，主要有以下几个部分组成：

• 可收集对象链表节点，共 24 字节，在此不再展开， 垃圾回收机制 讲解中有详细介绍；
• PyDictObject 结构体，6 个字段，共 48 字节；
• PyDictKeysObject 结构体，除两个数组外有 5 个字段，共 40 字节；
• 哈希索引数组，长度为 8 ，每个槽位 1 字节，共 8 字节；
• 键值对数组，长度为 5(用USABLE_FRACTION算出来的，限制在2/3之内) ，每个 PyDictKeyEntry 结构体 24 字节，共 120 字节。

内存优化#

python2.7空dict占用272字节，而python3.7只占用240！！！

Python 2.7 (r27:82525, Jul  4 2010, 07:43:08) [MSC v.1500 64 bit (AMD64)] on win32
>>> import sys
>>> empty_dict = {}
>>> sys.getsizeof(empty_dict)
272

python3.6之前#

如果有许多大的稀疏哈希表，则会浪费大量内存。

python3.6之后#

为了以更紧凑的方式表示哈希表，可以在哈希表中 拆分 indices 和real key-value。

indices 指向一个 索引数组，索引项指向原始内容存储的位置。可以将索引视为更简单的版本哈希表，将entries视为数组，数组将每个 哈希值、key和value(PyDictKeyEntry)存储为一个元素。

每当 搜索或插入 一个元素时，根据hash value 和 indices的大小，就可以在indices数组中得到一个索引，并根据新得到的索引从entries中得到结果。

为优化内存使用， Python 将 dict 哈希表分为 哈希索引(indices) 和 键值对(entries) 两个数组来实现。例如，在64字大小的操作系统中，每个指针需要8个字节，原来需要 \(8 * 3 * 8 = 192\) ，而优化后只需 $8 * 3 * 3 + 1 * 8 = 80 $ ，节省了大约58%的内存使用。

为什么遍历字典python3.6之前是无序的，python3.6之后有序？#

因为entries 按插入顺序存储元素，所以可以 按插入项的相同顺序遍历哈希表。在旧版本的实现中，按hash key的顺序存储元素，遍历哈希表时会出现无序。这就是为什么dict在python3.6之前是无序的，而在python3.6之后是有序的

优化计算#

由于哈希表必须保持 稀疏 ，最多只有 2/3 满，这意味着要浪费至少 \(\frac{1}{3}\) 的内存空间。更雪上加霜的是，一个键值对条目 PyDictKeyEntry 大小达 24 字节，试想一个规模为 65536 的哈希表，将浪费高达 512KB 的内存空间：

\[65536 * \frac{1}{3} * 24 = 524288\]

为了尽量节省内存， Python 将 键值对数组压缩到原来的 \(\frac{2}{3}\)，只负责存储，索引由另一个数组负责。由于索引数组只需要保存 键值对数组 的下标，而整数占用的内存空间只是若干字节，因此可以 节约大量内存。

索引数组每个元素的大小#

索引数组 可根据哈希表规模，选择 尽量小的整数类型。对于规模 不超过 256 的哈希表，选择 8 位整数即可；对于长度 不超过 65536 的哈希表， 16 位整数足矣；以此类推。

#define DK_SIZE(dk) ((dk)->dk_size)
#if SIZEOF_VOID_P > 4
#define DK_IXSIZE(dk)                          \
    (DK_SIZE(dk) <= 0xff ?                     \
        1 : DK_SIZE(dk) <= 0xffff ?            \
            2 : DK_SIZE(dk) <= 0xffffffff ?    \
                4 : sizeof(int64_t))
#else
#define DK_IXSIZE(dk)                          \
    (DK_SIZE(dk) <= 0xff ?                     \
        1 : DK_SIZE(dk) <= 0xffff ?            \
            2 : sizeof(int32_t))
#endif

哈希表规模	条目表规模	旧方案	新方案	节约内存
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

free list#

#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
static PyDictObject *free_list[PyDict_MAXFREELIST];

CPython还使用 free list 重用删除的哈希表，避免内存碎片，提高性能

每个进程全局变量都有个 free list

if we create a new dict object, the memory request is delegate to CPython's memory management system

d = dict()

del a

如果free list未满, dict类型的析构函数将当前dict存储到free list。

下次创建新的dict对象时，将检查 free list， 如果有 可用的对象则从 free list分配；如果没有，则从 CPython的内存管理系统分配。

d = dict()

哈希#

可哈希 ( hashable )对象#

根据哈希表性质， key对象 必须满足以下两个条件，否则哈希表便不能正常工作：

• 哈希值在对象整个生命周期内 不能改变； ( list 、dict 等 可变对象均不能作为哈希key)
• 可比较，且比较相等的对象哈希值必须相同； 满足这两个条件的对象便是 可哈希 ( hashable )对象，只有 可哈希对象才可作为哈希表的键。因此，诸如 dict 、set等底层由哈希表实现的容器对象，其键对象必须是可哈希对象。

而用户自定义的对象默认便是可哈希对象，对象哈希值由对象地址计算而来，且任意两个不同对象均不相等：

>>> class A:
...     pass
>>>
>>> a = A()
>>> b = A()
>>>
>>> hash(a), hash(b)
(2852108, 2852116)
>>> a == b
False

#### 哈希函数 哈希值 计算作为对象行为中的一种，秘密也隐藏在类型对象中—— tp_hash 函数指针。而内置函数 hash 则依赖类型对象中的 tp_hash 函数，完成哈希值计算并返回。

以 str 对象为例，其哈希函数位于 Objects/unicodeobject.c 源文件，unicode_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 */
};

对于用户自定义的对象，可以实现 hash 魔术方法，重写默认哈希值计算方法。举个例子，假设标签类 Tag 的实例对象由 value 字段唯一标识：

class Tag:
    def __init__(self, value, title):
        self.value = value
        self.title = title

    def __hash__(self):
     """value 字段唯一标识,根据 value 字段实现 哈希函数"""
        return hash(self.value)

    def __eq__(self, other):
      """根据 value 字段实现 相等性 判断"""
        return self.value == other.value

哈希值 使用频率 较高，而且在对象生命周期内均不变。因此，可以在对象内部 对哈希值进行缓存，避免重复计算。以 str 对象为例，内部结构中的 hash 字段便是用于保存哈希值。

哈希冲突#

解决哈希冲突的常用方法有两种：

• 分离链接法 ( separate chaining ) ；
• 开放地址法 ( open addressing )；

分离链接法#

开放地址法#

• 线性探测 ，顾名思义， \(d_i\)是一个线性函数，例如 \(d_i = 2 * i\)
• 平方探测 ，顾名思义， \(d_i\)是一个平方函数，例如 \(d_i = i^2\) 线性探测 和 平方探测 很简单，平方探测似乎更胜一筹。如果哈希表存在局部热点，探测很难快速跳过热点区域，而 平方探测 则好很多。然而，这两种方法都不够好——因为固定的探测序列加大了冲突的概率。

Python 探测方法在 lookdict 函数中实现，位于 Objects/dictobject.c 源文件内。关键代码如下：

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 解释器启动一个交互式终端，并计算字符串 fasion 的哈希值：

>>> import os
>>> os.getpid()
2878
>>> hash('fasion')
-1023772170

我们再次执行 Python 2 解释器启动另一个交互式终端，发现字符串 fasion 的哈希值保存不变：

>>> import os
>>> os.getpid()
2915
>>> hash('fasion')
-1023772170

如果一些别有用心的人 构造出大量哈希值相同的 key ，并提交给服务器，会发生什么事情呢？例如，向一台 Python 2 Web 服务器 post 一个 json 数据，数据包含大量的 key ，所有 key 的哈希值相同。这意味着 哈希表将频繁发生哈希冲突，性能由 \(O(1)\) 急剧下降为 \(O(N)\)，被活生生打垮！这就是 哈希攻击 。

问题很严重，好在应对方法却很简单:为对象加把 盐(salt)。具体做法如下： 1. Python 解释器进程启动后，产生一个 随机数作为 盐 ； 2. 哈希函数同时参考 对象本身 以及 随机数 计算哈希值； 这样一来，攻击者无法获悉解释器内部的随机数，也就无法构造出哈希值相同的对象了！Python 自 3.3 以后，哈希函数均采用 加盐模式，杜绝了 哈希攻击 的可能性。Python 哈希算法在 Python/pyhash.c 源文件中实现，有兴趣的童鞋可以学习一下，这里就不再展开了。

执行 Python 3.7 解释器，启动一个交互式终端，并计算字符串 fasion 的哈希值：

>>> hash('fasion')
6950491525924312838

再次执行 Python 3.7 解释器，启动另一个交互式终端，发现字符串 fasion 的哈希值已经变了：

>>> hash('fasion')
-7162025883309105262

## reference 1. dict 2. Python 源码深度剖析/13 dict 对象，高效的关联式容器 2. Python 源码深度剖析/14 dict 哈希表高级知识精讲