编程Python

Python内置数据结构(列表,集合,字典)源码初探

字数统计: 633字   |   阅读时长: 2分

摘要: Python源码 -- 列表、集合、字典的一些要点

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

(1) 列表: 可以存放任何类型的数据

(2) 集合: 无序，不重复，可变

  • 从列表中删除重复项
  • 交集、并集、差分和对称差分等集合操作
  • set 不记录元素位置或者插入点。因此不支持 indexing 或其它类序列的操作。
  • 查看 PySetObject 可以发现，set 的值的存储是通过结构 setentry 来保存数据值的；
  • Python3.7 源码 — PySetObject
  • PySetObject 变化过程中，元素有三种状态, Python3.7 源码 — three kinds of entries
1
2
3
4
5
6
7
8
9
/* There are three kinds of entries in the table:
1. Unused:  key == NULL and hash == 0
2. Dummy:   key == dummy and hash == -1
3. Active:  key != NULL and key != dummy and hash != -1
The hash field of Unused slots is always zero.
The hash field of Dummy slots are set to -1
meaning that dummy entries can be detected by
either entry->key==dummy or by entry->hash==-1.
*/

(3) 字典:

1
2
3
4
5
6
typedef struct {
    /* Cached hash code of me_key. */
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value; /* This field is only meaningful for combined tables */
} PyDictKeyEntry;

其中 me_hash 是哈希生成的值，me_key 是对应的 key 值，me_value 就是对应的 value 值。

  • 字典对象是通过 PyDictObject 来实现, Python3.7 源码 — PyDictObject

  • Python3.4 后,字典被分为分离字典(split-table dictionaries)与联合字典(combined-table dictonaries)两类

    • 分离字典: 用来保存对象的 __dict__ 属性，它们的键表被缓存在类型属性中，并允许所有该类型的实例共享值。
    • 联合字典: 直接通过 dict 內建函数与 {} 生成。

  • 一个 PyDictObject 对象的变化过程中，entry 的状态会在不同的状态间转换。基本上在如下四种状态中转换：Unused、Active、Dummy 和 Pending。其中 Pending 是集合没有的。

    • Unused: me_key 和 me_value 均为空，Unused 可以转变为 Active
    • Active: me_key 和 me_value 均不为空，Active 可以转变为 Dummy 或者 Pending 状态
    • Dummy: 先前保存了一个 Active 的键值对，但是这个键值对被删除了，Dummy 的位置不能被重新使用，一旦发生碰撞，探针序列就无法知道这对键值对曾是活跃的键值对。
    • Pending: me_key 不为空而 me_value 为空
Share