前言

现代的编程语言都在语言级或标准库中提供某种关联式的容器，容器中的元素通常是以(key,value)的形式存在的。

关联式容器总会极大地关注键的搜索效率，其实现都会基于良好的数据结构，如C++中的map的实现基于红黑树，搜索时间复杂度为O(logN)。

Python中的关联容器PyDictObject即dict是基于散列表实现的。Dict对搜索的效率要求很高，因为Python本身的实现中dict被大量的使用，如Python字节码的运行环境，其中存放变量名和变量值，通过查找变量名获得变量值。因此dict的实现没有采用平衡二叉树，而是采用了散列表，最优情况下散列表的搜索复杂度为O(1)。

散列表

Python在处理哈希冲突的时候采用开放地址法，在删除散列表中的元素的时候，不能进行真正的删除，因为会导致冲突探测链的探测过早的结束，所以Python采用一种伪删除的方式。

PyDictObject

关联容器的entry

关联容器中的一个(key,value)元素称为一个entry或slot。Python中，一个entry定义如下：

1
2
3
4
5
6
7
8
9
10
11
// dictobject.h
typedef struct {
    /* Cached hash code of me_key.  Note that hash codes are C longs.
     * We have to use Py_ssize_t instead because dict_popitem() abuses
     * me_hash to hold a search finger.
     */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

PyDictObject存放的是PyObject*，可以存放任何Python对象。me_hash域存储的是me_key的散列值。

PyDictObject中entry可以在3种状态间转换：

  • Unused态：该entry从现在到之前都没有存储过(key,value)对。
  • Active态：存储了一个(key,value)对entry便传化为Active态。
  • Dummy态 ： entry中的(key,value)对被“伪删除”后，进入Dummy态。
entry三种状态


关联容器的实现

关联容器PyDictObject是一大堆entry的集合，集合结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// dictobject.j
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;  /* # Active + # Dummy */
    Py_ssize_t ma_used;  /* # Active */
    /* The table contains ma_mask + 1 slots, and that's a power of 2.
     * We store the mask instead of the size because the mask is more
     * frequently needed.
     */
    Py_ssize_t ma_mask;
    /* ma_table points to ma_smalltable for small tables, else to
     * additional malloc'ed memory.  ma_table is never NULL!  This rule
     * saves repeated runtime null-tests in the workhorse getitem and
     * setitem calls.
     */
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

当PyDictObject中的entry数量超过8个时，Python会认为这是一个大dict了，将会申请额外内存空间，并将ma_table指向这块空间。

entry三种状态


PyDictObject中元素搜索

PyDictObject提供两种搜索策略，lookdict和lookdict_string，Python默认搜索方式为lookdict_string。

Python获取冲突链上的第一个entry的过程采用，将hash值（我认为是元素序号）与entry的数量做一个与操作，结果自然会落在entry的数量之下。

freeslot正是用来指向探测序列中第一个处于Dummy态的entry，如果搜索失败，freeslot会提供一个处于Dummy态的entry。

根据hash值获得的冲突探测链上第一个entry与待查找的元素的比较：

  1. 根据hash值获得entry的索引，是冲突探测链上的第一个entry的索引。
  2. 在两种情况下搜索结束：
    • entry处于Unused态，表明冲突探测链搜索完成，搜索失败；
    • ep->me_key == key，表明entry的key与待搜索的key匹配，搜索成功。
  3. 若当前entry处于Dummy态，这是freeslot。
  4. 检查Active态entry中的key与待查找的key是否“值相同”，若成立，搜索成功。

遍历探测链时发生的lookdict所进行的操作：

  1. 根据Python所采用的探测函数，获得探测链中的下一个待检查的entry。
  2. 检查到一个Unused态entry，表明搜索失败，这时有两种结果：
    • 如果freeslot不为空，则返回freeslot所指entry。
    • 如果freeslot为空，则返回该Unused态entry。
  3. 检查entry中的key与带查找的key是否符合“引用相同”规则。
  4. 检查entry中的key与待查找的key是否符合“值相同”规则。
  5. 遍历过程中，如果发现Dummy态entry，且freeslot未设置，则设置freeslot。

PyDictObject插入

搜索成功，返回处于Active的entry，直接替换me_value。
搜索失败，返回Unused或Dummy的entry，完整设置me_key、me_hash和me_value。

如果table的装载率大于2/3时，后续的插入动作遭遇到冲突的可能性会非常大，在装载率大于或等于2/3时需要改变table的大小。

PyDictObject的删除

先计算hash值，搜索相应的entry，删除entry维护的元素，将entry从Active态变换为Dummy态，调整PyDictObject对象中维护table使用情况的变量。