Python 字典与集合（一）

可散列数据类型

原子不可变数据类型（str、 bytes 和数值类型） 都是可散列类型， frozenset 也是可散列的，元组中包含的所有元素都是可散列类型， 那么它也是可散列的。

一般来讲用户自定义的类型的对象都是可散列的， 散列值就是它们的 id() 函数的返回值， 所以所有这些对象在比较的时候都是不相等的，除非重写 __hash__ 和 __eq__ 方法。

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
Traceback (most recent call last):
File "", line 1, in 
TypeError: unhashable type: 'list'
>>> tf = (1, 2, frozenset([30, 40]))
>>> hash(tf)
-4118419923444501110

字典

只有可散列的数据类型才能用作映射里的键（只有键有这个要求， 值并不需要是可散列的数据类型）。

>>> d = {(1,2,3) : 'abc'}
>>> d
{(1, 2, 3): 'abc'}
>>> d[(1,2,3)]
'abc'
>>> d = {[1,2,3] : 'abc'}
Traceback (most recent call last):
  File line 1, in 
    d = {[1,2,3] : 'abc'}
TypeError: unhashable type: 'list'

collections.ab 模块中定义了 Mapping 和 MutableMapping 两个抽象基类，为 dict 和类似的类型提供接口。但是非抽象映射类型一般不会直接继承这些基类，而是会对 dict 或 collections.User.Dict 进行扩展。这些基类可以用来对映射类型的判断。

>>> from collections import abc
>>> my_dict = {}
>>> isinstance(my_dict, dict)
True
>>> isinstance(my_dict, abc.Mapping) # 可以判断字典和类似的类型
True

字典的多种创建形式

>>> 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})
>>> a == b == c == d == e
True

字典推导

>>> l = [(1, 'a'),(2, 'b'),(3, 'c'),(4, 'd'),(5, 'e'),(6, 'f'),(7, 'g')]
>>> d = {n: c for n, c in l}
>>> d
{1: 'a', 2: 'b', 3: 'c', 4: 'd', 5: 'e', 6: 'f', 7: 'g'}
>>> {n : c.upper() for n, c in l if n % 2 ==0}
{2: 'B', 4: 'D', 6: 'F'}

# 实例
>>> 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 = {country: code for code, country in DIAL_CODES}
>>> country_code
{'China': 86, 'India': 91, 'Bangladesh': 880, 'United States': 1,
'Pakistan': 92, 'Japan': 81, 'Russia': 7, 'Brazil': 55, 'Nigeria':
234, 'Indonesia': 62}
>>> {code: country.upper() for country, code in country_code.items()
... if code < 66}
{1: 'UNITED STATES', 55: 'BRAZIL', 62: 'INDONESIA', 7: 'RUSSIA'}

字典 setdefault

import sys
import re
WORD_RE = re.compile(r'\w+')
index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
  for line_no, line in enumerate(fp, 1): # 枚举，从 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)
# 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
	print(word, index[word])

defaultdict

import sys
import re
import collections
WORD_RE = re.compile(r'\w+')
index = collections.defaultdict(list) # 如果 key 不存在，则新建列表为 key 的值
with open(sys.argv[1], 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)
# 以字母顺序打印出结果
for word in sorted(index, key=str.upper):
print(word, index[word])

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

>>> import collections
>>> d = collections.defaultdict(list)
>>> d['a'].append(123)
>>> d
defaultdict(<class 'list'>, {'a': [123]})
>>> d['a']
[123]
>>> d['b']
[]
>>> d.get('c')
>>> 

这背后运行的其实是特殊方法 __missing__，它会在 defaultdict 找不到键的时候，调用 default_factory。

dict 中并没有实现 __missing__ 方法，但可以继承 dict，然后实现 __missing__ 方法，特殊方法 Python 会自动调用，这样找不到键时就不会抛出 KeyError 异常。

class StrKeyDict0(dict):
	def __missing__(self, key):
		"""如果找不到key对应的值，就使用字符串的key再找一次。"""
		if isinstance(key, str):
			'''如果已经是字符串key，抛出异常。（必须，否则递给调用）'''
			raise KeyError(key)
		return self[str(key)]
		
	def get(self, key, default=None):
		try:
			return self[key] # 走 __getitem__ 方法，如果找不到进入 __missing__
		except KeyError:
			return default # 找不到返回默认值
			
	def __contains__(self, key):
		return key in self.keys() or str(key) in self.keys() 

>>> d = StrKeyDict0([('2', 'two'), ('4', 'four')])
>>> d['2']
'two'
>>> d[4]
'four'
>>> d[1]
Traceback (most recent call last):
...
KeyError: '1'

>>> d.get('2')
'two'
>>> d.get(4)
'four'
>>> d.get(1, 'N/A')
'N/A'

>>> 2 in d
True
>>> 1 in d
False

其它类型字典

collections.OrderedDict

这个类型在添加键的时候会保持顺序， 因此键的迭代次序总是一致的。 OrderedDict 的 popitem 方法默认删除并返回，取决于 last 参数，默认 True ，后进先出，False 先进先出。

>>> from collections import OrderedDict
>>> d = OrderedDict([('a','A'),('b','B')])
>>> d
OrderedDict([('a', 'A'), ('b', 'B')])
>>> d['a']
'A'
>>> d.popitem()
('b', 'B')
>>> d
OrderedDict([('a', 'A')])
>>> d.update(red=1,blue=2)
>>> d
OrderedDict([('a', 'A'), ('red', 1), ('blue', 2)])
>>> d.popitem()
('blue', 2)
>>> d
OrderedDict([('a', 'A'), ('red', 1)])
>>> d.popitem(last=False)
('a', 'A')
>>> d
OrderedDict([('red', 1)])

collections.ChainMap

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

>>> from collections import ChainMap
>>> dict_a = {'red': 1}
>>> dict_b = {'blue': 2}
>>> dict_c = {'green': 3}
>>> cm = ChainMap(dict_a, dict_b, dict_c)
>>> cm['blue']
2

collections.Counter

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

>>> from collections import Counter
>>> c = Counter('absbsdfbc')
>>> c
Counter({'b': 3, 's': 2, 'a': 1, 'd': 1, 'f': 1, 'c': 1})
>>> c['b']
3
>>> del c['b']
>>> c
Counter({'s': 2, 'a': 1, 'd': 1, 'f': 1, 'c': 1})
>>> c['s'] = 1
>>> c
Counter({'a': 1, 's': 1, 'd': 1, 'f': 1, 'c': 1})
>>> list(c.elements())
['a', 's', 'd', 'f', 'c']
>>> c['z'] = 6
>>> c
Counter({'z': 6, 'a': 1, 's': 1, 'd': 1, 'f': 1, 'c': 1})
>>> c.most_common(2)
[('z', 6), ('a', 1)]
>>> c['m']
0
>>> c['m'] + 1
1
>>> c
Counter({'z': 6, 'a': 1, 's': 1, 'd': 1, 'f': 1, 'c': 1})
>>> c['m'] += 1
>>> c
Counter({'z': 6, 'a': 1, 's': 1, 'd': 1, 'f': 1, 'c': 1, 'm': 1})
>>> c.update('abc')
>>> c
Counter({'z': 6, 'a': 2, 'c': 2, 's': 1, 'd': 1, 'f': 1, 'm': 1, 'b': 1})

collections.UserDict

自定义映射类型。UserDict 有一个 data 的属性， 是 dict 的实例， 这个属性实际上是 UserDict 最终存储数据的地方。

import collections
class StrKeyDict(collections.UserDict):
	"""get 方法不需要了，因为它继承了 Mapping.get 方法"""
	def __missing__(self, key):
		if isinstance(key, str):
			raise KeyError(key)
		return self[str(key)]
		
	def __contains__(self, key):
		return str(key) in self.data # 实际数据

	def __setitem__(self, key, item):
		self.data[str(key)] = item

不可变映射类型

标准库里所有的映射类型都是可变的，但可以使用 MappingProxyType 定义只读映射。

>>> from types import MappingProxyType
>>> d = {1: 'A'}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: 'A'})
>>> d_proxy[1]
'A'
>>> a_proxy[2] = 'x'
NameError: name 'a_proxy' is not defined
>>> d[2] = 'x'
>>> d_proxy
mappingproxy({1: 'A', 2: 'x'})
>>> d_proxy[2]
'x'