dict部分源码解析(cpython)

2021-06-18

2021-06-17

本文字数: 2.4k 阅读时长: 10 分钟

阅读次数次

python中大部分的运行机制当中都采用了dict来进行数据的管理，所以为了最高效的查询性能，
dict底层选择了基于哈希表实现。其中在python3.6之前，dict的实现里将数据存在了hash表里，
所以之前的dict是无序且十分消耗内存的，而在python3.6以后，官方对dict进行了很大地改进
（主要是将数据和hash部分分离），包括从无序变为有序，在一定程度上减少了内存的消耗，以及
部分操作性能的提升。
链接1
链接2

3.6版本前和3.6后对比

3.6前

用一个数组存储combined

1 2	\[(hash, key, value), (hash, key, value), (hash, key, value)] 通过计算hash把数据放到数组某个位置

dict状态

1.Unused：此时key为null，即还未使用当前位置，此时索引值被设为-1
2.Active：如果当前位置设置了键值对，那么就会进入该状态，表示正在使用中，此时索引值就是所在位置的索引
3.Dummy：当被使用的key删除时，将会进入该状态，用于避免探测链断开而导致索引出错的问题

3.6后

用两个数组存储，一个为entries存储数据的顺序，另一个为原来的

# entries
[3, 5, 1, 4, 2]

[(hash, key, value), (hash, key, value), (hash, key, value), (hash, key, value), (hash, key, value)]

dict状态

1.Unused：此时key为null，即还未使用当前位置，此时索引值被设为-1
2.Active：如果当前位置设置了键值对，那么就会进入该状态，表示正在使用中，此时索引值就是所在位置的索引
3.Pending：同样是删除键值对以后进入的状态，此时索引不变，但是对应索引存储的value将会被删除，从而等待新的对应索引的key插入

3.6后源码

PyDictObject

typedef struct {
    // 通用对象头
    PyObject_HEAD
    // 键值对的数量
    Py_ssize_t ma_used;
    // 版本标记
    uint64_t ma_version_tag;
    // key集合，哈希表就存在这里面
    PyDictKeysObject *ma_keys;
    // entries集合，split中，所有的键值对都存在ma_values里，而combined型的ma_values将会是null
    PyObject **ma_values;
} PyDictObject;

key集合

typedef struct _dictkeysobject PyDictKeysObject;
struct _dictkeysobject {
    // key集合的引用数
    Py_ssize_t dk_refcnt;
    // 哈希表索引数组的大小
    Py_ssize_t dk_size;
    // 字典查询方法
    dict_lookup_func dk_lookup;
    // 字典中key集合可用大小
    Py_ssize_t dk_usable;
    // entries中键值对的数量
    Py_ssize_t dk_nentries;
    // 每个键对应存放数据位置的索引
    char dk_indices[];
};

entries集合

typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    // 在split型中，value存放在ma_values中，所以只有combined型的时候，me_value才存放value
    PyObject *me_value;
} PyDictKeyEntry;

dict基本配置和缓冲池

基本配置

// 哈希表的起始尺寸为8
#define PyDict_MINSIZE 8

// 哈希表相对于索引数量的尺寸
#define ESTIMATE_SIZE(n)  (((n)*3+1) >> 1)

// 当需要更新dict尺寸时，尺寸大小为索引数*3
#define GROWTH_RATE(d) ((d)->ma_used*3)

缓冲池

// dict缓冲池大小，尺寸和list缓冲池一样是80
#ifndef PyDict_MAXFREELIST
#define PyDict_MAXFREELIST 80
#endif
// dict对象和dict中的key集合对象都有进行缓冲池操作
static PyDictObject *free_list[PyDict_MAXFREELIST];
static int numfree = 0;
static PyDictKeysObject *keys_free_list[PyDict_MAXFREELIST];
static int numfreekeys = 0;

创建dict

PyObject *
PyDict_New(void)
{
    // 引用+1
    dictkeys_incref(Py_EMPTY_KEYS);
    // 通过空集合和空entries创建一个空字典
    return new_dict(Py_EMPTY_KEYS, empty_values);
}

// 创建一个dict对象
static PyObject *
new_dict(PyDictKeysObject *keys, PyObject **values)
{
    PyDictObject *mp;
    assert(keys != NULL);
    // 缓存池
    if (numfree) {
        mp = free_list[--numfree];
        assert (mp != NULL);
        assert (Py_TYPE(mp) == &PyDict_Type);
        _Py_NewReference((PyObject *)mp);
    }
    else {
        mp = PyObject_GC_New(PyDictObject, &PyDict_Type);
        if (mp == NULL) {
            dictkeys_decref(keys);
            if (values != empty_values) {
                free_values(values);
            }
            return NULL;
        }
    }
    // 初始化操作，注意这里的keys和values的内容还都是空的
    mp->ma_keys = keys;
    mp->ma_values = values;
    mp->ma_used = 0;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    ASSERT_CONSISTENT(mp);
    return (PyObject *)mp;
}

添加元素

int
PyDict_SetItem(PyObject *op, PyObject *key, PyObject *value)
{
    PyDictObject *mp;
    Py_hash_t hash;
    if (!PyDict_Check(op)) {
        PyErr_BadInternalCall();
        return -1;
    }
    assert(key);
    assert(value);
    mp = (PyDictObject *)op;
    // 获取对象的哈希值，如果不是可哈希的，则无法执行setitem操作
    if (!PyUnicode_CheckExact(key) ||
        (hash = ((PyASCIIObject *) key)->hash) == -1)
    {
        hash = PyObject_Hash(key);
        if (hash == -1)
            return -1;
    }
    // 如果哈希表是一个空表，则直接往空字典插入数据
    if (mp->ma_keys == Py_EMPTY_KEYS) {
        return insert_to_emptydict(mp, key, hash, value);
    }
    // 添加或修改操作函数
    return insertdict(mp, key, hash, value);
}
``` 

#### insertdict修改逻辑

static int
insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
PyObject *old_value;
PyDictKeyEntry *ep;

Py_INCREF(key);
Py_INCREF(value);
if (mp->ma_values != NULL && !PyUnicode_CheckExact(key)) {
    if (insertion_resize(mp) < 0)
        goto Fail;
}
// 寻找对应key的索引
Py_ssize_t ix = mp->ma_keys->dk_lookup(mp, key, hash, &old_value);
// 异常情况处理
if (ix == DKIX_ERROR)
    goto Fail;

assert(PyUnicode_CheckExact(key) || mp->ma_keys->dk_lookup == lookdict);
MAINTAIN_TRACKING(mp, key, value);

if (_PyDict_HasSplitTable(mp) &&
    ((ix >= 0 && old_value == NULL && mp->ma_used != ix) ||
     (ix == DKIX_EMPTY && mp->ma_used != mp->ma_keys->dk_nentries))) {
    if (insertion_resize(mp) < 0)
        goto Fail;
    ix = DKIX_EMPTY;
}
// 如果对应的key的映射为空，则代表添加数据
if (ix == DKIX_EMPTY) {
    assert(old_value == NULL);
    if (mp->ma_keys->dk_usable <= 0) {
        if (insertion_resize(mp) < 0)
            goto Fail;
    }
    // 寻找哈希表中当前key的插入位置
    Py_ssize_t hashpos = find_empty_slot(mp->ma_keys, hash);
    // ep指向entries的最后一位（索引为dk_nentries处）
    ep = &DK_ENTRIES(mp->ma_keys)[mp->ma_keys->dk_nentries];
    // 设置indices中对应entries的索引，可以看到设置的entries索引就是entries的数量，因为键值对每次都是往entries的最后一位添加的
    dictkeys_set_index(mp->ma_keys, hashpos, mp->ma_keys->dk_nentries);
    // 设置新加入entries的键值对数据
    ep->me_key = key;
    ep->me_hash = hash;
    if (mp->ma_values) {
        assert (mp->ma_values[mp->ma_keys->dk_nentries] == NULL);
        mp->ma_values[mp->ma_keys->dk_nentries] = value;
    }
    else {
        ep->me_value = value;
    }
    // 添加成功操作
    mp->ma_used++;
    mp->ma_version_tag = DICT_NEXT_VERSION();
    mp->ma_keys->dk_usable--;
    mp->ma_keys->dk_nentries++;
    assert(mp->ma_keys->dk_usable >= 0);
    ASSERT_CONSISTENT(mp);
    return 0;
}
// 如果不是添加操作，并且指定entries的value和当前传入的value不同，则需要更新value
if (old_value != value) {
    // split型表的操作
    if (_PyDict_HasSplitTable(mp)) {
        // 直接更新entries中对应索引的value
        mp->ma_values[ix] = value;
        // 当前位置属于pending状态（已删除状态），则说明之前没有使用，现在使用了，所以使用数+1
        if (old_value == NULL) {
            assert(ix == mp->ma_used);
            mp->ma_used++;
        }
    }
    // combined型表的操作
    else {
        assert(old_value != NULL);
        // 由于key、value都是存在哈希表中，直接修改哈希表对应位置的value
        DK_ENTRIES(mp->ma_keys)[ix].me_value = value;
    }
    mp->ma_version_tag = DICT_NEXT_VERSION();
}
Py_XDECREF(old_value);
ASSERT_CONSISTENT(mp);
Py_DECREF(key);
return 0;

Fail:
Py_DECREF(value);
Py_DECREF(key);
return -1;
}



## hash冲突与dict hash冲突处理
哈希算法被计算的数据是无限的，而计算后的结果范围有限，
因此总会存在不同的数据经过计算后得到的值相同，这就是哈希冲突
这个时候就需要一种方法解决这种冲突

### hash冲突解决方法

#### 开放寻址法
从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。
后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于
等于所需要存放的元素。

- 线行探查法
依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。
直到碰到空闲的单元或者探查完全部单元为止。

- 平方探查法
发生冲突的单元d\[i], 加上 1²、 2²等。即d\[i] + 1²，d\[i] + 2², d\[i] + 3²...直到找到空闲单元。

- 双散列函数探查法
这种方法使用两个散列函数hl和h2。其中hl和前面的h一样，以关键字为自变量，
产生一个0至m—l之间的数作为散列地址；h2也以关键字为自变量，产生一个l至m—1
之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，
探查序列的步长值是固定值l

- 二次探测法

f(key) = (f(key)+di) MOD m (di = 1^2, -1^2, 2^2, -2^2,……, q^2, -q^2, q <= m/2)

1	- 注：1^2 表示是 1的平方

设哈希表长m＝14，哈希函数H（key）＝key％11。
表中已有4个结点：addr(15)=4，addr(38)=5，addr(61)=6，addr(84)=7，
其余地址为空。如果用二次探测再散列处理冲突，关键字为49的结点的地址是？
因为 f(49) = 5 与 f(38) 冲突
所以需要采用二次探测再散列来处理冲突
(f(49) + di) MOD 14(哈希表长m＝14)
第一次 di = 1^2
（5 + 1）MOD 14 = 6 与addr(61)=6冲突
第二次 di = -1^2
（5 - 1）MOD 14 = 4 与addr(15)=4 冲突
第三次 di = 2^2
（5 + 4）MOD 14 = 9 没有冲突
所以 addr(49)=9

```

链地址法

冲突生成链表，链表一直往下。java使用此方法作为首要解决hash冲突的方法，
jdk1.7完全采用单链表来存储同义词，jdk1.8则采用了一种混合模式，对于链表
长度大于8的，会转换为红黑树存储。

再hash

同时构造多个不同的哈希函数
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，
直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间

###dict的hash冲突解决
使用开放寻址的二次探查，如果使用的容量超过数组大小的2/3，
就申请更大的容量。数组大小较小的时候resize为*4，
较大的时候resize*2

python源码解析

3.6版本前和3.6后对比

3.6前

dict状态

3.6后

dict状态

3.6后源码

PyDictObject

key集合

entries集合

dict基本配置和缓冲池

创建dict

添加元素

链地址法

再hash