04 字典、集合,你真的了解吗? 你好,我是景霄。

前面的课程,我们学习了Python中的列表和元组,了解了他们的基本操作和性能比较。这节课,我们再来学习两个同样很常见并且很有用的数据结构:字典(dict)和集合(set)。字典和集合在Python被广泛使用,并且性能进行了高度优化,其重要性不言而喻。

字典和集合基础

那究竟什么是字典,什么是集合呢?字典是一系列由键(key)和值(value)配对组成的元素的集合,在Python3.7+,字典被确定为有序(注意:在3.6中,字典有序是一个implementation detail,在3.7才正式成为语言特性,因此3.6中无法100%确保其有序性),而3.6之前是无序的,其长度大小可变,元素可以任意地删减和改变。

相比于列表和元组,字典的性能更优,特别是对于查找、添加和删除操作,字典都能在常数时间复杂度内完成。

而集合和字典基本相同,唯一的区别,就是集合没有键和值的配对,是一系列无序的、唯一的元素组合。

首先我们来看字典和集合的创建,通常有下面这几种方式: d1 = {‘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

这里注意,Python中字典和集合,无论是键还是值,都可以是混合类型。比如下面这个例子,我创建了一个元素为

1 ,

‘hello’ ,

5.0 的集合:

s = {1, ‘hello’, 5.0}

再来看元素访问的问题。字典访问可以直接索引键,如果不存在,就会抛出异常:

d = {‘name’: ‘jason’, ‘age’: 20} d[‘name’] ‘jason’ d[‘location’] Traceback (most recent call last): File “", line 1, in KeyError: 'location'

也可以使用get(key, default)函数来进行索引。如果键不存在,调用get()函数可以返回一个默认值。比如下面这个示例,返回了

‘null’ 。

d = {‘name’: ‘jason’, ‘age’: 20} d.get(‘name’) ‘jason’ d.get(‘location’, ‘null’) ‘null’

说完了字典的访问,我们再来看集合。

首先我要强调的是,集合并不支持索引操作,因为集合本质上是一个哈希表,和列表不一样。所以,下面这样的操作是错误的,Python会抛出异常: s = {1, 2, 3} s[0] Traceback (most recent call last): File “", line 1, in TypeError: 'set' object does not support indexing

想要判断一个元素在不在字典或集合内,我们可以用value in dict/set 来判断。

s = {1, 2, 3} 1 in s True 10 in s False d = {‘name’: ‘jason’, ‘age’: 20} ‘name’ in d True ‘location’ in d False

当然,除了创建和访问,字典和集合也同样支持增加、删除、更新等操作。

d = {‘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()操作是删除集合中最后一个元素,可是集合本身是无序的,你无法知道会删除哪个元素,因此这个操作得谨慎使用。

实际应用中,很多情况下,我们需要对字典或集合进行排序,比如,取出值最大的50对。

对于字典,我们通常会根据键或值,进行升序或降序排序: d = {‘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)]

这里返回了一个列表。列表中的每个元素,是由原字典的键和值组成的元组。

而对于集合,其排序和前面讲过的列表、元组很类似,直接调用sorted(set)即可,结果会返回一个排好序的列表。 s = {3, 4, 2, 1} sorted(s) /# 对集合的元素进行升序排序 [1, 2, 3, 4]

字典和集合性能

文章开头我就说到了,字典和集合是进行过性能高度优化的数据结构,特别是对于查找、添加和删除操作。那接下来,我们就来看看,它们在具体场景下的性能表现,以及与列表等其他数据结构的对比。

比如电商企业的后台,存储了每件产品的ID、名称和价格。现在的需求是,给定某件商品的ID,我们要找出其价格。

如果我们用列表来存储这些数据结构,并进行查找,相应的代码如下: def find_product_price(products, product_id): for id, price in products: if id == product_id: return price return None products = [ (143121312, 100), (432314553, 30), (32421912367, 150) ] print(‘The price of product 432314553 is {}’.format(find_product_price(products, 432314553))) /# 输出 The price of product 432314553 is 30

假设列表有n个元素,而查找的过程要遍历列表,那么时间复杂度就为O(n)。即使我们先对列表进行排序,然后使用二分查找,也会需要O(logn)的时间复杂度,更何况,列表的排序还需要O(nlogn)的时间。

但如果我们用字典来存储这些数据,那么查找就会非常便捷高效,只需O(1)的时间复杂度就可以完成。原因也很简单,刚刚提到过的,字典的内部组成是一张哈希表,你可以直接通过键的哈希值,找到其对应的值。 products = { 143121312: 100, 432314553: 30, 32421912367: 150 } print(‘The price of product 432314553 is {}’.format(products[432314553])) /# 输出 The price of product 432314553 is 30

类似的,现在需求变成,要找出这些商品有多少种不同的价格。我们还用同样的方法来比较一下。

如果还是选择使用列表,对应的代码如下,其中,A和B是两层循环。同样假设原始列表有n个元素,那么,在最差情况下,需要O(n^2)的时间复杂度。 /# list version def find_unique_price_using_list(products): unique_price_list = [] for _, price in products: /# A if price not in unique_price_list: /#B unique_price_list.append(price) return len(unique_price_list) products = [ (143121312, 100), (432314553, 30), (32421912367, 150), (937153201, 30) ] print(‘number of unique price is: {}’.format(find_unique_price_using_list(products))) /# 输出 number of unique price is: 3

但如果我们选择使用集合这个数据结构,由于集合是高度优化的哈希表,里面元素不能重复,并且其添加和查找操作只需O(1)的复杂度,那么,总的时间复杂度就只有O(n)。

/# set version def find_unique_price_using_set(products): unique_price_set = set() for _, price in products: unique_price_set.add(price) return len(unique_price_set) products = [ (143121312, 100), (432314553, 30), (32421912367, 150), (937153201, 30) ] print(‘number of unique price is: {}’.format(find_unique_price_using_set(products))) /# 输出 number of unique price is: 3

可能你对这些时间复杂度没有直观的认识,我可以举一个实际工作场景中的例子,让你来感受一下。

下面的代码,初始化了含有100,000个元素的产品,并分别计算了使用列表和集合来统计产品价格数量的运行时间: import time id = [x for x in range(0, 100000)] price = [x for x in range(200000, 300000)] products = list(zip(id, price)) /# 计算列表版本的时间 start_using_list = time.perf_counter() find_unique_price_using_list(products) end_using_list = time.perf_counter() print(“time elapse using list: {}”.format(end_using_list - start_using_list)) /#/# 输出 time elapse using list: 41.61519479751587 /# 计算集合版本的时间 start_using_set = time.perf_counter() find_unique_price_using_set(products) end_using_set = time.perf_counter() print(“time elapse using set: {}”.format(end_using_set - start_using_set)) /# 输出 time elapse using set: 0.008238077163696289

你可以看到,仅仅十万的数据量,两者的速度差异就如此之大。事实上,大型企业的后台数据往往有上亿乃至十亿数量级,如果使用了不合适的数据结构,就很容易造成服务器的崩溃,不但影响用户体验,并且会给公司带来巨大的财产损失。

字典和集合的工作原理

我们通过举例以及与列表的对比,看到了字典和集合操作的高效性。不过,字典和集合为什么能够如此高效,特别是查找、插入和删除操作?

这当然和字典、集合内部的数据结构密不可分。不同于其他数据结构,字典和集合的内部结构都是一张哈希表。

  • 对于字典而言,这张表存储了哈希值(hash)、键和值这3个元素。
  • 而对集合来说,区别就是哈希表内没有键和值的配对,只有单一的元素了。

我们来看,老版本Python的哈希表结构如下所示: –+——————————-+ | 哈希值(hash) 键(key) 值(value) –+——————————-+ 0 | hash0 key0 value0 –+——————————-+ 1 | hash1 key1 value1 –+——————————-+ 2 | hash2 key2 value2 –+——————————-+ . | … +_____________+

不难想象,随着哈希表的扩张,它会变得越来越稀疏。举个例子,比如我有这样一个字典:

{‘name’: ‘mike’, ‘dob’: ‘1999-01-01’, ‘gender’: ‘male’}

那么它会存储为类似下面的形式:

entries = [ [’–’, ‘–’, ‘–’] [-230273521, ‘dob’, ‘1999-01-01’], [’–’, ‘–’, ‘–’], [’–’, ‘–’, ‘–’], [1231236123, ‘name’, ‘mike’], [’–’, ‘–’, ‘–’], [9371539127, ‘gender’, ‘male’] ]

这样的设计结构显然非常浪费存储空间。为了提高存储空间的利用率,现在的哈希表除了字典本身的结构,会把索引和哈希值、键、值单独分开,也就是下面这样新的结构:

Indices —————————————————- None index None None index None index … —————————————————- Entries ——————– hash0 key0 value0 ——————— hash1 key1 value1 ——————— hash2 key2 value2 ——————— … ———————

那么,刚刚的这个例子,在新的哈希表结构下的存储形式,就会变成下面这样:

indices = [None, 1, None, None, 0, None, 2] entries = [ [1231236123, ‘name’, ‘mike’], [-230273521, ‘dob’, ‘1999-01-01’], [9371539127, ‘gender’, ‘male’] ]

我们可以很清晰地看到,空间利用率得到很大的提高。

清楚了具体的设计结构,我们接着来看这几个操作的工作原理。

插入操作

每次向字典或集合插入一个元素时,Python会首先计算键的哈希值(hash(key)),再和 mask = PyDicMinSize - 1做与操作,计算这个元素应该插入哈希表的位置index = hash(key) & mask。如果哈希表中此位置是空的,那么这个元素就会被插入其中。

而如果此位置已被占用,Python便会比较两个元素的哈希值和键是否相等。

  • 若两者都相等,则表明这个元素已经存在,如果值不同,则更新值。
  • 若两者中有一个不相等,这种情况我们通常称为哈希冲突(hash collision),意思是两个元素的键不相等,但是哈希值相等。这种情况下,Python便会继续寻找表中空余的位置,直到找到位置为止。

值得一提的是,通常来说,遇到这种情况,最简单的方式是线性寻找,即从这个位置开始,挨个往后寻找空位。当然,Python内部对此进行了优化(这一点无需深入了解,你有兴趣可以查看源码,我就不再赘述),让这个步骤更加高效。

查找操作

和前面的插入操作类似,Python会根据哈希值,找到其应该处于的位置;然后,比较哈希表这个位置中元素的哈希值和键,与需要查找的元素是否相等。如果相等,则直接返回;如果不等,则继续查找,直到找到空位或者抛出异常为止。

删除操作

对于删除操作,Python会暂时对这个位置的元素,赋于一个特殊的值,等到重新调整哈希表的大小时,再将其删除。

不难理解,哈希冲突的发生,往往会降低字典和集合操作的速度。因此,为了保证其高效性,字典和集合内的哈希表,通常会保证其至少留有1/3的剩余空间。随着元素的不停插入,当剩余空间小于1/3时,Python会重新获取更大的内存空间,扩充哈希表。不过,这种情况下,表内所有的元素位置都会被重新排放。

虽然哈希冲突和哈希表大小的调整,都会导致速度减缓,但是这种情况发生的次数极少。所以,平均情况下,这仍能保证插入、查找和删除的时间复杂度为O(1)。

总结

这节课,我们一起学习了字典和集合的基本操作,并对它们的高性能和内部存储结构进行了讲解。

字典在Python3.7+是有序的数据结构,而集合是无序的,其内部的哈希表存储结构,保证了其查找、插入、删除操作的高效性。所以,字典和集合通常运用在对元素的高效查找、去重等场景。

思考题

1. 下面初始化字典的方式,哪一种更高效? /# Option A d = {‘name’: ‘jason’, ‘age’: 20, ‘gender’: ‘male’} /# Option B d = dict({‘name’: ‘jason’, ‘age’: 20, ‘gender’: ‘male’})

2. 字典的键可以是一个列表吗?下面这段代码中,字典的初始化是否正确呢?如果不正确,可以说出你的原因吗?

d = {‘name’: ‘jason’, [‘education’]: [‘Tsinghua University’, ‘Stanford University’]}

欢迎留言和我分享,也欢迎你把这篇文章分享给你的同事、朋友。

参考资料

https://learn.lianglianglee.com/%e4%b8%93%e6%a0%8f/Python%e6%a0%b8%e5%bf%83%e6%8a%80%e6%9c%af%e4%b8%8e%e5%ae%9e%e6%88%98/04%20%e5%ad%97%e5%85%b8%e3%80%81%e9%9b%86%e5%90%88%ef%bc%8c%e4%bd%a0%e7%9c%9f%e7%9a%84%e4%ba%86%e8%a7%a3%e5%90%97%ef%bc%9f.md