python的dict源码解读

发表于 | 分类于

python的dict源码解读

PyDictEntry

1
2
3
4
5
typededf struct{
  Py_ssize_t me_hash;
  PyObject *me_key;
  PyObject *me_value;
} PyDictEntry

其中me_hash 用于存储hash值

PyDictObject

1
2
3
4
5
6
7
8
9
10
11
12
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];
};

其中PyObject_HEAD 用于表明首地址，ma_fill 为活动槽以及哑槽的综述，但已有的记录被删除后，该记录的位置被标记为哑槽，ma_used 为活动槽总数，ma_mask 为数组长度减一的标记，用于计算槽的索引，ma_table 为数组本身，ma_smalltable为长度为 8 的初始数组，即字典的初始大小。

构造过程

构造过程主要分为以下几步：

  1. 如果PyDictObject缓冲池中有可用的对象，则取出最后一个对象使用，将各个参数初始化，如果没有则创建一个对象；
  2. 关联搜索方法
  3. 返回对象

添加键值对过程

这里别人的博客中写的比较详细，我直接贴上来

现在我们想添加如下的键/值对：{‘a’: 1, ‘b’: 2′, ‘z’: 26, ‘y’: 25, ‘c’: 5, ‘x’: 24}，那么将会发生如下过程：

分配一个字典结构，内部表的尺寸为8。

  • PyDict_SetItem : key = ‘a’, value = 1
    • hash = hash(‘a’) = 12416037344
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 12416037344 & 7 = 0
        • slot 0 is not used so return it
      • init entry at index 0 with key, value and hash
      • ma_used = 1, ma_fill = 1
  • PyDict_SetItem : key = ‘b’, value = 2
    • hash = hash(‘b’) = 12544037731
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 12544037731 & 7 = 3
        • slot 3 is not used so return it
      • init entry at index 3 with key, value and hash
      • ma_used = 2, ma_fill = 2
  • PyDict_SetItem : key = ‘z’, value = 26
    • hash = hash(‘z’) = 15616046971
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 15616046971 & 7 = 3
        • slot 3 is used so probe for a different slot: 5 is free
      • init entry at index 5 with key, value and hash
      • ma_used = 3, ma_fill = 3
  • PyDict_SetItem : key = ‘y’, value = 25
    • hash = hash(‘y’) = 15488046584
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 15488046584 & 7 = 0
        • slot 0 is used so probe for a different slot: 1 is free
      • init entry at index 1 with key, value and hash
      • ma_used = 4, ma_fill = 4
  • PyDict_SetItem : key = ‘c’, value = 3
    • hash = hash(‘c’) = 12672038114
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 12672038114 & 7 = 2
        • slot 2 is free so return it
      • init entry at index 2 with key, value and hash
      • ma_used = 5, ma_fill = 5
  • PyDict_SetItem : key = ‘x’, value = 24
    • hash = hash(‘x’) = 15360046201
    • insertdict
      • lookdict_string
        • slot index = hash & mask = 15360046201 & 7 = 1
        • slot 1 is used so probe for a different slot: 7 is free
      • init entry at index 7 with key, value and hash
      • ma_used = 6, ma_fill = 6