第三章–字典与集合

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

3.1泛映射类型

collections.abc模块中有Mapping和MutableMapping两个抽象基类，作用是给dict或其他类似的映射类型定义接口，还有可以用与isinstance()判断某个数据是否是映射类型

标准库中所有映射类型都是利用dict实现了，限制是只有hashable的数据类型才可以作为映射的key

关于hashbale的一些解释

• 原子不可变数据类型 str、bytes、数值类型都是hashable的
• frozenset是hashable的，因为根据其定义frozenset里只能容纳hashable类型
• 元祖只有它包含的所有元素都是hashable的，它才是hashable的

tt=(1,2,(30,40))
print(hash(tt)) # sucess
tl=(1,2,[30,40])
print(hash(tl)) # TypeError: unhashable type: '
1
2
3
4

• 用户自定义类型hashable
  1.用到__hash__的情况有调用hash的时候跟在set、frozenset、dict等哈希集合中
  官方文档 https://docs.python.org/3/reference/datamodel.html#object.hash
  非常建议去读一下官方文档

Called by built-in function hash() and for operations on members of hashed collections including set, frozenset, and dict. 
1

2. 关键是__hash__跟__eq__的实现
3. hash跟eq都不实现的话会用object的hash跟eq函数，object的hash跟eq都是返回对象的内存地址，这时a1==a2 a1 is a2 hash(a1)==hash(a2)的返回值都是一样的，如果a1 a2都是指向同一个对象的话，结果都是True ,如果a1 a2不是指向同一对象，结果都为False

class ClassA():

    def __init__(self):
        self.name='jason'


a1=ClassA()
a2=ClassA()
print(a1==a2, a1 is a2, hash(a1)==hash(a2)) # False False False
a2=a1
print(a1==a1, a1 is a2, hash(a1)==hash(a2)) # True True True
1
2
3
4
5
6
7
8
9
10
11

4. 自定义hash，不实现eq，这样会用到object的eq函数，作为dict的key值时会调用hash跟eq函数，如果两个key的hash相同，还会调用key的eq函数，如果eq结果为False，那么会把两个key识别为不同，尽管他们的hash相同，如下面的代码，dic最终有两个key

class ClassA():

    def __init__(self):
        self.name='jason'

    def __hash__(self):
        print('ClassA Hash method')
        return hash(self.name)


a1=ClassA()
a2=ClassA()
print(a2.__hash__)
dic={}
dic[a1]=1
dic[a2]=2
print(dic)

# <bound method ClassA.__hash__ of <__main__.ClassA object at 0x000001283708D160>>
# ClassA Hash method
# ClassA Hash method
# {<__main__.ClassA object at 0x000001283708D438>: 1, <__main__.ClassA object at 0x000001283708D160>: 2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

5. 自定义eq不定义hash，只定义了eq的话hash方法会变为None，不可调用，此时不能作为dict的key

class ClassA():

    def __init__(self):
        self.name='jason'

    def __eq__(self, other):
        print('ClassA Eq method')
        return self.name==other.name


a1=ClassA()
a2=ClassA()
print(a2.__hash__) # None
dic={}
dic[a1]=1  # TypeError: unhashable type: 'ClassA'
dic[a2]=2
print(dic)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

6. 如果同时定义了hash跟eq，作为dict的key时都会调用，只有两个变量hash值相同，eq返回True时才能判定为同一个key，下面两处代码分别展示了两个变量hash值相同，但eq返回True跟False的情况

class ClassA():

    def __init__(self):
        self.name='jason'

    def __hash__(self):
        print('ClassA Hash method')
        return hash(self.name)
    def __eq__(self, other):
        print('ClassA Eq method')
        return self.name==other.name


a1=ClassA()
a2=ClassA()
print(a2.__hash__)
dic={}
dic[a1]=1
dic[a2]=2
print(dic)

# <bound method ClassA.__hash__ of <__main__.ClassA object at 0x000001EEFFE1D470>>
# ClassA Hash method
# ClassA Hash method
# ClassA Eq method
# {<__main__.ClassA object at 0x000001EEFFE1D160>: 2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class ClassA():

    def __init__(self):
        self.name='jason'

    def __hash__(self):
        print('ClassA Hash method')
        return hash(self.name)
    def __eq__(self, other):
        print('ClassA Eq method')
        # return self.name==other.name
        return self.name=='mike'


a1=ClassA()
a2=ClassA()
print(a2.__hash__)
dic={}
dic[a1]=1
dic[a2]=2
print(dic)

# <bound method ClassA.__hash__ of <__main__.ClassA object at 0x00000201586FD4E0>>
# ClassA Hash method
# ClassA Hash method
# ClassA Eq method
# {<__main__.ClassA object at 0x00000201586FD470>: 1, <__main__.ClassA object at 0x00000201586FD4E0>: 2}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

7. 参考：
   https://blog.csdn.net/sinat_38068807/article/details/86519944
   https://blog.csdn.net/lnotime/article/details/81194962

3.2字典推导

跟列表推导式类似
实现key跟value的互换：dic={value,key for key,value in other_dic.items()}

3.3 常见的映射方法

展示了dict、collections.defaultdict、collections.OrdereDict的方法列表

3.4 映射的弹性key查询

有时候为了方便起见，就算某个键在映射里不存在，我们也希望在通过这个键读取值的
时候能得到一个默认值。有两个途径能帮我们达到这个目的，一个是通过 defaultdict 这
个类型而不是普通的 dict，另一个是给自己定义一个 dict 的子类，然后在子类中实现
__missing__ 方法。

• defaultdict
  举例 dd=collections.defaultdict(list)
  执行dd[key]时，如果key在dd.keys()里则返回dd[key],如果key不在的话就会调用list()得到默认值赋值给dd[key],并返回列表的引用
  
• __missing__方法
  __missing__方法只会被__getitem__调用，跟get或者__contains__无关，这个跟defaultdict的default_factory一个道理，当d[key]找不到key对应的值后就会调用missing方法

3.5 字典的变种

• collections.OrderedDict
  添加key时会保持顺序，key的迭代顺序是一致的，popitem默认删除字典最后一个元素，如果是popitem(last=False)的话会删除第一个元素
• collections.ChainMap
  通过链式的形式存储多个映射对象，在查找key时对所有映射对象进行查询
  查询会查询所有对象，修改只会修改第一个映射对象里的key

from collections import ChainMap

dicA={'a':1,'b':2}
dicB={'b':3,'c':4}
cm=ChainMap(dicA,dicB)
print(cm)# ChainMap({'a': 1, 'b': 2}, {'b': 3, 'c': 4})
print(cm['b']) # 2
cm.pop('b')
print(cm) # ChainMap({'a': 1}, {'b': 3, 'c': 4})
print(dicA) # {'a': 1}
print(cm['b']) # 3
cm.pop('c') # KeyError: "Key not found in the first mapping: 'c'"

1
2
3
4
5
6
7
8
9
10
11
12
13

• collections.Counter
  给key准备一个整数计数器，每次更新一个key时增加家属器

from collections import Counter

ct=Counter('abcdefg')
print(ct)
ct.update('aaaabbddd')
print(ct)
print(ct.most_common(2))

# Counter({'a': 1, 'b': 1, 'c': 1, 'd': 1, 'e': 1, 'f': 1, 'g': 1})
# Counter({'a': 5, 'd': 4, 'b': 3, 'c': 1, 'e': 1, 'f': 1, 'g': 1})
# [('a', 5), ('d', 4)]
1
2
3
4
5
6
7
8
9
10
11

• collections.UserDict
  把标准dict用纯Python又实现了一遍，3.6详细介绍

3.6子类化UserDict

UserDict并不是dict的子类，更像是对dict的一个封装，UserDict有一个data属性，是dict实例，实际上data是数据最终存储的地方，我们构建映射类继承UserDict而不是dict，可以避免dict隐式调用自身的某些方法

3.7不可变映射类型

不可变映射类型意思是指用户能读取映射的值，但不能添加新key或修改value值

from types import MappingProxyType

d={'a':1}
mp=MappingProxyType(d)
print(mp)# {'a': 1}
print(mp['a']) # 1
# mp['b']=2 # TypeError: 'mappingproxy' object does not support item assignment
# mp['a']=3 # TypeError: 'mappingproxy' object does not support item assignment
d['a']=4
print(mp) # {'a': 4}
1
2
3
4
5
6
7
8
9
10

3.8集合论

集合中的元素必须是hashable的，set类型本身不是hashable的，但是frozenset可以，因此可以创建一个包含不同frozenset的set
集合的运算 集合a、b a|b返回合集 a&b返回交集，a-b返回差集
集合推导，跟字典推导类似
s={key for key in my_dict.keys()}

集合的函数列举

dict和set的背后原理

dict和set背后都是用散列表
给予散列表实现的dict和set有以下特点

• 集合里的元素必须是可散列的。
• 集合很消耗内存。
• 可以很高效地判断元素是否存在于某个集合。
• 元素的次序取决于被添加到集合里的次序。
• 往集合里添加元素，可能会改变集合里已有元素的次序。
  注意，不要在遍历dict和set的同时对他们的值进行修改，这可能导致某些值不被遍历到
  dict的keys items values方法返回的都是字典视图，而不是列表