写点什么

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

2019 年 9 月 30 日

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 年 9 月 30 日 14:31634

评论

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

微软商店报错:0x80131500

wood

几款Java开发者必备常用的工具,准点下班不在话下

华为云开发者社区

Java 工具 开发

安装Centos7时提示 /dev/root does not exits

wood

建议收藏,mybatis插件原理详解

田维常

mybatis

OpenKruise v0.7.0 版本发布:新增周期任务分发控制器

阿里巴巴云原生

阿里云 容器 开发者 运维 云原生

全部卸载office

wood

干货丨如何使用Redash连接DolphinDB数据源

DolphinDB

数据处理 时序数据库 DolphinDB 数据库开发 redash

等保数据备份和恢复关键点,这些你该知道!

华为云开发者社区

数据 容灾 恢复

PostgreSQL高可用:多主复制解决方案

PostgreSQLChina

数据库 postgresql 开源

不装鲁大师怎么查看自己主板型号

wood

一个服务器部署多个wordpress,500报错等等宝塔的设置

wood

flink 使用curl,通过RESTful api,上传和删除jar包

Geek_de9857

flink RESTful curl 上传jar 删除jar

Mysql中,1=1和 1=1=1 和 -1=-1 和 -1=-1=-1 和 5=5 和 5=5=5 有什么区别

Geek_de9857

MySQL sql 返回值 1=1=1 -1=1=1

架构师训练营第 13 周学习总结

netspecial

极客大学架构师训练营

90分钟10个手写案例,从源码底层给你讲解7种线程池创建方式

996小迁

Java 源码 架构 资料 笔记

LeetCode题解:127. 单词接龙,双向BFS,JavaScript,详细注释

Lee Chen

算法 LeetCode 前端进阶训练营

《O2O实战:他们是如何利用互联网的》.pdf

田维常

互联网

从阿里离职后人虚了,头也秃了,就剩这份Java性能优化的PDF了

Java架构追梦

Java 架构 面试 性能优化 并发

架构师 3 期 3 班 -week4- 作业

zbest

作业 week4

女朋友突然问我DNS是个啥....

乱敲代码

计算机网络 DNS DNS服务器

扩招1W人,字节跳动内部公开12月份Java岗71道面试题

比伯

Java 编程 架构 面试 程序人生

程序员因重复记录日志撑爆ELK被辞退!

Java架构师迁哥

从面试角度分析LinkedList源码

Java旅途

Java List 集合 linkedlist

forsage以太坊矩阵系统软件开发|forsage以太坊矩阵APP开发

开發I852946OIIO

系统开发

阿里华为等大厂如何处理数值精度/舍入/溢出问题

Java架构师迁哥

zh-cn:子主题-wordpress

wood

WordPress

The superclass "javax.servlet.http.HttpServlet" was not found on the Java Build Path

wood

eclipse

win10看不到局域网电脑,无法连接打印机

wood

PC端怎么更改iCloudDrive目录位置?

wood

wordpress后台的目录编辑页和标签页无法访问

wood

985研究生熬夜23天吃透845页架构宝典 终收割腾讯Java岗offer!再也不用怀疑人生了

比伯

Java 编程 架构 面试 程序人生

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