“AI 技术+人才”如何成为企业增长新引擎?戳此了解>>> 了解详情
写点什么

Python 中常见的数据结构:字典、映射和散列表

  • 2019-09-30
  • 本文字数:2540 字

    阅读完需:约 8 分钟

Python中常见的数据结构:字典、映射和散列表

在 Python 中,字典是核心数据结构。字典可以存储任意数量的对象,每个对象都由唯一的字典键标识。


字典通常也被称为映射、散列表、查找表或关联数组。字典能够高效查找、插入和删除任何与给定键关联的对象。


这在现实中意味着什么呢?字典对象相当于现实世界中的电话簿。


电话簿有助于快速检索与给定键(人名)相关联的信息(电话号码)。因此不必为了查找某人的号码而浏览整本电话簿,根据人名基本上就能直接跳到需要查找的相关信息。


若想研究以何种方式组织信息才有利于快速检索,上述类比就不那么贴切了。但基本性能特征相同,即字典能够用来快速查找与给定键相关的信息。


总之,字典是计算机科学中最常用且最重要的数据结构之一。


那么 Python 如何处理字典呢?


我们来看看 Python 及其标准库中可用的字典实现。

dict——首选字典实现

由于字典非常重要,因此 Python 直接在语言核心中实现了一个稳健的字典 1:dict 数据类型 2。


1 为了与其他资料统一,这里将不区分中文语境下的 dict(字典)和“字典类型的数据结构”,统称为“字典”。——译者注


2 详见 Python 文档:“Mapping Types — dict”。


Python 还提供了一些有用的“语法糖”来处理程序中的字典。例如,用花括号字典表达式语法和字典解析式能够方便地创建新的字典对象:


phonebook = {    'bob': 7387,    'alice': 3719,    'jack': 7052,}
squares = {x: x * x for x in range(6)}
>>> phonebook['alice']3719
>>> squares{0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}
复制代码


关于哪些对象可以作为字典键,有一些限制。


Python 的字典由可散列类型 3 的键来索引。可散列对象具有在其生命周期中永远不会改变的散列值(参见__hash__),并且可以与其他对象进行比较(参见__eq__)。另外,相等的可散列对象,其散列值必然相同。


像字符串和数这样的不可变类型是可散列的,它们可以很好地用作字典键。元组对象也可以用作字典键,但这些元组本身必须只包含可散列类型。


Python 的内置字典实现可以应对大多数情况。字典是高度优化的,并且是 Python 语言的基石,例如栈帧中的类属性和变量都存储在字典中。


Python 字典基于经过充分测试和精心调整过的散列表实现,提供了符合期望的性能特征。一般情况下,用于查找、插入、更新和删除操作的时间复杂度都为 O(1)。


大部分情况下,应该使用 Python 自带的标准字典实现。但是也存在专门的第三方字典实现,例如跳跃表或基于 B 树的字典。


除了通用的 dict 对象外,Python 的标准库还包含许多特殊的字典实现。它们都基于内置的字典类,基本性能特征相同,但添加了其他一些便利特性。


下面来逐个了解一下。

collections.OrderedDict——能记住键的插入顺序

collections.OrderedDict 是特殊的 dict 子类,该类型会记录添加到其中的键的插入顺序。


尽管在 CPython 3.6 及更高版本中,标准的字典实现也能保留键的插入顺序,但这只是 CPython 实现的一个副作用,直到 Python 3.7 才将这种特性固定下来了。因此,如果在自己的工作中很需要用到键顺序,最好明确使用 OrderedDict 类。


顺便说一句,OrderedDict 不是内置的核心语言部分,因此必须从标准库中的 collections 模块导入。


>>> import collections>>> d = collections.OrderedDict(one=1, two=2, three=3)
>>> dOrderedDict([('one', 1), ('two', 2), ('three', 3)])
>>> d['four'] = 4>>> dOrderedDict([('one', 1), ('two', 2), ('three', 3), ('four', 4)])
>>> d.keys()odict_keys(['one', 'two', 'three', 'four'])
复制代码

collections.defaultdict——为缺失的键返回默认值

defaultdict 是另一个 dict 子类,其构造函数接受一个可调用对象,查找时如果找不到给定的键,就返回这个可调用对象。


与使用 get()方法或在普通字典中捕获 KeyError 异常相比,这种方式的代码较少,并能清晰地表达出程序员的意图。



>>> from collections import defaultdict>>> dd = defaultdict(list)
# 访问缺失的键就会用默认工厂方法创建它并将其初始化# 在本例中工厂方法为list():>>> dd['dogs'].append('Rufus')>>> dd['dogs'].append('Kathrin')>>> dd['dogs'].append('Mr Sniffles')
>>> dd['dogs']['Rufus', 'Kathrin', 'Mr Sniffles']
复制代码

collections.ChainMap——搜索多个字典

collections.ChainMap 数据结构将多个字典分组到一个映射中 8,在查找时逐个搜索底层映射,直到找到一个符合条件的键。对 ChainMap 进行插入、更新和删除操作,只会作用于其中的第一个字典。


>>> from collections import ChainMap>>> dict1 = {'one': 1, 'two': 2}>>> dict2 = {'three': 3, 'four': 4}>>> chain = ChainMap(dict1, dict2)
>>> chainChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})
# ChainMap在内部从左到右逐个搜索,# 直到找到对应的键或全部搜索完毕:>>> chain['three']3>>> chain['one']1>>> chain['missing']KeyError: 'missing'
复制代码

types.MappingProxyType——用于创建只读字典

MappingProxyType 封装了标准的字典,为封装的字典数据提供只读视图。该类添加自 Python 3.3,用来创建字典不可变的代理版本。


举例来说,如果希望返回一个字典来表示类或模块的内部状态,同时禁止向该对象写入内容,此时 MappingProxyType 就能派上用场。使用 MappingProxyType 无须创建完整的字典副本。


>>> from types import MappingProxyType>>> writable = {'one': 1, 'two': 2}>>> read_only = MappingProxyType(writable)
# 代理是只读的:>>> read_only['one']1>>> read_only['one'] = 23TypeError:"'mappingproxy' object does not support item assignment"
# 更新原字典也会影响到代理:>>> writable['one'] = 42>>> read_onlymappingproxy({'one': 42, 'two': 2})
复制代码

小结:Python 中的字典

本节列出的所有 Python 字典实现都是内置于 Python 标准库中的有效实现。


一般情况下,建议在自己的程序中使用内置的 dict 数据类型。这是优化过的散列表实现,功能多且已被直接内置到了核心语言中。


如果你有内置 dict 无法满足的特殊需求,那么建议使用本节列出的其他数据类型。


虽然前面列出的其他字典实现均可用,但大多数情况下都应该使用 Python 内置的标准 dict,这样其他开发者在维护你的代码时就会轻松一点。


本文内容来自作者图书作品《深入理解 Python 特性》,点击购买


2019-09-30 14:311321

评论

发布
暂无评论
发现更多内容

这本现代魔法原理指南,把计算机体系掰开揉碎讲清楚了

Zilliz

编码

和12岁小同志搞创客开发:手撕代码,Arduino IDE 软件下载和环境搭建

不脱发的程序猿

少儿编程 智能硬件 创客开发 Arduino

全是精华!阿里最新出品的“SpringCloud架构笔记” GitHub已爆火

Java 程序员 后端

内卷严重!看看这些java核心资料,提高竞争力,争做拍死别人的后浪

Java 程序员 后端

先知道怎么手写一个分页查询,再去使用PageHelper吧

Java 程序员 后端

分布式服务下,消息中间件改造

Java 程序员 后端

关于Maven,这几个一定要会的知识点,你真的了解吗?

Java 程序员 后端

公司用算法考核程序员,与绩效挂钩,成绩太差将面临淘汰?

Java 程序员 后端

和12岁小同志搞创客开发:如何驱动 12864 OLED液晶显示屏?

不脱发的程序猿

少儿编程 智能硬件 创客开发 12864 OLED液晶显示屏

全新演绎!美团内部疯传Spring Boot速成手册也太香了

Java 程序员 后端

全网最热Vue入门教程你不看就吃亏了哦

Java 程序员 后端

全链路压测必备基础组件之线程上下文管理之“三剑客”

Java 程序员 后端

关于Spring注解容器配置的那些事,掌握这几点,不再难!

Java 程序员 后端

关于电商秒杀系统中防超卖、以及高性能下单的处理方案简述

Java 程序员 后端

活用向量数据库,普通散户也能找到潜力股!

Zilliz

数据库 Milvus 股票

Python Qt GUI设计:窗口布局管理方法【基础】(基础篇—5)

不脱发的程序猿

Python qt GUI设计 Qt Designer 窗口布局方式

全新演绎!美团内部疯传Spring Boot速成手册也太香了(1)

Java 程序员 后端

全网最全Spring面试题之基础篇整理总结(共69题,附超详细解答)

Java 程序员 后端

全网最新最全面Java程序员面试清单(12专题5000解析)

Java 程序员 后端

Python Qt GUI设计:Python调用UI文件的两种方法(基础篇—3)

不脱发的程序猿

Python qt PyQt 调用UI文件 上位机开发

全网首发!撸了谷歌大神写的Spring源码笔记后,感觉之前读的都是渣渣

Java 程序员 后端

关于计算机面试重难点 之 操作系统,字节架构师有话说

Java 程序员 后端

和12岁小同志搞创客开发:手撕代码,点亮LED灯

不脱发的程序猿

少儿编程 智能硬件 创客开发 Arduino

入秋的第一篇数据结构算法:看看归并与快排的风采

Java 程序员 后端

全文检索工具solr:第一章:理论知识

Java 程序员 后端

ajax跨域问题

加里都好

JavaScript ajax HTTP

几款常见接口管理平台对比

Java 程序员 后端

先到先得!价值百万的的ELk+Lucene笔记,技术点拉满

Java 程序员 后端

冷门的 Java 应用程序安全沙箱机制了解一下

Java 程序员 后端

凭借着这份Spring面试题,我拿到了阿里,字节跳动美团的offer!

Java 程序员 后端

八年CRUD,疫情备战三个月,三面头条、四面阿里拿offer面经分享

Java 程序员 后端

Python中常见的数据结构:字典、映射和散列表_编程语言_Dan Bader_InfoQ精选文章