Python 核心技术与实战
景霄
Facebook 资深工程师
78765 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 47 讲
开篇词 (1讲)
Python 核心技术与实战
15
15
1.0x
00:00/00:00
登录|注册

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的集合:
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Python 核心技术与实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(165)

  • 最新
  • 精选
  • pyhhou
    思考题 1: 第一种方法更快,原因感觉上是和之前一样,就是不需要去调用相关的函数,而且像老师说的那样 {} 应该是关键字,内部会去直接调用底层C写好的代码 思考题 2: 用列表作为 Key 在这里是不被允许的,因为列表是一个动态变化的数据结构,字典当中的 key 要求是不可变的,原因也很好理解,key 首先是不重复的,如果 Key 是可以变化的话,那么随着 Key 的变化,这里就有可能就会有重复的 Key,那么这就和字典的定义相违背;如果把这里的列表换成之前我们讲过的元组是可以的,因为元组不可变

    作者回复: 正解

    9
    452
  • 燕儿衔泥
    1.直接{}的方式,更高效。可以使用dis分析其字节码 2.字典的键值,需要不可变,而列表是动态的,可变的。可以改为元组

    作者回复: 使用dis分析其字节码很赞

    9
    88
  • 随风の
    文中提到的新的哈希表结构有点不太明白 None 1 None None 0 None 2 是什么意思? index是索引的话 为什么中间会出现两个None

    作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素,index表示有元素,并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了

    26
  • 星文友
    --+-------------------------------+ | 哈希值 (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教材里讲字典集合的,有几个能讲到像我这样深入。

    4
    14
  • 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'] ] 你数一下两个版本中空着的元素的个数,就很清晰了。

    7
    12
  • 力维
    内容挺好的,但好像有个小错误:关于查找价格的例子,列表查找并没有用到双重循环吧?A是循环,B只是判断语句,不构成循环。

    作者回复: 语句“if x in list”虽然表面上是条件语句,但是内部是循环,因为判断一个元素在不在列表里,必须得遍历一遍,时间复杂度是O(n)

    3
    9
  • Jon徐
    list indices就是哈希表,None表示该位置目前尚未被占用,索引的值即是在list entries中存储dict键值和哈希值的下标。 作业中初始化dict,key不能使用可变类型吧,value可以使任意对象。

    作者回复: 回答的很好

    6
  • farFlight
    老师好,在王争老师的数据结构课程中提到哈希表常与链表一起使用,譬如用来解决哈希冲突。请问python底层对字典和集合的实现是否也是这样的呢?

    作者回复: 这个就是文中所说的线性寻找了,但是Python底层解决哈希冲突还有更好的方法,线性寻找是最简单的,但是不是最高效的

    6
  • 天凉好个秋
    不难想象,随着哈希表的扩张,它会变得越来越稀疏。 后面例子中解释的原因没看懂,能详细说说吗?

    作者回复: 哈希表为了保证其操作的有效性(查找,添加,删除等等),都会overallocate(保留至少1/3的剩余空间),但是很多空间其实都没有被利用,因此很稀疏

    2
    4
  • 鱼腐
    Indices:none | one | none | index | none | index 是什么意思?能补充讲解下吗

    作者回复: 这只是一种表示。None表示indices这个array上对应的位置没有元素,index表示有元素,并且对应entries这个array index位置上的元素。你看那个具体的例子就能看懂了

    4
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部