在Python中字典和集合都是依赖散列表(hash表)的。标准库里的所有映射类型都是利用dict来实现的，所以他们都需要可散列的数据类型才能用作这些映射的键。
在python中，原子不可变数据类型(str, bytes， 数值类型)都是可散列对象。元组则需要其包含的元素都是可散列的对象，才是可散列的。
>>> a = (1, 2, 34)
>>> hash(a)
2528502973941209896
>>> b = (1, 2, [3, 4])
>>> hash(b)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
话说collections也太多了吧，哪里都有它。
字典的构造
我们创建字典有几种方式，要在不同的情况下选择不同的情况。
# 1
>>> a = dict(one=1, two=2, three=3)
>>> a
{'one': 1, 'two': 2, 'three': 3}
# 2
>>> b = {'one': 1, 'two': 2, 'three': 3}
>>> b
{'one': 1, 'two': 2, 'three': 3}
# 3
>>> c = dict(zip(['one', 'two', 'three'], [1, 2, 3]))
>>> c
{'one': 1, 'two': 2, 'three': 3}
# 4
>>> d = dict([('one', 1), ('two', 2), ('three', 3)])
>>> d
{'one': 1, 'two': 2, 'three': 3}
>>> a == b == c == d
True
>>> type(a)
<class 'dict'>
字典推导式
在python中， 字典也有其推到式。 我们可以从任何以键值对作为元素的可迭代对象中构造出字典。
>>> test = [('one', 1), ('two', 2), ('three', 3)]
>>> dic = {word: num for word,num in test }
>>> dic
{'one': 1, 'two': 2, 'three': 3}
>>> test1 = [list(r) for r in test]
>>> test1
[['one', 1], ['two', 2], ['three', 3]]
>>> dic = {word: num for word,num in test1 }
>>> dic
{'one': 1, 'two': 2, 'three': 3}
几种常用的映射方法
书中有提到dict,collections.defaultdict, collections.OrderedDict三种数据类型，对于第二种和第三中，我们需要查阅官方文档来进一步的了解，在后面会有提及，但绝对没有官方文档来的详细。
常用的映射方法很多，但是常用的只有几个。 详细请查阅官方文档，我们将更多的目光放在细节上来
d[key]找不到键。
对于一个字典d， 当我们需要从中找到某一个key值所对应的value时，也许在字典中，不存在这个key。
在这种情况下，使用d.get(key， default)的确是一种解决方法。但是调用这种方法，我们只是得到了一个默认值， 并没有把这个键值对加入到字典中。
d = {'one':1, 'two': 2, 'three': 3}
>>> d['three']
3
>>> d['four']
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 'four'
>>> d.get('four', 4) # 这只是一个实例，
4
>>> 'four' not in d.keys()
True
>>> d['four'] = 4
>>> d
{'one': 1, 'two': 2, 'three': 3, 'four': 4}
我们需要两步才能手动给他添加一个新的键值对。
使用d.setdefault(key, default)
与d.get(key, default)相比，我们不仅会得到一个默认值，还会在字典中自动添加这个键值对。
>>> 'five' not in d.keys()
True
>>> d.setdefault('five', 5)
5
>>> d
{'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5}
另外一个类似书中的例子
>>> d = {'one': [1], 'two': [2], 'three': [3]}
>>> d
{'one': [1], 'two': [2], 'three': [3]}
>>> d.setdefault('four', []).append(4)
>>> d
{'one': [1], 'two': [2], 'three': [3], 'four': [4]}
使用__missing__方法
我们其实还可以来定义__missing__方法来解决冲突，我们可以直接使用collections.defaultdic，因为在collections.defaultdict已经实现了__missing__方法, 官方文档。我们也可以定义自己的子类来手动实现__missing__方法。
我们要知道，__missing__只会被__getitem__方法调用，比如表达式d[key]
defaultdict对象
通常如果需要使用__missing__, 我们都会继承自collections.defaultdic。因为他已经帮我们实现了__missing__方法。
>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> 'one' not in d.keys()
True
>>> d['one'].append(1)
>>> d
defaultdict(<class 'list'>, {'one': [1]})
另一个例子
>>> from collections import defaultdict
>>> dic = defaultdict(int)
>>>
>>> dic['one']
0
>>> dic
defaultdict(<class 'int'>, {'one': 0})
>>> dic['one'] = 1
>>> dic
defaultdict(<class 'int'>, {'one': 1})
自定义__missing__方法
假设我们我们所有已知的键都是数值的字符串性质，也就是说'1'，在我们获取字典中元素的时候，我们可以使用数字1和字符串'1'得到相同的值，我们就可以自定义一个继承于字典的类来实现__missing__方法。
class StrkeyDict(dict):
def __missing__(self, key):
if isinstance(key, str): # 如果是字符串，说明就算是字符串也没有对应元素
raise KeyError(key)
return self[str(key)]
def get(self, key, default=None):
try:
return self[key]
except KeyError:
return default
def __contains__(self, key):
return key in self.keys() or str(key) in self.keys()
if __name__ == '__main__':
d = StrkeyDict([('1', 'one'), ('2', 'two')])
print(d)
print(d['1'])
print(d[1]) # 对于1或者'1'都能得到元素
# print(d[3])
print(d.get(1))
print(d.get('1'))
{'1': 'one', '2': 'two'}
one
one
one
one
子类化UserDict
遇到新东西就去官方文档
UserDict本身不是对Dict的继承，实际上它拥有一个data的属性，这才是dict的实例化
from collections import UserDict
class StrkeyDict(UserDict):
def __missing__(self, key):
if isinstance(key, str):
raise KeyError(key)
return self[str(key)]
def __setitem__(self, key, item):
self.data[str(key)] = item
# 在这里我们就是使用data来存储数据
# 而且相比于上一个对__contains__的实现，这个更为简洁
def __contains__(self, key):
return str(key) in self.data
不可变映射类型
在很多情况下，我们有些内容是不允许用户修改的，也就是说是只读的。
在python3.3之后，types引入了一个封装类名叫MappingProxyType。如果给这个类一个映射，它会返回一个只读的映射视图。
>>> from types import MappingProxyType
>>> d = {}
>>> d['A'] = 1
>>> d
{'A': 1}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({'A': 1})
>>> d_proxy['B'] = 2
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: 'mappingproxy' object does not support item assignment
>>> d['B'] = 2
>>> d_proxy
mappingproxy({'A': 1, 'B': 2})
集合
在我以往的使用中，集合通常是用来去重的
>>> l = [1, 2, 1]
>>> l
[1, 2, 1]
>>> set(l)
{1, 2}
但实际上，他还有更多的用处。首先，在python中，集有两种形式，set和frozenset。集合中的元素必须是可散列的，但是set本身不是可散列的，而frozenset是可散列的。
>>> k = frozenset(l)
>>> k
frozenset({1, 2})
>>> hash(k)
-1826646154956904602
>>> k2 = set(l)
>>> hash(k2)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
集合还支持需多中缀运算符，比如合集|，交集&， 差集-
>>> num1 = {1, 2, 3}
>>> num2 = {2, 3, 4}
>>> num1 | num2
{1, 2, 3, 4}
>>> num1 & num2
{2, 3}
>>> num1 - num2
{1}
>>>
集合的创建
由于集合和字典都使用{}来表示，所以我们在创建一个空集合的时候，应当使用set(),而不是{}
>>> test = {}
>>> type(test)
<class 'dict'>
>>> test = set()
>>> type(test)
<class 'set'>
集合的操作
我还是认为官方文档是最好的记录
dict的实现及其导致的结果
如果要更加深入的了解字典和集合，了解散列表是非常必要的。
- 键必须是可散列的
- 必须支持hash()函数
- 支持通过__eq__()方法来检测相等性
- 若a == b， 则hash(a) == hash(b)
- 字典在内存上的开销巨大
由于字典使用了散列表， 而散列表又是稀疏的，这导致它在空间上的效率低下。其实在某些情况下，使用具名元组是一个不错的选择。
- 键的查询很快
dict的实现是典型的空间换时间：字典类型存在这巨大的内存开销，但是它们提供了无视数据量大小的快速访问—只要字典能被放在内存中。由于hash的作用，我们不需要遍历整个空间，而是将要查询的key值hash，并比较，解决冲突就可以了
- 键的次序取决于添加顺序
当往dict里添加新键而又发生散列冲突的时候，新键可能被安排存放到另一个位置，所以哪怕键的顺序是乱序的，当两个字典键值一样，他们依旧是想等的，比如dict([(key1, value1), (key2, value2)])和dict([(key2, value2), (key1, value2)])是相等的。
- 往字典里添加新键可能会改变已有键的顺序
无论何时往字典里添加新的键， Python的解释器都有可能作出字典扩容的决定。而一旦扩容，则会把字典里已有的元素添加到新表中。这个过程是有可能出现新的散列冲突的，从而导致发生顺序的改变。但是是否发生什么，我们是不能很确定的，他取决于字典背后的实现。
所以，我们不应对字典同时进行迭代和修改。因为如果我们在添加某个数据的时候，很有可能会导致字典键的顺序发生变化，从而导致迭代出错。最正确的是，首先进行迭代，得出要添加的数据，然后把这些数据放在一个新的字典中，迭代结束后再对原字典进行修改。
set的实现及其导致的结果
set和dict都是散列表实现的，所以两者的特性十分相似
- 集合里的元素必须是可散列的
- 集合很消耗内存
- 可以很高效的判断某个元素是否在某个集合中
- 元素的次序取决于被添加到集合里的次序
- 往集合里添加元素，可能导致原有元素的次序改变