[数据结构与算法]python的字典与集合

介绍

在Python中，字典与集合的实现方式都采用散列表（hash table）实现，集合是值为空的特殊字典。Python语言自身的实现中也广泛使用到了字典，如模块的命名空间、实例的属性记录中。字典要求键是可散列的（hashable），在Python中，一个对象是可散列的是指该对象在生命周期内散列值是不变的，需要在类中实现__hash__()和__eq__()两个方法, __hash__()用于计算散列值, __eq__()用于比较散列值是否相等.

dict.setdefault()

即要在dict中查找元素,又要向dict中添加未查找的元素及值时很有用,相比普通的实现方式,减少查表次数,提高运行效率

根据键获取值，如果没有该键，则存入该键及值，并返回该值。使用示例如下所示：

"""Build an index mapping word -> list of occurrences"""
import re
import sys

WORD_RE = re.compile(r'\w+')
index = {}
with open('03-dict-set\zen.txt', encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start() + 1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location)

# display in alphabetical order
for word in sorted(index, key=str.upper):
    print(word, index[word])

其中，index.setdefault(word, [])表示若word不在字典中，则存入该word，并将其对应的值设定为[]，并返回该值（空列表的引用）。

collections.defaultdict(one_callable)

同上, 在即要在dict中查找元素,又要向dict中添加未查找的元素及值时也是很有用的,相比普通的实现方式,减少查表次数

这个类型在构造方法里可以传入一个可调用对象，当出现未找到键的情况，则会调用该可用对象，其实现机理是在类里定义了一个default_factory用于存储用户定义的可调用对象，后这个对象在__missing__()中被调用。

__missing__()

所有的映射类型在处理找不到键的情况都会牵涉到使用__missing__()方法。__missing__()方法只会被__getitem__()方法调用. 如d[k]会调用__getitem__(), 而__getitem__()就会调用__missing__(). 但get()与in方法并不会调用__missing__(),因为它们里面并没有调用它, 其中get()方法是有单独实现的,而in以__contain__()方法实现.
另外, 在Python3中,k in my_dict.keys()中,dict.keys()返回的是一个’视图’,视图就像一个集合,在视图中查找元素是很快的.

不可变的映射类型

对于有些映射变量, 我们只希望其能被用户能读取, 不希望其被改动, 可以通过为该映射类型定义一个视图变量来实现该功能, 只把视图变量返回给用户调用, 视图是动态的, 可以根据变量自动改变,但不可以通过视图改变变量的值, 以下为一个小示例:

from types import MappingProxyType
d = {1:'a'}
d_proxy = MappingProxyType(d)

d为原变量,d_proxy为视图变量,d_proxy不可改动,而d可以改动.

集合

字典与集合的特点

• 内存开销巨大
• 键的存储次序与添加顺序有关
• 往字典里添加新键可能会改变已有键的顺序