Python - Dict + Set
基础
- 字典是由 kv 对组成的元素的集合,在 Python 3.7+,字典被确定为有序
- 相比于列表和元组,字典的性能更优,对于查找、添加和删除操作,时间复杂度为 O(1)
- 集合是一系列唯一无序的元素组合
- 字典和集合,无论是 Key 还是 Value,都可以是混合类型
字典初始化
1 | d1 = {'name': 'jason', 'age': 20, 'gender': 'male'} |
集合初始化
1 | s1 = {1, 2, 3} |
混合类型
1 | s = {1, 'hello', 5.0} |
字典通过 Key 访问,如果不存在,则抛出异常
1 | d = {'name': 'jason', 'age': 20} |
可以通过 get(key, default) 函数来访问,如果不存在,则返回默认值
1 | d = {'name': 'jason', 'age': 20} |
集合不支持索引操作,集合本质上是一个哈希表,与列表不一样
1 | s = {1, 2, 3} |
判断一个元素是否在一个集合或者字典中 - value in dict / set
1 | s = {1, 2, 3} |
字典和集合同样支持增加、删除、更新等操作
set.pop() 删除集合中的最后一个元素,但集合本身是无序的,随机删除
1 | d = {'name': 'jason', 'age': 20} |
1 | s = {1, 2, 3} |
根据字典的 Key 或者 Value,进行升序或者降序
返回一个列表,列表中的每个元素是由原字典的 Key 和 Value 组成的元组
1 | d = {'b': 1, 'a': 2, 'c': 10} |
对于集合,直接调用 sorted(set),返回一个排序后的列表
1 | s = {3, 4, 2, 1} |
性能
- 字典和集合是进行过性能高度优化的数据结构,特别适用于查找、添加和删除操作
- 字典的内部组成是哈希表,查找的时间复杂度为 O(1)
- 集合是高度优化的哈希表,查找的时间复杂度也是 O(1)
原理
字典和集合的内部结构都是哈希表
- 对于字典来说,哈希表存储了 Hash、Key 和 Value 3个元素
- 对于集合来说,哈希表中没有 Key 和 Value,只有单一元素,在 Java 中,为 Hash、Key、null
哈希表
老版本 Python 的哈希表 - 随着哈希表的扩张,会变得越来越稀疏 - 浪费存储空间
1 | --+-------------------------------+ |
为了提升存储空间的利用率,将索引与(Hash、Key 和 Value)单独分开 - 类似于 Java HashMap
1 | Indices |
插入
- 每次向字典或者集合插入一个元素时,Python 会首先计算 key 的哈希值,即 hash(key)
- 再与 mask = PyDicMinSize-1 进行与操作,计算该元素应该插入哈希表的位置 index = hash(key) & mask
- 如果哈希表该位置是空的,则该元素会被插入其中
- 如果哈希表此位置已被占用,Python 会比较两个元素的 Hash 和 Key 是否相等
- 如果都相等,表明该元素已经存在,如果值不同,则更新值
- 如果有一个不相等,表明发生哈希冲突,Python 会继续寻找哈希表中的空余位置,直到找到为止
- 简单实现为线性寻找,即从该位置开始,挨个往后寻找空位
查找
- 与插入类似,Python 根据 index = hash(key) & mask 找到预期位置
- 比较预期位置中的 Hash 和 Key 是否命中
- 如果命中,则直接返回
- 如果不命中,则继续查找,直到找到空位或者抛出异常为止
删除
- Python 会暂时对命中位置的元素,赋予一个特殊值,等到重新调整哈希表的大小时,再将其删除
Rehashing
- 哈希冲突的发生,往往会降低字典和集合操作的速度
- 为了保证高效性,字典和集合内的哈希表,往往会保证其至少留有 1/3 的剩余空间
- 当剩余空间小于 1/3 时,Python 会重新获取到更大的内存空间,扩充哈希表
- 哈希表内的所有元素都会被重新排放
- 虽然哈希冲突和 Rehashing,都会导致速度减缓,但发生次数极少
- 所以插入、查找和删除的平均时间复杂度依然为 O(1)
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.