04 | 字典、集合，你真的了解吗？

景霄



该思维导图由 AI 生成，仅供参考

你好，我是景霄。
前面的课程，我们学习了 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的集合：

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

Python中的字典和集合是高效的数据结构，本文通过比较列表和字典/集合在查找、添加和删除操作上的性能差异，强调了字典和集合在实际应用中的重要性。文章详细介绍了字典和集合的内部存储结构，以及插入、查找和删除操作的工作原理。通过实际代码示例和性能测试，读者可以直观地了解字典和集合的优势，以及在大型数据场景下的巨大性能优势。总结来说，字典和集合的内部哈希表存储结构保证了其查找、插入、删除操作的高效性，通常运用在对元素的高效查找、去重等场景。文章内容简洁清晰，适合读者快速了解字典和集合的特点和优势。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《Python 核心技术与实战》，新⼈⾸单¥59

立即购买

登录后留言

全部留言(167)

最新
精选

pyhhou
思考题 1：第一种方法更快，原因感觉上是和之前一样，就是不需要去调用相关的函数，而且像老师说的那样 {} 应该是关键字，内部会去直接调用底层C写好的代码思考题 2: 用列表作为 Key 在这里是不被允许的，因为列表是一个动态变化的数据结构，字典当中的 key 要求是不可变的，原因也很好理解，key 首先是不重复的，如果 Key 是可以变化的话，那么随着 Key 的变化，这里就有可能就会有重复的 Key，那么这就和字典的定义相违背；如果把这里的列表换成之前我们讲过的元组是可以的，因为元组不可变
作者回复: 正解
2019-05-17
9
463
燕儿衔泥
1.直接｛｝的方式，更高效。可以使用dis分析其字节码 2.字典的键值，需要不可变，而列表是动态的，可变的。可以改为元组
作者回复: 使用dis分析其字节码很赞
2019-05-17
10
91
随风の
文中提到的新的哈希表结构有点不太明白 None 1 None None 0 None 2 是什么意思？ index是索引的话为什么中间会出现两个None
作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素，index表示有元素，并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了
2019-05-17

29
星文友
--+-------------------------------+ | 哈希值 (hash) 键 (key) 值 (value) --+-------------------------------+ 0 | hash0 key0 value0 --+-------------------------------+ 1 | hash1 key1 value1 --+-------------------------------+ 2 | hash2 key2 value2 --+-------------------------------+ . | ... __+_______________________________+ 第一种数据结构，如何可以o(1)的查找一个key？没有索引啊这篇文章感觉写的不好，例子没有讲透稀疏一定浪费吗，里面没有值的话能占用多少空间我理解耗费空间的应该是k v的存储吧
作者回复: 根据key计算hash值后直接就可以找到对应的value啊，所以是O(1)，他并不是列表需要遍历，他是哈希表稀疏肯定浪费空间啊，里面没有值也是会有一定的存储损耗的你自己去看看市面上Python教材里讲字典集合的，有几个能讲到像我这样深入。
2019-05-29
4
16
Hoo-Ah
1. 直接使用大括号更高效，避免了使用类生成实例其他不必要的操作； 2. 列表不可以作为key，因为列表是可变类型，可变类型不可hash。问题：为什么在旧哈希表中元素会越来越稀？
作者回复: 你比较一下旧哈希表和新哈希表的存储结构就会发现，旧哈希表的空间利用率很低，一个位置要同时分配哈希值，键和值的空间，但是新哈希表把indices和entries分开后，空间利用率大大提高。看文中的例子，这是旧哈希表存储示意图 entries = [ ['--', '--', '--'] [-230273521, 'dob', '1999-01-01'], ['--', '--', '--'], ['--', '--', '--'], [1231236123, 'name', 'mike'], ['--', '--', '--'], [9371539127, 'gender', 'male'] ] VS 新哈希表存储示意图： indices = [None, 1, None, None, 0, None, 2] entries = [ [1231236123, 'name', 'mike'], [-230273521, 'dob', '1999-01-01'], [9371539127, 'gender', 'male'] ] 你数一下两个版本中空着的元素的个数，就很清晰了。
2019-05-17
7
12
力维
内容挺好的，但好像有个小错误：关于查找价格的例子，列表查找并没有用到双重循环吧？A是循环，B只是判断语句，不构成循环。
作者回复: 语句“if x in list”虽然表面上是条件语句，但是内部是循环，因为判断一个元素在不在列表里，必须得遍历一遍，时间复杂度是O(n)
2019-11-14
3
10
Jon徐
list indices就是哈希表，None表示该位置目前尚未被占用，索引的值即是在list entries中存储dict键值和哈希值的下标。作业中初始化dict，key不能使用可变类型吧，value可以使任意对象。
作者回复: 回答的很好
2019-05-17

7
farFlight
老师好，在王争老师的数据结构课程中提到哈希表常与链表一起使用，譬如用来解决哈希冲突。请问python底层对字典和集合的实现是否也是这样的呢？
作者回复: 这个就是文中所说的线性寻找了，但是Python底层解决哈希冲突还有更好的方法，线性寻找是最简单的，但是不是最高效的
2019-05-17

7
天凉好个秋
不难想象，随着哈希表的扩张，它会变得越来越稀疏。后面例子中解释的原因没看懂，能详细说说吗？
作者回复: 哈希表为了保证其操作的有效性（查找，添加，删除等等），都会overallocate（保留至少1/3的剩余空间），但是很多空间其实都没有被利用，因此很稀疏
2019-05-17
2
5
鱼腐
Indices:none | one | none | index | none | index 是什么意思？能补充讲解下吗
作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素，index表示有元素，并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了
2019-05-17

4

收起评论