写点什么

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:311531

评论

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

欧拉与AI深度结合:操作系统升级带来全新智能体验

彭飞

Merlin Protocol,一个专业的比特币生态资产适配协议

TerpLayer

区块链

大数据之云平台的使用与总结 主赛道:技术人的 2023 总结

Echo_Wish

大数据 云平台 年度总结 2023 开天平台

图像处理AI软件推荐:Topaz Photo AI 激活直装版

胖墩儿不胖y

Mac软件 图像处理工具

拼多多ID取商品详情API:电商行业的秘密武器与实时数据获取的智慧之路

Noah

小红书商品详情API:电商助力

Noah

C 语言教程:数据类型和格式说明符

小万哥

c 程序员 软件 后端 开发

PWM 调光的线性降压 LED 恒流驱动器

芯动大师

INFINI Labs 产品更新 | Easysearch 新增快照搜索功能,Console 支持 OpenSearch 存储

极限实验室

console easysearch

为开发者服务,让梦想成为可能|孙文龙理事长发表专题演讲

开放原子开源基金会

Java 开源 程序员 开发者 算法

敏捷任务拆解、工作量评估和指派

laofo

Scrum 敏捷 敏捷开发 研发效能 持续交付

openEuler商业化进展可观:累计装机量超610万套,市场持续扩容

彭飞

微服务的学习与实践 主赛道:技术人的 2023 总结

Echo_Wish

微服务 云原生 年度总结 2023 技术总结

openEuler社区与9大海外开源基金会深入合作,构建全球开源新生态

彭飞

专业的磁盘管理工具:DiskCatalogMaker 中文激活版

胖墩儿不胖y

Mac软件 磁盘管理工具 磁盘清理管理

一文搞懂Android和嵌入式Linux开发差异点

巫山老妖

Cilium CNI深度指南

俞凡

Kubernetes 云原生 网络 通信

APIitem_get:你的淘宝商品详情搜索神器

技术冰糖葫芦

API 接口

开放原子云社区正式成立

开放原子开源基金会

Java 开源 程序员 开发者 算法

开放原子开源基金会与9个开源项目举行捐赠签约仪式

开放原子开源基金会

Java 开源 程序员 开发者 算法

开源漏洞共享平台及安全奖励计划正式发布

开放原子开源基金会

Java 开源 程序员 开发者 算法

Raw图像处理推荐 Capture One Pro 23中文最新版

胖墩儿不胖y

Mac软件 raw图像 raw图像处理工具

生成式AI给我们带来的影响

月下独酌

大模型

找不到想找的图片?半小时,帮你实现一个AI版“图片搜索引擎”

鹤涵

Redis 核心技术与实战 openai AIGC ChatGPT

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