[TOC]

第三章 字典和集合

泛化映射类型

标准库里所有的映射类型都是利用dict实现的，只有可散列的数据类型才可以用作这些映射的键。

什么是可散列的数据类型?

1. 在这个对象的生命周期中，它的散列值是不变的
2. 而且这个对象需实现__hash__()方法
3. 还要有__qe__()方法，这样才能跟其他键比较

可散列的数据类型有哪些？

• 原子不可变类型：str,bytes,数值类型
• frozenset（返回一个冻结的集合，冻结后集合不能再添加或删除任何元素）
• 元组，只有当元组中所有元素都是可散列的，它才是可散列的
• 一般用户自定义的对象，散列值就是id()函数返回的值

与列表推导式类似，看下面的例子

>>> tuple_list = [(1,'a'),(2,'b'),(3,'c')]
>>> tuple_list
[(1, 'a'), (2, 'b'), (3, 'c')]
>>> dictcomp = {str(i):j for i,j in tuple_list}
>>> dictcomp
{'1': 'a', '2': 'b', '3': 'c'}

处理找不到的键

用d.get(k,default）处理找不到的键

字典d[k]找不到正确的键的时候，会抛出异常，可以使用d.get(k,default)代替，但这个用法效率较低。参数default表示当键k不存在的时候，默认返回一个值。

书中例子的一段代码：

occurrences = index.get(word,[])
# 如果word不存在，则会返回一个list
occurrences.append(loction)
index[word] = occurrences

用setdefault处理找不到的键

用法为d.setdefault(key,default),如果键不存在，就创建这个键，并令这个键指向默认default

上面Python代码与下面等价：

index.setdefault(word,[]).append(location)

collections.defaultdict处理找不到的键

在创建defaultdict对象的时候，首先需要给它配置一个当找不到键时候的默认值。具体地，实例化一个defaultdict的时候，需要给构造方法提供一个可调用的对象，这个可调用对象会在__getitem__找不到键的时候被调用，让__getitem__返回某种默认值。

当创建字典:dd = collections.defaultdict(list)时，如果dd[key]找不到键key，表达式dd[key]会执行3个步骤：

1. 调用list()创建一个列表
2. 把这个列表作为值，key作为键放到dd中
3. 返回这个列表的引用

上面的python语句可修改为

index = collections.defaultdict(list)

index[word].append(location)

特殊方法__missing__

所有的映射类型在找不到键的时候，即在__getitem__找不到键的时候，Python会自动调用__missing__方法。__missing__方法只会被__getitem__调用。

例子StrKeyDict0类,这个类可以同时使用非字符和字符类型

class StrKeyDict0(dict):
    # 这里继承了dict类
    def __missing__(self,str):
        if isinstance(key,str):
            raise KeyError(key)
        # 如果key本身就是str类型，则抛出异常，这里是为了防止死循环
        return self[str(key)]
    def get(self,default=None):
        try:
            return self[key]
        except KeyError:
            return default
        # 如果抛出异常，说明__missing__也失败了
    def __contains__(self,key):
        retrurn key in self.keys() or str(key) in self.keys()

字典的变种

1. collections.OrderedDict
   这个类型在添加键的时候会保持键顺序，所以在迭代的时候，键的次序总是一致的。
2. collections.ChainMap
   这个类型可以容纳数个不同的映射对象，当进行键查找的时候，这些对象会被当做一个整体，逐个被查找，直到找到建为止。
3. collections.Counter
   计数
4. collections.UserDict
   UserDict有一个data属性，这个属性是UserDict最终存储数据的地方

集合set

1. set类型和frozneset类型
2. 使用{1,2,3}要比set([1,2,3])速度快很多，因为后者首先查询构造语法，然后生成一个list，最后把这个list传入构造语法中
3. 集合推导式，用{}括起来

dict和set的底层实现都是散列表

查询的过程

为了获取 my_dict[search_key] 背后的值， Python首先会调用hash(search_key) 来计算 search_key 的散列值，把这个值最低的几位数字当作偏移量，在散列表里查找表元（具体取几位， 得看当前散列表的大小） 。 若找到的表元是空的， 则抛出 KeyError 异常。 若不是空的， 则表元里会有一对 found_key:found_value。这时候 Python 会检验 search_key == found_key 是否为真， 如果它们相等的话， 就会返回 found_value。如果search_key ！= found_key，则发生散列冲突，需根据解决冲突的办法，继续下一个搜索。

dict/set的实现及其导致的后果

1. 键必须是可hash的
2. 字典在内存上需要巨大的开销，因为散列表的稀疏性质，导致它在空间上的效率低下。
3. 查询快
4. 往字典里添加新键可能会改变已有键的次序，因为Python会设法保证大概有三分之一的表元是空的，所以快要到达这个阈值的时候，原有的散列表会被复制到一个更大的空间。所以当添加新键的时候，Python解释器都有可能会对字典扩容，建立一个更大的散列表，这时候会产生新的和原来不一样的hash冲突，导致新散列表中的键的次序发生变化。故当迭代一个字典的时候同时对这个字典修改，这个循环有可能会跳过一些键，所以最好不要同时对一个字典进行迭代和修改