Python核心技术与实战
景霄
Facebook资深工程师
立即订阅
12643 人已学习
课程目录
已完结 46 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从工程的角度深入理解Python
免费
基础篇 (14讲)
01 | 如何逐步突破,成为Python高手?
02 | Jupyter Notebook为什么是现代Python的必学技术?
03 | 列表和元组,到底用哪一个?
04 | 字典、集合,你真的了解吗?
05 | 深入浅出字符串
06 | Python “黑箱”:输入与输出
07 | 修炼基本功:条件与循环
08 | 异常处理:如何提高程序的稳定性?
09 | 不可或缺的自定义函数
10 | 简约不简单的匿名函数
11 | 面向对象(上):从生活中的类比说起
12 | 面向对象(下):如何实现一个搜索引擎?
13 | 搭建积木:Python 模块化
14 | 答疑(一):列表和元组的内部实现是怎样的?
进阶篇 (11讲)
15 | Python对象的比较、拷贝
16 | 值传递,引用传递or其他,Python里参数是如何传递的?
17 | 强大的装饰器
18 | metaclass,是潘多拉魔盒还是阿拉丁神灯?
19 | 深入理解迭代器和生成器
20 | 揭秘 Python 协程
21 | Python并发编程之Futures
22 | 并发编程之Asyncio
23 | 你真的懂Python GIL(全局解释器锁)吗?
24 | 带你解析 Python 垃圾回收机制
25 | 答疑(二):GIL与多线程是什么关系呢?
规范篇 (7讲)
26 | 活都来不及干了,还有空注意代码风格?!
27 | 学会合理分解代码,提高代码可读性
28 | 如何合理利用assert?
29 | 巧用上下文管理器和With语句精简代码
30 | 真的有必要写单元测试吗?
31 | pdb & cProfile:调试和性能分析的法宝
32 | 答疑(三):如何选择合适的异常处理方式?
量化交易实战篇 (8讲)
33 | 带你初探量化世界
免费
34 | RESTful & Socket: 搭建交易执行层核心
35 | RESTful & Socket: 行情数据对接和抓取
36 | Pandas & Numpy: 策略与回测系统
免费
37 | Kafka & ZMQ:自动化交易流水线
38 | MySQL:日志和数据存储系统
39 | Django:搭建监控平台
40 | 总结:Python中的数据结构与算法全景
技术见闻与分享 (4讲)
41 | 硅谷一线互联网公司的工作体验
42 | 细数技术研发的注意事项
加餐 | 带你上手SWIG:一份清晰好用的SWIG编程实践指南
43 | Q&A:聊一聊职业发展和选择
结束语 (1讲)
结束语 | 技术之外的几点成长建议
Python核心技术与实战
登录|注册

04 | 字典、集合,你真的了解吗?

景霄 2019-05-17

你好,我是景霄。

前面的课程,我们学习了 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的集合:

© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Python核心技术与实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(100)

  • pyhhou
    思考题 1:
    第一种方法更快,原因感觉上是和之前一样,就是不需要去调用相关的函数,而且像老师说的那样 {} 应该是关键字,内部会去直接调用底层C写好的代码

    思考题 2:
    用列表作为 Key 在这里是不被允许的,因为列表是一个动态变化的数据结构,字典当中的 key 要求是不可变的,原因也很好理解,key 首先是不重复的,如果 Key 是可以变化的话,那么随着 Key 的变化,这里就有可能就会有重复的 Key,那么这就和字典的定义相违背;如果把这里的列表换成之前我们讲过的元组是可以的,因为元组不可变

    作者回复: 正解

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

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

    2019-05-17
    1
    31
  • Python高效编程
    Python 3.7 以后插入有序变为字典的特性。构造新字典的方式:
    1. double star
    >>> d1 = {'name': 'jason', 'age': 20, 'gender': 'male'}
    >>> d2 = {'hobby': 'swim', **d1}
    2. update 函数:
    >>> d3 = {'hobby': 'swim'}
    >>> d3.update(d1)
    我们可以看到这两种方式得到的字典是满足插入有序的:
    >>> d3
    {'hobby': 'swim', 'name': 'jason', 'age': 20, 'gender': 'male'}
    在我的电脑上 第一种方式的性能要好一些。
    double star:
    229 ns ± 22.8 ns per loop
    update:
    337 ns ± 49.7 ns per loop
    2019-05-17
    20
  • 随风の
    文中提到的新的哈希表结构有点不太明白 None 1 None None 0 None 2 是什么意思? index是索引的话 为什么中间会出现两个None

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

    2019-05-17
    18
  • charily
    老师,你好!有几个让我困惑的地方想跟您确认一下,问题有点多,希望不吝赐教!
    1. 为了提高哈希表的空间利用率,于是使用了Indices、Entries结构分开存储(index)和(hashcode、key、value),这里的index是否就是Entries列表的下标?
    2、如果问题1成立,通过hash(key) & (PyDicMinSize - 1)计算出来的是否为Indices列表的下标?
    3、如果问题2成立,PyDicMinSize是什么?为什么要使用hashcode与(PyDicMinSize - 1)做与运算,相比起直接用hashcode作为Indices列表的下标会有什么好处?
    4、如果问题2成立,在往字典插入新元素的时候,通过hash(key) & mask计算出Indices的下标,如果Indices对应的元素位置值为None,则是否会将其值(index)修改为len(Entries),然后在Entries列表追加一行新的记录(hashcode,key,value)?
    5、如果问题2成立,在往字典插入新元素的时候,通过hash(key) & mask计算出Indices的下标,如果Indices对应的元素位置已经有值,则会跟Entries表中对应位置的key进行hash比较及相等比较来决定是进行value的更新处理还是hash冲突处理?
    2019-05-18
    5
    16
  • 许山山
    >>> dis.dis(lambda : dict())
      1 0 LOAD_GLOBAL 0 (dict)
                  3 CALL_FUNCTION 0 (0 positional, 0 keyword pair)
                  6 RETURN_VALUE

    >>> dis.dis(lambda : {})
      1 0 BUILD_MAP 0
                  3 RETURN_VALUE

    >>> %timeit dict()
    133 ns ± 2.95 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

    >>> %timeit {}
    74.6 ns ± 3.07 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

    {}, [], () 都比 dict(), list(), tuple() 初始化列表的性能要好,因为后者需要函数调用消耗了更多的时间。
    2019-05-17
    1
    10
  • 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
    1
    5
  • Ben
    1, 第一种更快, 反编译后, 第二种需要调用函数
    >>> import dis
    >>> def f1(): return {'1':1}
    ...
    >>> def f2(): return dict({'1':1})
    ...
    >>> dis.dis(f1)
      1 0 LOAD_CONST 1 ('1')
                  2 LOAD_CONST 2 (1)
                  4 BUILD_MAP 1
                  6 RETURN_VALUE
    >>> dis.dis(f2)
      1 0 LOAD_GLOBAL 0 (dict)
                  2 LOAD_CONST 1 ('1')
                  4 LOAD_CONST 2 (1)
                  6 BUILD_MAP 1
                  8 CALL_FUNCTION 1
                 10 RETURN_VALUE
    2. 不可以, 列表是可变的, 但是对hash表来说, 如果键值是可变的, 那么插入以及删除的位置都变成不确定的. 另外哈希冲突的概率也大大增加
    2019-06-20
    4
  • 许山山
    老师我明白了,(hash, key, val) 都是存在 entries 里面的,通过 indices[index] 找到 entry 再做比较就好了。
    2019-05-17
    4
  • 刘朋
    插入操作,
    mask = PyDicMinSize -1
    index = hash(key) & mask

    能否有个例子,想详细了解一下细节
    2019-05-17
    2
    4
  • farFlight
    老师好,在王争老师的数据结构课程中提到哈希表常与链表一起使用,譬如用来解决哈希冲突。请问python底层对字典和集合的实现是否也是这样的呢?

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

    2019-05-17
    4
  • 小狼
    s2 = Set([1, 2, 3])
    # Set 大写会报错:
    NameError: name 'Set' is not defined
    改成小写问题解决
    2019-05-17
    3
  • 鱼腐
    Indices:none | one | none | index | none | index 是什么意思?能补充讲解下吗

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

    2019-05-17
    3
  • 星文友
    --+-------------------------------+
      | 哈希值 (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
    2
  • William
    老师请问,key、hash值、indice三者的联系是啥? 一直以为hash(key)就是内存地址
    2019-05-24
    2
  • Danpier
    老师,对于集合插值有个疑问:
    s={1, 2.0}
    s.add(1.0)
    s
    # 输出
    {1, 2.0}
    上面这个示例,是不是因为1和1.0的哈希值相同,所以判定已存在元素,不插入。
    关于商品有多少种不同价格的时间复杂度也有疑问:
    第一个例子的时间复杂度是O(n^2),但我的理解是,最差的情况是每种商品价格不同。A层循环遍历时间复杂度是O(n),B层的时间复杂度由添加和遍历组成,添加的总时间复杂度是O(n),遍历时间复杂度是递增的:O(0+1+……+n-1),B层总的时间复杂度是O((n^2+n)/2),那list的时间复杂度不就是A+B:O((n^2+3n)/2)吗?怎么想都和两层for循环嵌套的时间复杂度不一样。
    第二个例子的时间复杂度是O(n),而我的理解是A层循环遍历时间复杂度是O(n),B层的添加查找的总时间复杂度是O(n),那set的时间复杂度不应该是A+B:O(2n)吗?
    不知道哪里理解出了问题,望老师指点。
    2019-05-18
    2
  • 趁早
    最后的例子很有代表性,举例很好
    2019-05-18
    2
  • Jon徐
    list indices就是哈希表,None表示该位置目前尚未被占用,索引的值即是在list entries中存储dict键值和哈希值的下标。
    作业中初始化dict,key不能使用可变类型吧,value可以使任意对象。

    作者回复: 回答的很好

    2019-05-17
    2
  • 静艺
    讲解得挺好,有深入讲,赞
    2019-08-08
    1
  • 山石尹口
    list做key的问题有点疑惑,即使list是可变的,它在内存中的地址是不变的,对地址是可以hash的吧?不然所有引用类型都没法做key了。当然,用引用类型做key不一定是好的做法,可能会带来混淆。
    2019-06-02
    1
收起评论
99+
返回
顶部