基础
- 字典(dict):由键(key)和值(value)配对组成的元素的集合
- 在 Python3.7+,字典被确定为有序
- 相比于列表和元组,字典的性能更优,特别是对于查找、添加和删除操作,字典都能在常数时间复杂度内完成
- 集合(set): 和字典基本相同,唯一的区别,就是集合没有键和值的配对,是一系列无序的、唯一的元素组合
创建:
1
2
3
4
5
6
7
8
9
10
11d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
d2 = dict({'name': 'jason', 'age': 20, 'gender': 'male'})
d3 = dict([('name', 'jason'), ('age', 20), ('gender', 'male')])
d4 = dict(name='jason', age=20, gender='male')
d1 == d2 == d3 ==d4
True
s1 = {1, 2, 3}
s2 = set([1, 2, 3])
s1 == s2
True元素访问:
字典访问:可直接索引, 也可使用get(key,default)函数来索引
1
2
3
4
5
6
7
8
9
10
11
12d = {'name': 'jason', 'age': 20}
d['name']
'jason'
d['location']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'location'
d.get('name')
'jason'
d.get('location', 'null')
'null'集合:并不支持索引操作,因为集合本质上是一个哈希表,和列表不一样
- 可用 value in dict/set 来判断一个元素是否在字典/集合内
1
2
3
4
5
6
7
8
9
10
11s = {1, 2, 3}
1 in s
True
10 in s
False
d = {'name': 'jason', 'age': 20}
'name' in d
True
'location' in d
False
增加、删除、更新等操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18d = {'name': 'jason', 'age': 20}
d['gender'] = 'male' # 增加元素对'gender': 'male'
d['dob'] = '1999-02-01' # 增加元素对'dob': '1999-02-01'
d
{'name': 'jason', 'age': 20, 'gender': 'male', 'dob': '1999-02-01'}
d['dob'] = '1998-01-01' # 更新键'dob'对应的值
d.pop('dob') # 删除键为'dob'的元素对
'1998-01-01'
d
{'name': 'jason', 'age': 20, 'gender': 'male'}
s = {1, 2, 3}
s.add(4) # 增加元素 4 到集合
s
{1, 2, 3, 4}
s.remove(4) # 从集合中删除元素 4
s
{1, 2, 3}- 集合的 pop() 操作是删除集合中最后一个元素,可是集合本身是无序的,你无法知道会删除哪个元素,因此这个操作谨慎使用
对字典或集合进行排序:
对于字典,通常根据键或者值进行升序或降序排序
1
2
3
4
5
6
7
8d = {'b': 1, 'a': 2, 'c': 10}
d_sorted_by_key = sorted(d.items(), key=lambda x: x[0]) # 根据字典键的升序排序
d_sorted_by_value = sorted(d.items(), key=lambda x: x[1]) # 根据字典值的升序排序
d_sorted_by_key
[('a', 2), ('b', 1), ('c', 10)]
d_sorted_by_value
[('b', 1), ('a', 2), ('c', 10)]
# 这里返回了一个列表。列表中的每个元素,是由原字典的键和值组成的元组对集合进行排序:
1
2
3
4s = {3,4,2,1}
sorted(s)
[1,2,3,4]
# 返回排好序的列表
性能
- 字典和集合是进行过性能高度优化的数据结构,特别是对于查找、添加和删除操作
- 例子一:
- 电商企业的后台,存储了每件产品的 ID、名称和价格。现在的需求是,给定某件商品的 ID,我们要找出其价格。
- 若用列表来存储这些数据结构,并进行查找,时间复杂度就为O(n), 即使我们先对列表进行排序,然后使用二分查找,也会需要 O(logn), 且列表的排序还需要 O(nlogn) 的时间
- 若使用字典,只需 O(1) 的时间复杂度就可以完成,因为字典内部组成是一张哈希表
- 例子二:
- 现在需求变成,要找出这些商品有多少种不同的价格
- 若使用列表,则有两层循环(循环原始数据表和新建的unique列表),最差情况需要O(n^2)
- 若选择使用集合,则只有一层循环(只循环原始数据表,新建的unique为集合,添加/查找只需O(1)), 总时间复杂度就是O(n)
工作原理
- 字典和集合的内部结构都是一张哈希表
- 字典的表,储存了哈希值,键和值3个元素
- 集合的表,只有单一的元素
- 插入操作:
- 每次向字典或集合插入一个元素时,Python 会首先计算键的哈希值(hash(key)),再和 mask = PyDicMinSize - 1 做与操作,计算这个元素应该插入哈希表的位置 index = hash(key) & mask。如果哈希表中此位置是空的,那么这个元素就会被插入其中。
- 若此位置已被占用,Python 便会比较两个元素的哈希值和键是否相等:若两者都相等,则表明这个元素已经存在,如果值不同,则更新值;若两者中有一个不相等,这种情况我们通常称为哈希冲突(hash collision), 思是两个元素的键不相等,但是哈希值相等。种情况下,Python 便会继续寻找表中空余的位置,直到找到空位为止
- 查找操作
- Python 会根据哈希值,找到其应该处于的位置;
- 然后,比较哈希表这个位置中元素的哈希值和键,与需要查找的元素是否相等
- 如果相等,则直接返回;如果不等,则继续查找,直到找到空位或者抛出异常为止
- 删除操作
- Python 会暂时对这个位置的元素,赋于一个特殊的值,等到重新调整哈希表的大小时,再将其删除
- 哈希冲突的发生,往往会降低字典和集合操作的速度;为了保证其高效性,字典和集合内的哈希表,通常会保证其至少留有1/3 的剩余空间。随着元素的不停插入,当剩余空间小于 1/3 时,Python 会重新获取更大的内存空间,扩充哈希表。在这种情况下,表内所有的元素位置都会被重新排放。