Fluent Python 笔记(四):字典和集合
发布网友
发布时间：2024-09-29 07:32
共1个回答
热心网友
时间：22小时前
Fluent Python 笔记（一）：数据模型
Fluent Python 笔记（二）：序列基础
Fluent Python 笔记（三）：高效操作序列
Fluent Python 笔记（四）：字典和集合
Fluent Python 笔记（五）：把函数当做对象
最近忙得团团转，更新进度缓慢。
本文将概述字典和集合的使用方法与底层实现。
字典（Dict）
字典是Python中最为核心的数据结构，广泛应用于程序中，并构成Python语言的基础。
模块命名空间、类和实例属性、函数的关键字参数等都是通过字典实现的。
字典被高度优化，其底层机制将在后续探讨。
字典构造示例
字典推导示例
灵活处理缺失键值的几种方法
为已知将频繁缺失键值的情况提供默认值，可使用defaultdict。
defaultdict工作原理
实例化defaultdict时提供default_factory，每次__getitem__传入不存在的key时，产生默认值。
字典的__missing__函数
__missing__函数仅在__getitem__调用时调用，产生默认值，其他函数无效。
自定义defaultdict示例
非str键转化为str进行查找
Python 3中查找效率高，尤其对于大字典，使用dict.keys()返回view效率极佳。
常用映射模块
collections模块中的defaultdict之外的常用映射类型
有序字典、计数映射、纯Python映射、自定义映射类型
不可变映射和映射proxy
集合（Set）
集合主要作用是去重
集合元素必须可哈希，set类型不可哈希，frozenset可哈希，可加入set中
集合构造方式
集合推导示例
字典及集合底层实现
字典内部使用哈希表，查找时间微不足道，无论大小，只要内存允许。
哈希表中的每个元素包含bucket，bucket中存储条目和值。
Python保持bucket空位率至少为1/3，当哈希表过满时重新构建。
查找字典时，使用哈希函数获取offset，遍历bucket。
插入和更新条目，查找空bucket时放入新item，找到符合key时覆盖原有值。
哈希表增长时，增加哈希值中用于offset的位数，降低碰撞率。
字典实用工作结论
对象满足可哈希条件
自定义__eq__方法时，必须实现__hash__，否则破坏哈希算法。
可变状态依赖的__eq__方法会抛出TypeError。
字典空间效率较低
替换dict为tuple减少内存使用
dict实现空间换时间
在Python 3中，字典view动态反应dict改变
总结：字典是Python中至关重要且应用广泛的结构，通常可作为模块内部结构的模拟。使用现成模块或约定俗成方法解决字典特殊需求，避免自行实现。集合和字典底层机制相似，早期版本的集合通过键值相同的字典实现，使用方法接近。
