知其然,还要知其所以然. 讲讲dict,list,set常见的容器的底层设计
Dict
查询平均复杂度O(1),
增删复杂度O(1)
dict,又叫字典.在python3.6和以前版本中的实现和之后不太一样.简单来说:
- python3.6及之前是无序的
- python3.7及之后是有序的
无序dict版本
底层:哈希列表, 列表里的元素都为(hash_value, key, value), 其中hash_value为用hash函数对key作用生成, 这也是为什么dict的key必须是可hash的.
因为是列表,所以通过下标查找元素的复杂度为O(1).
1
2
3
4
5
6
7
8
# 无序dict底层的hash列表大概长这样
entries = [
['--', '--', '--'],
[hash_value, key, value],
['--', '--', '--'],
['--', '--', '--'],
[hash_value, key, value],
]
Q:如何知道元素的下标呢?
A:将hash_value对列表的长度n取模,就可以得到一个[0, n-1]之间的下标.
Q:如果hash_value取到相同的下标怎么办?
A:判断key值是否相同,相同则进行修改操作,不同则认为出现了哈希冲突.
Q:如何解决hash冲突?
A:1. 如果元素数量大于列表大小的2/3, 也叫哈希表的装填系数.则先扩容, 扩容能降低hash冲突的可能性 2.对取模得到的下标i进行probe(i)的操作,直至找到一个空的位置.(为什么一定能找到则需要用一些高等数学知识来证明,这里只需要知道python保证了一定能找到.
Q: 删除dict中的元素的处理流程
有序dict版本
有序的dict的实现主要是通过另外一张indices表来辅助,保证enteies的元素是按顺序存储的
1
2
3
4
5
6
indices = [None, None, index, None, index, None, index]
entries = [
[hash0, key0, value0],
[hash1, key1, value1],
[hash2, key2, value2]
]
indices表存放的是元素在enteies的位置. 而hash的结果则表示元素在indices的位置
Set
同dict,同样使用哈希表来实现
List
list底层实现为可变长数组
Tuple
固定长度的数组
