摘要: Python源码 -- 列表、集合、字典的一些要点
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
(1) 列表: 可以存放任何类型的数据
- 查看 PyListObject 可以发现,list 实际存放的是
PyObject*
指针 - Python3.7 源码 — PyListObject
(2) 集合: 无序,不重复,可变
- 从列表中删除重复项
- 交集、并集、差分和对称差分等集合操作
- set 不记录元素位置或者插入点。因此不支持 indexing 或其它类序列的操作。
- 查看 PySetObject 可以发现,set 的值的存储是通过结构 setentry 来保存数据值的;
- Python3.7 源码 — PySetObject
- PySetObject 变化过程中,元素有三种状态, Python3.7 源码 — three kinds of entries
1 | /* There are three kinds of entries in the table: |
(3) 字典:
- 一个键值对的对应保存就是 PyDictKeyEntry 类型来保存, Python3.7 源码 — PyDictKeyEntry
1 | typedef struct { |
其中 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
为空
- Unused: