《Fluent Python》CH.03_数据结构-字典和集合 读书笔记 (散列表、字典、集合)

本章内容的大纲如下:

• 常见的字典方法
• 如何处理查找不到的键
• 标准库中 dict 类型的变种
• set 和 frozenset 类型
• 散列表的工作原理
• 散列表带来的潜在影响（什么样的数据类型可作为键、不可预知的 顺序，等等）

小结

• 与Jdk8的雷同之处， jdk8的map基本等价于dict的构造，查询、冲突、新增等操作基本都符合散列表的结构，扩容结构升级方面1/3——jdk8是75%原则（膨胀系数）
• 转换文件的命令 jupyter nbconvert --to markdown E:PycharmProjectsTianChiProject 0_山枫叶纷飞competitions 13_fluent_pythonCH.03_数据结构-字典和集合.ipynb

3.1 泛映射类型

collections.abc 模块中有 Mapping 和 MutableMapping 这两个抽象 基类，它们的作用是为 dict 和其他类似的类型定义形式接口

图 3-1：collections.abc 中的 MutableMapping 和它的超类的 UML 类图（箭头从子类指向超类，抽象类和抽象方法的名称以斜体 显示） 然而，非抽象映射类型一般不会直接继承这些抽象基类，它们会直接对 dict 或是 collections.User.Dict 进行扩展。

这些抽象基类的主要 作用是作为形式化的文档，它们定义了构建一个映射类型所需要的最基 本的接口。然后它们还可以跟 isinstance 一起被用来判定某个数据是 不是广义上的映射类型：

import collections
my_dict = {}
isinstance(my_dict, collections.abc.Mapping)

True

isinstance(my_dict, collections.abc.MutableMapping)

True

什么是可散列的数据类型

• dict中的元素必须是可以散列的元素，即只有可散列的数据类型才能用作这些映射里的键（只有键有 这个要求，值并不需要是可散列的数据类型）。
• 可散列类型的定义:
  • 如果一个对象是可散列的，那么在这个对象的生命周期中，它的散列值是不变的，而且这个对象需要实现 hash() 方 法。
  • 另外可散列对象还要有 eq() 方法，这样才能跟其他键做比较。
  • 如果两个可散列对象是相等的，那么它们的散列值一定是一样的；反之，则不成立。
• 符合可散列类型的数据结构：
  • 原子不可变类型（str、bytes、数值类型）都是可散列的类型，frozenset 也是可散列的，因为根据其定义，frozenset 里 只能容纳可散列类型。
  • 是不可变序列的元组 &&（当且仅当其中的所有元素是可以散列的）
  • 数组不是可以散列的，没有实现hash
  • 对象：如果一个对象实现了 eq 方法，并且在方法中用到了这 个对象的内部状态的话，那么只有当所有这些内部状态都是不可变 的情况下，这个对象才是可散列的。

示例数组的hash:

tt1 = (1, 2, (30, 40))
hash(tt1)

8027212646858338501

tt2 = (1, 2, [30, 40])
hash(tt2)

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-7-902044673c2b> in <module>
      1 tt2 = (1, 2, [30, 40])
----> 2 hash(tt2)
      3 


TypeError: unhashable type: 'list'

3.2 字典推导

列表推导和生成器表达式的概念就移植到了字典 上，从而有了字典推导（后面还会看到集合推导）。

字典推导 （dictcomp）可以从任何以键值对作为元素的可迭代对象中构建出字典。

dictcomp形式:

• {K: V for K, V in MAP [加其他的if判断等条件]}

示例 3-1 就展示了利用字典推导可以把一个装满元组的列表变成两个不同的字典。

DIAL_CODES = [(1,'A'), (2, 'B'), (3, 'C')]
country_code = {country:code for code,country in DIAL_CODES}
country_code

{'A': 1, 'B': 2, 'C': 3}

{code:country for country, code in country_code.items() if code%2!=0}

{1: 'A', 3: 'C'}

3.3 字典常见的映射方法

映射类型的方法其实很丰富。表 3-1 为我们展示了 dict、defaultdict 和 OrderedDict 的常见方法，后面两个数据类型 是 dict 的变种，位于 collections 模块内。

常用API:

• clear()移除所有元素
• contains(k)
• delitem(k)，del d[k]，移除键为 k 的元素
• get(k, [default]) • • • 没有键 k，则返回 None 或者 default
• items() • • • 返回 d 里所有的键值对

update ‘鸭子函数’

• update(m, [**kargs]) • • • m 可以是映射或者键值对迭代 器，用来更新 d 里对应的条目。
  • update 方法处理参数 m 的方式，是典型的“鸭子类 型”。函数首先检查 m 是否有 keys 方法，如果有，那么 update 函数就 把它当作映射对象来处理。否则，函数会退一步，转而把 m 当作包含了 键值对 (key, value) 元素的迭代器。Python 里大多数映射类型的构造 方法都采用了类似的逻辑，因此你既可以用一个映射对象来新建一个映 射对象，也可以用包含 (key, value) 元素的可迭代对象来初始化一个 映射对象

### 用setdefault处理找不到的键

my_dict = {}
my_dict.setdefault('A', []).append('P23')
my_dict

{'A': ['P23']}

# 等价的写法
my_dict = {}
if 'A' not in my_dict.keys():
    my_dict['A'] = []

my_dict['A'].append('P23')
my_dict

{'A': ['P23']}

3.4 映射的弹性键查询

• 一个是通过 defaultdict 这个类型而不是普通的 dict
• 另一个 是给自己定义一个 dict 的子类，然后在子类中实现 __missing__ 方 法

3.4.1 defaultdict：处理找不到的键的一个选择

用法:

• defaultdict 里的 default_factory 只会在 __getitem__ 里被调用，在其他的方法里完全不会发挥作用。比 如，dd 是个 defaultdict，k 是个找不到的键， dd[k] 这个表达 式会调用 default_factory 创造某个默认值，而 dd.get(k) 则会 返回 None。

#### 创建一个从单词到其出现情况的映射
import re
import collections

words_file = """
A B C  D

E f g"""
WORD_RE = re.compile(r'w+')

index = collections.defaultdict(list)
for match in WORD_RE.finditer(words_file):
    word = match.group()
    column_no = match.start()+1
    location = (0, column_no)
    index[word].append(location)
for word in sorted(index, key=str.upper):
    print(word, index[word])

A [(0, 2)]
B [(0, 4)]
C [(0, 6)]
D [(0, 9)]
E [(0, 12)]
f [(0, 14)]
g [(0, 16)]

3.4.2 特殊方法__missing__

• 所有的映射类型在处理找不到的键的时候，都会牵扯到 __missing__ 方法。
• __missing__ 方法只会被 __getitem__ 调用（比如在表达 式 d[k] 中）。提供 __missing__ 方法对 get 或者 __contains__（in 运算符会用到这个方法）这些方法的使用没有 影响。

示例 3-7 重写一个missing的dict

class missing_dict(dict):
    def __missing__(self, key):
        return 'None' if key is None else str(key)+'2333'

my_dict = missing_dict()
my_dict['2333']

'23332333'

3.5 字典的变种

collections.OrderedDict

• 在添加键的时候会保持顺序，因此键的迭代次序总是一致 的
• 类似于Java的LinkedSet
• OrderedDict 的 popitem 方法默认删除并返回的是字典里的最后 一个元素，但是如果像 my_odict.popitem(last=False) 这样调用 它，那么它删除并返回第一个被添加进去的元素。

collections.ChainMap

• 该类型可以容纳数个不同的映射对象，然后在进行键查找操作的时 候，这些对象会被当作一个整体被逐个查找，直到键被找到为止。

collections.Counter

这个映射类型会给键准备一个整数计数器。每次更新一个键的时候 都会增加这个计数器。

下面的小例子利用 Counter 来计算单词中各个字母出现的次数：

ct = collections.Counter('andffffdfg')
ct

Counter({'a': 1, 'n': 1, 'd': 2, 'f': 5, 'g': 1})

ct.update('adfrwef')
ct

Counter({'a': 2, 'n': 1, 'd': 3, 'f': 7, 'g': 1, 'r': 1, 'w': 1, 'e': 1})

print('most_common([n]) 会按照次 序返回映射里最常见的 n 个键和它们的计数')
ct.most_common(2)

most_common([n]) 会按照次 序返回映射里最常见的 n 个键和它们的计数





[('f', 7), ('d', 3)]

colllections.UserDict

这个类其实就是把标准 dict 用纯 Python 又实现了一遍。

需要开发人员自己继承实现.

3.6 子类化UserDict

好处:

• 子类不用改写 get 方法，它的表现跟 __getitem__ 一致

3.7 不可变映射类型

• 标准库里所有的映射类型都是可变的
• 但是从 Python 3.3 开始，types 模块中引入了一个封装类名叫 MappingProxyType。如果给这个类一个映射，它会返回一个只读的映 射视图。虽然是个只读视图，但是它是动态的；改变原有的映射，可以达到修改的效果。

### 示例 3-9 用 MappingProxyType 来获取字典的只读实例 mappingproxy
from types import MappingProxyType
d_origin_mapping = {1: 'A'}
d_proxy = MappingProxyType(d_origin_mapping)
d_proxy

mappingproxy({1: 'A'})

d_proxy[1]

'A'

d_origin_mapping[2] = 'B'
d_proxy

mappingproxy({1: 'A', 2: 'B'})

3.8 集合论

• set 类型本身是不可散列的
• frozenset是可以散列的 (可以放进set中作为元素)
• 除了保证唯一性，集合还实现了很多基础的中缀运算符
  • a | b 返回的是它们的合集
  • a & b 得到的是交集，等同于intersection
  • a - b 得到的是差集

ft = frozenset([1,2,3])
print('不可执行add等变更操作~')
ft.add(233)

不可执行add等变更操作~



---------------------------------------------------------------------------

AttributeError                            Traceback (most recent call last)

<ipython-input-28-ae1f00200c4e> in <module>
      1 ft = frozenset([1,2,3])
      2 print('不可执行add等变更操作~')
----> 3 ft.add(233)


AttributeError: 'frozenset' object has no attribute 'add'

a = {1,1,3,'a'}
b = {2,4,5,1}
print(a & b)
print(a | b)
print(a - b)

{1}
{1, 2, 3, 4, 5, 'a'}
{3, 'a'}

3.8.1 集合字面量

• 空集，那么必须写成 set() 的形式
• 除了空集，集合的字符串表示形式总是以 {...} 的形 式出现。

print(type({}))
print(type(set()))
print(type({1}))

<class 'dict'>
<class 'set'>
<class 'set'>

3.8.2 集合推导

• 基本同字典推导式,每次遍历出的元素为单个

{chr(i) for i in range(32, 44)}

{' ', '!', '"', '#', '$', '%', '&', "'", '(', ')', '*', '+'}

3.8.3 集合的操作

同数学中常见集合操作

举几个不常见的:

• or，并集

• s.update(it, ...)，把可迭代的 it 和其他所有参数 转化为集合，然后求它们和 s 的并集，并把 s 更新成这个并 集

• s.__sub__(z) s 和 z 的差集，或者叫作相对 补集

• s.isdisjoint(z) 查看 s 和 z 是否不相交（没有共同元 素）

• s.issubset(it) 把可迭代的 it 转化为集合，然后查看 s 是否为它的子集

• s.__contains__(e) 元素 e 是否属于 s

• s.discard(e) • 如果 s 里有 e 这个元素的话，把它移除

• s.pop() • 从 s 中移除一个元素并返回它的值，若 s 为空，则抛 出 KeyError 异常

• s.iter() • • 返回 s 的迭代器

• s.remove(e) • 从 s 中移除 e 元素，若 e 元素不存在，则抛出 KeyError 异常

3.9 dict和set的背后

• Python 里的 dict 和 set 的效率有多高？

  • 底层结构是散列表，是一种高效的散列结构+搜索结构
  • Python 会设法保证大概还有三分之一的表元是空的，所以在快要达 到这个阈值的时候，原有的散列表会被复制到一个更大的空间里面

• 为什么它们是无序的？

  • 哈希散列后，不再有序
  • 扩容后也不再有序

• 为什么并不是所有的 Python 对象都可以当作 dict 的键或 set 里的 元素？

  • 部分没有实现hash和eq方法的对象不可以

• 为什么 dict 的键和 set 元素的顺序是跟据它们被添加的次序而定 的，以及为什么在映射对象的生命周期中，这个顺序并不是一成不 变的？

  • set 和 frozenset 的实现也依赖散列表，但在它们的散列表里存放的只有元素的引用（就像在字典里只存放键而没有相应的值）；初始化的时候的顺序并没有被打乱，此时引用保持顺序，随着新的值的加入，顺序得到混淆

  • 扩容导致的结果就是要新建一个更大的散列表，并把字 典里已有的元素添加到新表里

• 为什么不应该在迭代循环 dict 或是 set 的同时往里添加元素？

  • 并发存在冲突风险
  • 扩容撞车添加操作的风险

hash加盐

从 Python 3.3 开始，str、bytes 和 datetime 对象的散 列值计算过程中多了随机的“加盐”这一步。所加盐值是 Python 进程内的一个常量，但是每次启动 Python 解释器都会生成一个 不同的盐值。随机盐值的加入是为了防止 DOS 攻击而采取的 一种安全措施。

验证 set 元素的顺序的变更

st = {1,2,3,4,500,60000}

for i in range(700,702):
    st.add(i)
st

{1, 2, 3, 4, 500, 700, 701, 60000}

print('如上所示, set的顺序得到变化,hash的结果,我们打印一下: ')
for num in st.__iter__():
    print(num, 'hash: ', hash(num))

如上所示, set的顺序得到变化,hash的结果,我们打印一下: 
60000 hash:  60000
1 hash:  1
2 hash:  2
3 hash:  3
4 hash:  4
500 hash:  500
700 hash:  700
701 hash:  701

字典和散列表的几个特点

• 集合里的元素必须是可散列的。
• 集合很消耗内存。
• 可以很高效地判断元素是否存在于某个集合
• 在构建集合时，元素的次序取决于被添加到集合里的次序。
• 往集合里添加元素，可能会改变集合里已有元素的次序。
• 整体上set还是无序的数据结构，如果想要保持有序使用：collections.OrderedDict 或者方法sorted（set）