Python_dict与set

Python中的字典类与集合类其内部均采用散列表实现，查询速度不受规模影响。

字典类

丰富的字典构建方法

普通构建方法

a = dict(one = 1 , two = 2 , three = 3)
b = {"one" : 1 , "two" : 2 , "three" : 3}
c = dict(zip(["one" , "two" , "three"] , [1,2,3]))
d = dict([("two" , 2) , ("one" , 1) , ("three" , 3)])
e = dict({"three" : 3 , "one":1 , "two":2})
print(a == b == c == d ==e)

上面的构建方法虽然是多样的，但是其键的插入顺序存在不同，如果产生哈希冲突，那么键的顺序会产生偏差。后半节会进行展示。

字典推导构建字典

用法与列表推导很像，这里不解释。

DIAL_CODES = [
        (86, 'China'),
        (91, 'India'),
        (1, 'United States'),
        (62, 'Indonesia'),
        (55, 'Brazil'),
        (92, 'Pakistan'),
        (880, 'Bangladesh'),
        (234, 'Nigeria'),
        (7, 'Russia'),
        (81, 'Japan'),
    ]
country_code = {code:country.upper() for code ,country in DIAL_CODES}
print(country_code)
# {86: 'CHINA', 91: 'INDIA', 1: 'UNITED STATES', 62: 'INDONESIA', 55: 'BRAZIL', 92: 'PAKISTAN', 880: 'BANGLADESH', 234: 'NIGERIA', 7: 'RUSSIA', 81: 'JAPAN'}
country_code = {country:code for code ,country in DIAL_CODES}
print(country_code)
# {'China': 86, 'India': 91, 'United States': 1, 'Indonesia': 62, 'Brazil': 55, 'Pakistan': 92, 'Bangladesh': 880, 'Nigeria': 234, 'Russia': 7, 'Japan': 81}

如何处理找不到的键

首先介绍几个字典类关键方法与解释，方便接下来的理解；

方法名	作用
d.default_factory	在__missing__函数中被调用的函数，用于给未找到的元素设置值
d.get(k , [default])	返回键k对应的值，如果字典里没有键k，则返回None或者default
d.__getitem__(k)	让字典d能用d[k]的形式返回键k对应的值
d.__missing__(k)	当__getitem__找不到对应键的时候，则调用此方法
d.__setdefault(k,[default])	若字典中有键k，则直接返回k所对应的值；若无，则使d[k] = default，然后返回default

利用get(k , default)

以下代码实现了利用字典记录词与词频的记录，在键缺失时，采用get()方法进行处理，但是一般来说get的效率很低。

import sys
import re

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[0], 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)
            # this is ugly; coded like this to make a point
            occurrences = index.get(word, [])  # <1>
            occurrences.append(location)       # <2>
            index[word] = occurrences          # <3>
# print in alphabetical order
for word in sorted(index, key=str.upper):  # <4>
    print(word, index[word])
# END INDEX0

获得键word的值，没有则返回[ ]
添加新的位置信息到变量中
将此变量赋值给地点对应键
依次打印词与词位置信息

利用setdefault方法

import sys
import re

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[0], 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)  # <1>

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

上面代码中仅使用了一条语句就实现的相关功能，这是所提倡的方式。

1	my_dict.setdefault(key , []).append(new_value)

等价于

1
2
3

if key not in my_dict:
	my_dict[key] = []
my_dict[key].append(new_value)

利用defaultdict类实现

collection.defaultdict类的特点在于，在用户创建对象的时候就可以给它配置一个找不到键值时创造默认值的方法。通俗将就是在初始化对象时，参数为一个可以调用的方法，此方法在找不到键值时调用。

例如：

1	dd = defaultdict(list)

如果键值不存在时其会进行接下来的流程：

调用list() 构建一个新的列表
新列表作为值，new_value作为键，加入字典中
返回新列表的索引

import sys
import re
import collections

WORD_RE = re.compile(r'\w+')
# 构建一个默认形式的字典
index = collections.defaultdict(list)     # <1>
with open(sys.argv[0], 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[word].append(location)  # <2>

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

实现字典子类并重写 missing方法

当__getitem__找不到对应键的时候，则调用此方法，而__getitem__在dict[key]是进行调用。

class StrKeyDict0(dict):  # <1>

    def __missing__(self, key):
        if isinstance(key, str):  # <2>
            raise KeyError(key)
        return self[str(key)]  # <3>

    def get(self, key, default=None):
        try:
            return self[key]  # <4>
        except KeyError:
            return default  # <5>

    def __contains__(self, key):
        return key in self.keys() or str(key) in self.keys()  # <6>

上面代码中实现了字典的子类及相关方法，这里不解释，可在具体应用时操作。

字典的变种

字典的变种很多，或多或少也接触过。collection.OrderDict\collection.ChainMap\collection.Counter等，不一一解释，用时自然知道。

集合类

集合是唯一对象的聚集。在日常使用中较少，其内部实现结构也是散列表。在集合中包含有两个重要的类别：set与frozenset.其存在一个重要的差别就是：frozenset是可散列的，set是不可散列的。而集合的元素要求是需要散列的。也就是说set的元素可以是forzenset，反之不可以。

上面说的散列就是指的hash()方法，可以哈希则表明hash(key)是不可变的，而set会产生变化，自然不能hash().

集合的构造

普通构建

# 经典构建
s = set([1,2,3])
# {1, 2, 3}

# 空集的构建
s = set()
# set()

利用字面量构建

这里的字面量就是数学表达式的方式，除了空集。

1
2
3

# 字面量构建
s = {1,2,3}
print(s)

集合推导

1
2
3

from unicodedata import name
print({ chr(i) for i in range(32,256) if "SIGN" in name(chr(i) , "")})
# {'>', '±', '÷', '+', '¤', '£', '<', '©', '$', '¶', '#', '¥', '×', 'µ', '¬', '=', '°', '%', '¢', '®', '§'}

dict与set背后的机制

只介绍dict即可。我们知道字典的背后机制是散列表，而散列表是一种稀疏数组。理想的散列函数应当保证整体的均衡性，也就是说越相似的散列值，其结果偏差越大。散列的解决冲突算法采用了再散列法。

键必须是可散列的

支持hash()函数，并且散列值不可变；
支持通过__eq__()方法检测相等性；
若a == b ,则 hash(a) == hash(b)

字典内存开销大

首先需要保证字典是一个稀疏的数组，那么其空间效率低下；

键查询快

不解释

键的次序却决于添加顺序

这是由于大量元素插入过程中，不可避免的会产生冲突。不同顺序会导致差别。

# BEGIN DIALCODES
# dial codes of the top 10 most populous countries
DIAL_CODES = [
        (86, 'China'),
        (91, 'India'),
        (1, 'United States'),
        (62, 'Indonesia'),
        (55, 'Brazil'),
        (92, 'Pakistan'),
        (880, 'Bangladesh'),
        (234, 'Nigeria'),
        (7, 'Russia'),
        (81, 'Japan'),
    ]

d1 = dict(DIAL_CODES)  # <1>
print('d1:', d1.keys())
d2 = dict(sorted(DIAL_CODES))  # <2>
print('d2:', d2.keys())
d3 = dict(sorted(DIAL_CODES, key=lambda x:x[1]))  # <3>
print('d3:', d3.keys())
assert d1 == d2 and d2 == d3  # <4>
# END DIALCODES
"""
# BEGIN DIALCODES_OUTPUT
d1: dict_keys([880, 1, 86, 55, 7, 234, 91, 92, 62, 81])
d2: dict_keys([880, 1, 91, 86, 81, 55, 234, 7, 92, 62])
d3: dict_keys([880, 81, 1, 86, 55, 7, 234, 91, 92, 62])
# END DIALCODES_OUTPUT
"""

新键的添加可能影响原键的顺序

这是一个之前的盲点，无论何时往字典里添加新的键，Python解释器都可能做出为字典扩容的决定。扩容则导致新建一个更大的散列表，并将字典里已有的元素添加到新表里。这个过程可能产生新的散列冲突，导致次序变化。

由此可知，不可以对字典同时进行迭代与修改。

如果对字典同时进行迭代与修改，如果想要扫描并修改一个字典，最好分成两步：先对字典迭代，得出需要添加的内容，放入新字典；迭代结束后，对原字典更新。

字典类