Python内核阅读(六): Dict对象

Python 2017-08-05

起步

python中PyDictObject采用了散列表,平均状况是O(1)复杂度的搜索效率.

散列表是通过一定的函数将需搜索的键值映射为一个整数,将这个整数视为索引去访问某片连续的内存区域. 一般情况下,hash table会申请一块较大的连续内存通过映射函数f(n)得到所对应的索引.

在使用散列表过程中,随着需要存储的数据增多,hash冲突的概率就越高.会直接影响到hash的效率和性能.

在python中采用闭散列法来解决冲突,闭散列法也称为开放定址法.当产生冲突时,python会通过一个二次探测函数f,计算下一个候选索引, 如果索引不可用,就再次用f探测.直到找到一个可用的位置.

之所以叫做闭散列法,就是因为冲突的元素没有开辟额外的存储空间,还是在原先hash表的空间范围之内。

关联容器

假如我们将具有某种关系的两个数组成一组,例如(3, 6), (4, 8),他们具有2倍关系, 组成一组的好处就是找到3就能立马找到6.

因此关联容器常以(key, value)存在.Python中定义这样的关联容器Entry:

[dict-common.h]
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

在PyDictKeyEntry中,me_hash表示me_key的散列值, 保存这个值是为了避免重复计算. 在PyDictObject对象发生变化时, 其中的entry也会在不同的状态间切换.关联容器存在3中状态:

  • Unused(未使用):index == DKIX_EMPTY
  • Active(活动): index >= 0, me_key != NULL and me_value != NULL
  • Dummy(删除状态): index == DKIX_DUMMY 之所以不能直接转成Unused状态是因为这要会导致冲突测链中断
#define DKIX_EMPTY (-1)
#define DKIX_DUMMY (-2)  /* Used internally */
#define DKIX_ERROR (-3)

关联容器的实现

[dictobject.h]
typedef struct {
    PyObject_HEAD

    // Active元素个数
    Py_ssize_t ma_used;

    // 全局唯一, 值会随着dict的修改而改变
    uint64_t ma_version_tag;

    PyDictKeysObject *ma_keys;

    // 如果ma_values == NULL 表示哈希表是结合的, 如果ma_values != NULL 则表被拆分
    PyObject **ma_values;
} PyDictObject;

PyDictKeysObject是这样定义的:

[dict-common.h]
struct _dictkeysobject {
    Py_ssize_t dk_refcnt;

    // hash表允许容纳元素的个数 必定是2的指数
    Py_ssize_t dk_size;

    // 与hash table有关的函数
    dict_lookup_func dk_lookup;

    // 元素个数 Active + Dummy
    Py_ssize_t dk_usable;

    // 元素个数 Active
    Py_ssize_t dk_nentries;

    union {
        int8_t as_1[8];
        int16_t as_2[4];
        int32_t as_4[2];
    } dk_indices;
};

“PyDictKeyEntry dk_entries [dk_usable];” 数组如下,参阅DK_ENTRIES()宏:

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

从python3.6开始,借鉴 PyPy 字典设计,采用更紧凑的存储结构.内存效率更高, 更多信息可以查看https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html

key可以分布如下:

+---------------+
| dk_refcnt     |
| dk_size       |
| dk_lookup     |
| dk_usable     |
| dk_nentries   |
+---------------+
| dk_indices    |
|               |
+---------------+
| dk_entries    |
|               |
+---------------+

dk_indices 是实际的哈希表。它在条目中保存索引,或KIX_EMPTY(-1)或DKIX_DUMMY(-2)。哈希表能容纳元素的个数 dk_size .dk_entries是一个PyDictKeyEntr的数组。它的大小是USABLE_FRACTION(dk_size)。 可以使用DK_ENTRIES(dk)来获取指向条目的指针。注意:由于负值用于DKIX_EMPTY和DKIX_DUMMY,所以键入 dk_indices条目是有符号整数,int16用于表大小dk_size == 256。

为什么说更省空间呢?

比如需要一个字典d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'},那其结构在旧模式下是:

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

而使用新的为:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

indices就是哈希表,改变的只是布局, 哈希表算法将不变.例子中节省了得58%的内存。据说能节省30%~95~的空间(取决表的完整程度). 除了节省空间, 新的布局迭代更快, keys() values() items(),直接在关联容器entries获取, 无需判断['--', '--', '--']空关联容器. 移动或者复制hash表,只需操作indices即可.

请注意,sizeof(index)可以小到单个小字节的字节,大字节的两个字节直到sizeof(Py_ssize_t)为巨大的dict。因此可以看到PyDictKeyObject中的dk_indices是个联合体.为了是更省内存. 作者很抠内存的, 巴不得一个字节当两个字节用.

PyDictObject 对象的创建

python内部通过PyDict_New来创建一个新的dict对象:

[dictobject.h]
PyObject * PyDict_New(void)
{
    PyDictKeysObject *keys = new_keys_object(PyDict_MINSIZE);
    if (keys == NULL)
        return NULL;
    return new_dict(keys, NULL);
}

PyDict_MINSIZE 值为8, 默认情况下, PyDict_New会创建8个entry

static PyDictKeysObject *new_keys_object(Py_ssize_t size)
{
    PyDictKeysObject *dk;
    Py_ssize_t es, usable;

    usable = USABLE_FRACTION(size);
    es = 4;

    if (size == PyDict_MINSIZE && numfreekeys > 0) {
        // 使用缓冲池
        dk = keys_free_list[--numfreekeys];
    }
    else {
        dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
                             + es * size
                             + sizeof(PyDictKeyEntry) * usable);
    }
    DK_DEBUG_INCREF dk->dk_refcnt = 1;
    dk->dk_size = size;
    dk->dk_usable = usable;
    dk->dk_lookup = lookdict_unicode_nodummy;
    dk->dk_nentries = 0;
    // hash table 初始化
    memset(&dk->dk_indices.as_1[0], 0xff, es * size);
    memset(DK_ENTRIES(dk), 0, sizeof(PyDictKeyEntry) * usable);
    return dk;
}

keys.entries 和 values 用数组按添加顺序存储主键和值引用。实际哈希表由 keys.indices 数组承担,通过计算主键哈希值找到合适位置,然后在此存储主键在 keys.entries 的实际索引。如此,只要通过 indices 获取实际索引后,就可读取主键和值信息。

dk = PyObject_MALLOC(sizeof(PyDictKeysObject)
                             - Py_MEMBER_SIZE(PyDictKeysObject, dk_indices)
                             + es * size    // hash索引表
                             + sizeof(PyDictKeyEntry) * usable);    // PyDictKeyEntry 的数组, 申请大小为表size的2/3

也就是说 PyDictKeysObject 中成员 dk_indices 有两个重要的成分, 一个是前半部分的hash table索引. 另一个是后半部分的关联容器数组

元素搜索

无论是字典的设置d["aaa"] = 3 还是获取 a = d["aaa"] 都需要对hash table进行搜索. python位hash表搜索提供了多种函数, 通用的lookdict, 针对字符串类型的lookdict_unicode, 针对数字的 lookdict_index. 但他们的算法是相同的. lookdict 是获取字典

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;    // mask是2的指数-1, 因此相当于取模

    for (;;) {
        Py_ssize_t ix = dk_get_index(dk, i);// dk->indecs[i]
        if (ix == DKIX_EMPTY) {
            *value_addr = NULL;
            return ix;
        }
        if (ix >= 0) {
            PyDictKeyEntry *ep = &ep0[ix];
            assert(ep->me_key != NULL);
            if (ep->me_key == key) { // 同一个引用
                *value_addr = ep->me_value;
                return ix;
            }
            if (ep->me_hash == hash) {  // 因为不同值的hash结果可能相同
                PyObject *startkey = ep->me_key;
                Py_INCREF(startkey);
                int cmp = PyObject_RichCompareBool(startkey, key, Py_EQ);// 进行完整的比较
                Py_DECREF(startkey);
                if (cmp < 0) {
                    *value_addr = NULL;
                    return DKIX_ERROR;
                }
                if (dk == mp->ma_keys && ep->me_key == startkey) {
                    if (cmp > 0) {
                        *value_addr = ep->me_value;
                        return ix;
                    }
                }
                else {
                    /* The dict was mutated, restart */
                    goto top;
                }
            }
        }
        perturb >>= PERTURB_SHIFT;
        i = (i*5 + perturb + 1) & mask; // 哈希探测函数
    }
    assert(0);          /* NOT REACHED */
    return 0;
}

dk_get_index(dk, i) 简单理解为->dk_indices.as_1[i] 即可, 对于不同规模的hash表, 用as_1或as_2有所不同而已. 对于lookdict来说, 永远不会返回NULL, 如果搜索不到待查找的key, 同样会返回一个空的关联容器的索引.

在python的字典中,"相同"这个概念包含了两个含义:

  1. 引用相同
  2. 值相同 在lookdictep->me_key == key 就意味着他们的值相同, 在其判断体内加printf("key is same\n"); 可以看到:
>>> a = {}
>>> a[2] = "python"
>>> a[2]
key is same
'python'
>>> a[999] = "php"
>>> a[999]
'php'
>>>

小整数对象是共享的, 因此他们key都是指向同一个地址. 大整数对象并不是共享, 但是999明明在key中是存在的,因此"值相同"规则就有存在的意义.

总结搜索过程入下:

  1. 根据PyObject *key 的哈希值获得entry索引, 这是冲突探测链上第一个entry索引.
  2. 两种情况下,搜索结束:
    • entry处于Unuse状态,表示冲突弹窗搜索结束, 搜索失败
    • ep->me_key == key 表示entry的key与待搜索key是同一个PyObject对象, 搜索成功
  3. 若当前的entry处于Dummy态, 设置为freeslot
  4. 检查Active态中的entry中的key是否与待查找的key"值相同", 若找到, 搜索成功. 若不匹配, 则沿着探测链查找.探测链检测到DUMMY状态是,设置freeslot

当entry中的key与待查找的key不匹配时, 拦着探测链顺藤摸瓜.

探测链上的过程与前面的过程基本一致, 总之,lookdict 如果搜索成功, 返回一定是有效的entry索引.如果搜索失败,则返回一个Unused状态的entry索引.因为dummy状态的entry实际也是一个空闲的entry, 当遍历到Dummy状态的entry,便会设置freeslot,freeslot是下一个被inserte";&g曠为sed状eE軛探穎测闲E eE'x[败,则迚探况下s测闲E 个okdict_indexke享,楚值直省败,则 当遍已. 的e探测链gt;>过PyD说 量冲池 ect 对象皐索成索维抁皂当䐍ode>之 彐量䐍找结数 用传递ENT着ENT䐍找NT结数 探测链// ,python紧凑dex >n" ((i{ ed + + 1) & mask; // 哈帰意味獳dex >n" (i); rb +i) %ndex dk-&意味y状ex dk-个-1, 因元素搜插p> 假如我 mutasces凴, 向同try到储䘯同柺硂彊探测static Py_ssize_ PyO&g, NULect 对象 ct *key, / // k, bject **value_ad在.PyDictKeysOk; P{ = NULL i = (Entry *ep = &eDictKeysOtartkey)与 (startkey)在.Py (size_mp-_keys; NULL 舙表被; numfreeke!PyUdummy; CheckEx/">LL); vt;= 0re(ho / dk--_kask g Fai }, turn _kt ix = dk_get_in_keys; ep0ndices.alookdi-_k_EQ);//bject ; num{ = NULL DKIX_EMPTY) { Fai } 探ive态metActive元ive态, 因L);必分整的bjecry扩素 DKIUNCtry _HasS/rstT //-_kask numfreek ((ix{ // p; ep->me{ = NULL表示哈; numfreeke_keys; //and ix) || IX_EMPTY) { p; ep->me_keys; //and _keys; ep0ndices.a= 0; ) vt;= 0re(ho / dk--_kask g Fai }, t_inY和DKIX_D (sizeturn _k探i.散回 DKIX_EMPTY) { *valuACHIre(ho= Pyo_obj ent量+1 ; tkeys; ep0ndices.ausable;k // i; UNCtry _Checkades { cy-_ka i }< } 探metA S(dk); _keys; ep0)[ .!= NULL< Fai = mp-&t iartkey)在.Py (sizet iartkey)与 }

dk_储䘯同kdict

,设置要的能相:i.散回个,个Unus是中的 当遍,丙下,搜索关联替宯于kdictent,hash ta). de>d["aaa"] NULL 示me_ 但他们hash表try_indices 3 4意味罓实个调置_indiceNCtry _SetIode意味 e>[dictobje PyONCtry _SetIodeLeck; P{ct *key, / k; P在.PyDictKeysOtry p, PyObjec i = (En// k, bjecDictKeyject_Lect 对象 ) DKI!PyUdummy; CheckEx/">LL); || ( / _ineyEnASCIIp, PyObj)/ 同ndice / 表ne D { / _inRichCompaHashLL); i = (i*5 +mp- / _ine D }

dk_aluesL);局, 替[dictobje探梞长能DKIX_ERROGROWTH_RATK_I) ((_I)eys; //*2)+(_I)eys; sndices.a dk-gt;

dk_, uint请SABLE交pkdict<, NU/ dk-意身彊探测static Py_ssize_ PyO, NU/ dk-Lect 对象 ct *kma_used; &gdk-yDictKeysOma_used; perobj dk-&g Entry *epdk; P{ s&g Enp, PyObj*{ NULL &g Entry *epE; top: nteFEMd('re smdef _请yDict{ //. { obj dk-ct_NCtry _amp;&am i = (i*5 robj dk-sk Dict{ numfreekeybj dk-{ i = (i*5 robj dk-sk k //e D DictKey{ sct_tkeys; ep0 i = ({ NULL ct_tkeys; NULL &g 探簏为t对之A tkeys; sct_object(Py_ssize_obj dk- iA DKI{ sndices.alookdi表unicode_ tkeys; ep0ndices.alookdict_unicode_ i = (tkeys; NULL ct_ r _inY()宏:

{ s i = (nteMassunip-below sEles we tyl= eansfhea1; e:u _o_obj s *alue 'ra; NULLn"); nL_k_E_key == key

dk_/ dk-簆 / dk_s量扩礧况, 或存掬迁睍,塨 / ed状e享hash ttt寜PyDicn id

pyeader <="2mens://www.hongweipeng.com/usr/themes/GreenGrapes/img/head.jpg"ment(Kve typeds-cc.pn> 通迯数刱sed载"> 通明has䐍抠内且sizeey䖣嫠sepre" s
馒息吧n id= s/div> tlogo-urbtn btncsscsubmit"> /div> data-toggh" mmoda"data-tar(dk="#payl">da">¥co/ d= s="m-logo-url>da">da">= s="m-logo-url>da"-d=1"odiv clas s="m-logo-url>da"-learfix
  • ="m-logo-url>da"
    /div> l-md-8">/spandata- ''m")s mmoda">"menu_aria- =" ">&redode2>关联s="label labsr- y">C/spa2>关联//div> d=

    da" thon">谢谢据增唯持假4d= s

    nam n id= s

    > this. pe="text/javascript"> (function getElemenwrcod('httdth: 10 ''; : !imtentaearchsubtaex-a-mm_117570917_17204454_1my'6003>

    a>' int c taex_sct_createElement(tag); "(functi int c taex_s.idden';" hreft"> (functi i = (i*5 r taex_s.UTF-8">ct_"gbk" i = (i*5 r taex_s.i; "taex-s-mm_117570917_17204454_1my'6003>< i = (i*5 r taex_s.asykupa.n } taex_s.s:/ "//p? rnx/01/fex?i=mm_117570917_17204454_1my'6003>< i = (i*5 r taex__ingetElementById('rese('form'); anvas" if ex_h) ex_hfore(holder, rtaex_s, ex_hffirstut); int c