[TOC]

1 python 27 字典结构

1. 字典通过哈希表实现

  • 默认版本: Python2.7.x
  • cpython 2.7 源码 dictobject.c dictobject.h
  • 以下代码对源码有删减, 只保留主要逻辑

2. 字典中基本存储单元: PyDictEntry

  • 哈希表初始大小 PyDict_MINSIZE 为 8

    • 1
2
3
4
5
6
7
8

      #define PyDict_MINSIZE 8
/* PyDict_MINSIZE is the starting size for any new dict.
 * 8 allows dicts with no more than 5 active entries; experiments suggested
 * this suffices for the majority of dicts (consisting mostly of usually-small
 * dicts created to pass keyword arguments).
 * Making this 8, rather than 4 reduces the number of resizes for most
 * dictionaries, without any significant extra memory use.
 */

  • 字典中存储键值对的单元叫做 PyDictEntry* , 下文简称 entry (也称 slot), 字典通过 idx 来访问 entry(idx: 可以理解为数组的下标, 由键, 字典长度 和 hash 算法生成)

  • entry 有三种状态: Unused/Active/Dummy (Dummy 是删除的结果)

  • 字典结构 PyDictObject

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill; // ma_fill 是使用了的 entry 加 dummy entry 的数量和
    Py_ssize_t ma_used; // ma_used 是被占用了(即活跃的)的 entry 数量
    Py_ssize_t ma_mask; // 掩码, 等于所有 entry 数量 n -1, n = 2 ^ n
    PyDictEntry *ma_table; // 指向 PyDictEntry(存键值对)的数组
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

  • PyDictEntry 结构:

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

    typedef struct {
    Py_ssize_t me_hash;
    PyObject *me_key; 
    PyObject *me_value
} PyDictEntry;
  
// 存储索引等于 哈希值 & 掩码, 例如 n = 8, 掩码为 7(111), 相当于 取hash 值末尾三位为索引
>>> d["ftp"] = 21
>>> b = bits(hash("ftp"))
1101001001111111111001001010100001
>>> b[-3:]
001

  • PyDictEntry 大体类似于:

    Idx Hash Key Value
    000
    001 …1010001 “ftp” 21
    010
    011
    100
    101
    110
    111

3. 插入逻辑

  1. 最好 时间O(1) 空间O(1), 最坏 时间O(n) 空间 O(n)

    • 普通情况时间复杂接近 O(1)

  2. 当添加一个新键值对时, 调用栈

    1. PyDict_SetItem
    2. dict_set_item_by_hash_or_entry
    3. insertdict
    4. insertdict_by_entry
    5. dictresize

  3. 具体实现

    1. 计算哈希(如果这个键的哈希值已经被缓存了则用缓存值)

      1
2
3
4
5
6
7
8

      PyDict_SetItem -> dict_set_item_by_hash_or_entry // PyDict_SetItem: 计算hash 传入后者
    dict_set_item_by_hash_or_entry(register PyObject *op, PyObject *key, long hash, PyDictEntry *ep, PyObject *value);
      // if 哈希表中没有新增 entry key, 先
        insertdict(mp, key, hash, value);
      // else 相当于更新键值对, 已存在 entry, 更新 value 即可
      insertdict_by_entry(mp, key, hash, ep, value) 
        // 检测已使用大小, 重新调整数组大小
        dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

    2. 新增 entry key

      1. insertdict 先找到 entry, 再调用 insertdict_by_entry

      2. 1
2
3
4
5
6

         static int
 insertdict(register PyDictObject *mp, PyObject *key, long hash, PyObject *value)
 {
     ep = mp->ma_lookup(mp, key, hash); // try get entry
     return insertdict_by_entry(mp, key, hash, ep, value); // 更新 entry
 }

      3. mp->ma_lookup(mp, key, hash); 即调用 lookdict_string, lookdict

    3. 检测是否需要扩容

      1. 检测

        1
2
3
4
5

        // insertdict_by_entry 插入 entry 之后, 如果新增 entry 和 dummy entry 的总量超过了数组大小(ma_mask+1))的 2/3, 则重新调整字典的大小.
if (!(mp->ma_used > n_used   &&   mp->ma_fill*3 >= (mp->ma_mask+1)*2))
  return 0;
// 扩容系数 GROWTH_RATE python2.7 为 4, 如果数组使用大小超过 50K 则扩容系数为 2
return dictresize(mp, (mp->ma_used > 50000 ? 2 : 4) * mp->ma_used);

      2. 调用 dictresize

        1. 做了什么: 扩容

        2. 怎么做的:

          • 计算新数组大小

          • 新建新哈希数组, 赋给 PyDictObject * mp

          • 将所有旧值拷贝到新数组中

           1
 2
 3
 4
 5
 6
 7
 8
 9
10

          static int
  dictresize(PyDictObject *mp, Py_ssize_t minused)
{
  /* Find the smallest table size > minused. 先计算出始数组最小的容量大小*/
  for (newsize = PyDict_MINSIZE;
       newsize <= minused && newsize > 0;
       newsize <<= 1)
    ;
  // 循环 oldtable, 调用 insertdict_clean(mp, ep->me_key, (long)ep->me_hash, ep->me_value); 插入
}

  4. lookdict_string 及 lookdict 实现细节 - 解决哈希冲突

    1. 如果是非字符串调用 lookdict(mp, key, hash)

      • 区别: lookdict_string
        1. never raise an exception
        2. never return NULL

    2. key 为字符串的情况很常见, 所以单独实现 lookdict_string

      •  1
 2
 3
 4
 5
 6
 7
 8
 9
10

           static PyDictEntry *
 lookdict_string(PyDictObject *mp, PyObject *key, register long hash)
 {
     i = hash & mask;	// 初始索引 PERTURB_SHIFT 干扰右移因子 为 5, 原因在下面
     for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {
         i = (i << 2) + i + perturb + 1; 
         ep = &ep0[i & mask];				// 重新计算索引
       // 找到一个key为空, 或者已存在的相同 entry(key, hash, value值都相同, 且不为 dummy)
     }    
 }

  5. 哈希冲突理论 - 索引(idx)出现哈希冲突, 使用开放定址法解决

    • 开放地址法中的简易模式线性探测法
      • 如果地址 i 已经被使用, 则尝试 i + 1
      • 弊端:
        • 字典中, 使用连续关键字作为 key 较为常见
        • 存储的位置一般为连续存储
        • 所以使用 i + 1 这种顺序查找空位往往会全部扫描才能找到, 效率低下
    • Python 使用开放地址法 中的 二次探测序列（quadratic probing sequence）解决哈希冲突
    • 为什么没有使用拉链法
      • 需要申请内存, 效率慢

  6. 二次探测序列

    • 1
2
3
4
5
6
7

      i = hash & mask; // 起始存储单元
perturb = hash;  // 初始干扰值
while (存储单元非空) && (单元内值不等于关键字值) {
    perturb >>= 5; // 5 为 PERTURB_SHIFT
   i = (i*5 + perturb + 1) & mask;
   // use j % 2**i as the next table index;
}

    • PERTURB_SHIFT 每次偏移量, 为什么最终为 5 个 bit?

      • You want it small so that the high bits of the hash code continue to affect the probe sequence across iterations; but you want it large so that in really bad cases the high-order hash bits have an effect on early iterations.

      • 右移数字小可以 在探测序列查找的迭代过程中, 让哈希值中高位的值一直持续影响探测

      • 右移数字大可以 在探测序列查找的迭代过程中, 让哈希值中高位的值尽早影响探测

      • 最后权衡选择5最好

    • perturb 最终为 0 的情况:

      • 上式即为 j = 5 * j + 1
      • idx = j % (range(2^i))
      • 可以确保总会找到一个空位

4. 字典长度调整 dictresize

  • 1

    static int dictresize(PyDictObject *mp, Py_ssize_t minused)

  • 当 entry 使用率超过 2/3, dictresize()函数将会被调用, 数组长度调整后的长度不小于活动槽数量的 4 倍, 即 minused = 4*ma_used

  • 删除键值对后, 即使最终活动槽的数量远小于总的数量也不会触发 dictresize(), 但是当删除较多键后又增加较少键, 会调用 dictresize(), 最终缩小调整数组大小,

5. 删除逻辑

  • When an item is removed, the corresponding index is replaced by DKIX_DUMMY DKIX_DUMMY with a value of -2 and the entry in the entry array replaced by NULL, when inserting is performed the new values are appended to the entries array, Haven"t been able to discern yet, but pretty sure when the indices fills up beyond the 2/3 threshold resizing is performed. This can lead to shrinking instead of growing if many DUMMY entries exist. – Jim Fasarakis Hilliard.

  • 删除时, 首先计算键的哈希值, 然后调用搜索函数返回到该条目, 将这个 entry 标记为哑槽(dummy entry)

  • 不直接删除而是标记为 dummy 状态的原因:

    • 为了保证探测链的连续性.
    • 使用开放地址法如果遇到哈希冲突会构成探测链, 如果删除的结点位于探测链中, 则之后结点会找不到

6. 字典原理通过哈希表实现而造成的特性

  1. Python 2.7 字典的实现原理是哈希表解释

  2. 为什么不能依赖 dict 的顺序

  3. 新加一个键值对会 dict.keys() 顺序会改变

  4. 为什么 dict 的 key 不能使用可变对象

  5. 如果 class 要实现 __hash__ 方法, 需要

    1. 散列越分散越好, 尽量避免相同值
    2. 同一个 instance 拥有相同的 hash 值
    3. 必须实现 __eq__ 方法
    4. __hash__ 与 __eq__ 要快, 因为使用频繁

  6. 相同的值应该有相同的 哈希值

    1. 比如 数字 9 int, float 等

2 Python36 CPython字典新特性: 有序且性能更好

  1. python3.6 的新结构
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# 旧字典
typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;
    Py_ssize_t ma_used;
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

# 新字典:
layout:
+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
| dk_indices    |
|               |
+---------------+
| dk_entries    |
|               |
+---------------+
  1. 对比

For example, the dictionary:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

d = {"timmy": "red", "barry": "green", "guido": "blue"}
// is currently stored as:
entries = [["--", "--", "--"],
         [-8522787127447073495, "barry", "green"],
         ["--", "--", "--"],
         ["--", "--", "--"],
         ["--", "--", "--"],
         [-9092791511155847987, "timmy", "red"],
         ["--", "--", "--"],
         [-6480567542315338377, "guido", "blue"]]   

// Instead, the data should be organized as follows:
indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, "timmy", "red"],
        [-8522787127447073495, "barry", "green"],
           [-6480567542315338377, "guido", "blue"]] 
     
// old: 3 * 8 * 8byte : 5 * 3 * 8byte = 总共占用 192 byte 空闲 120byte
// new: 8byte + 3 * 3 * 8byte : 5byte = 总共占用 80 byte 空闲 5byte

  1. 实现原理 - 使用了两个 array 数组

    1. 第一个数组保存索引及顺序
      • dk_indices, 是一个哈希表, 保存了entrys中的 index (即存储了 entry 对应的位置), or DKIX_EMPTY(-1)or DKIX_DUMMY(-2). dk_indices 的大小就是 dk_size
    2. 第二个数组与旧 dict 一样存储 entry, 不过只保留有效的, 没有空位
      • dk_entries is array of PyDictKeyEntry. 存储实际数据

  2. 变化:

    1. 节省空间复杂度:

      • 旧字典使用稀疏数组 sparse array, 占用的无效空间最少为 1/3(为了保证探测序列能够以足够快的速度找到空闲槽), 新字典使用密集数组, 省空间.

    2. 第二个优点:

      • Currently, keys(), values, and items() loop over the sparse table, skipping-over free slots in the hash table. Now, keys/values/items can loop directly over the dense table, using fewer memoryaccesses…dense table

      • 密集数组, 相对稀疏数组而言, 不存在空隙), 简而言之, 密集数组占地方小, 循环迭代快.

    3. 第三个优点: ...resizing is faster and touches fewer pieces of memory..., 调整字典大小需要的内存更少. 因为在调整大小过程中, 旧字典的每一个 hash/key/value 都要移动或者复制, 新字典只需更新 indices 就行了, 除了偶尔由于删除需要填补而移动之外, hash/key/value 位置是固定的.

3 Python dict PEP

  • todo

4 拓展: 哈希表(hash tables) 二次探测序列（quadratic probing sequence）

«算法第四版小红书», 第三章查找第四节散列表

  • 散列表查找算法分两步:
    • 将键转化为数组的索引
    • 处理冲突, 使用拉链法和开放地址(其中最简单的方法叫线性探测法)
  1. 散列函数
    • 每一种类型的键需要对应不同的散列函数
    • 正整数: 除留余数法, 选择大小为素数M的数组, 对于任意正整数, 计算除以 M 的余数.
    • 浮点数: Java 采用的方法是将键表示为二进制, 再使用除留余数法
    • 字符串: 将字符串转为较大的整数再计算
    • 组合键: 类似字符串
    • 软缓存, 缓存散列值
  2. 解决碰撞冲突方法
    1. 拉链法
      • 定义: 将大小为 M 的数组中的每一个元素指向一条链表, 链表中的每个结点都存储了散列值为该元素的索引的键值对
      • 用 M 条链表保存 N 个键, 链表平均长度为 N/M
    2. 开放地址法中的线性探测法
      • 开放地址法: 用大小为 M 的数组保存 N 个键值对, 其中 M>N, 依靠空位解决碰撞冲突
      • 线性探测法: 当碰撞发生时, 继续查找下一个位置, 直到为空
      • 将散列表中的空元素作为查找结束的标志

流畅的Python字典扩展:

  1. 代码之美18章-Python字典类:如何打造全能战士 CPython dictobject.c源文件
  2. PEP274
  3. Brandon Rhodes 的讲座"The Mighty Dictionary”

参考:

  1. 深入Python字典的内部实现(英文原文) 其译文
  2. python之禅
  3. «算法第四版小红书»
  4. [Python-Dev] More compact dictionaries with faster iteration
  5. Brandon Rhodes The Dictionary Even Mightier PyCon 2017