python3.7的字典是有序的

发布时间:2019-10-18 09:06:59编辑:auto阅读(583)

    python3.7的字典是有序的

    旧结构

    python3.7之前的字典结构,经典粗暴的hash表实现方式,这样的话每次hash表的扩容和缩容都可能导致hash值的改变。

    hash表容量更新的前后,它的键之间的相对顺序是会变化的,因此字典的元素是无序的。旧结构类似下面

    --+-------------------------------+
      | 哈希值 (hash)  键 (key)  值 (value)
    --+-------------------------------+
    0 |    hash0      key0    value0
    --+-------------------------------+
    1 |    hash1      key1    value1
    --+-------------------------------+
    2 |    hash2      key2    value2
    --+-------------------------------+
    . |           ...
    __+_______________________________+

    新结构

    Indices
    ----------------------------------------------------
    None | index0 | None | None | index2 | None | index1 ...
    ----------------------------------------------------
    
    Entries
    --------------------
    hash0   key0  value0
    ---------------------
    hash1   key1  value1
    ---------------------
    hash2   key2  value2
    ---------------------
            ...
    ---------------------
    

    新结构由 Indices(索引,数组实现) 和 Entries(实体,PyDictObject类型) 两种结构组成。

    • 当插入一个数据时,先计算数据对应的hash值并映射成 Indices 数组的一个下标,没有冲突的话就将另一个值 Entries_index(暂时这么叫吧) 填入Indices数组中下标对应的位置。并在Entries后面追加一行记录,类似 hash值, key值, value值 。如果冲突的话可以用基本的解决冲突的办法,这里不赘述了。

    这种方法,字典 增删改查的时间复杂度 会有以前的O(1) 变为O(2),因为多了一步查找的过程。而且字典扩容和缩容时要按照Indices的顺序来保持字典始终有序。

    但是至少有两个优化。

    • 字典占用的内存变小了。旧的字典总会预留大于 1/3的容量的hash位置,防止hash碰撞过多影响效率。现在则不必预留。
    • 字典有序了。

    源码见:
    dictobject.h

    dictobject.c

    记于:2019/07/23

关键字