字典与集合：以及背后的哈希表

《流畅的python》读书笔记 Day 2:

字典：

1. 构造方法：

   - b = {'one': 1, 'two': 2, 'three': 3} #最符合我逻辑的
   - a = dict(one=1, two=2, three=3) #左边默认为字符串
   - c = dict(zip(['one', 'two', 'three'], [1, 2, 3])) #用于一次性写完键和值
   

2. 字典推导：
   规则与昨天的列表推导几乎一样，用for和if构造字典。
   一个承载成对数据的列表，它可以直接用在字典的构造方法中

   country_code = {country: code for code, country in DIAL_CODES}
   

集合与一些操作

1. 集合中的元素必须是可散列的， set 类型本身是不可散列的， 即集合里的元素不能重复。
2. 集合初始化：
   a={1,2,3}
   可以看做是没有value的dict。
3. 有趣的数学操作：
   - a & b 求交集
   - a | b 求并集

背后的哈希：

dict 和 set 都建立在哈希上实现。
哈希表 （散列表）实质上是一个稀疏数组，即大部分元素为0. 散列表里存放的单元 （表元），在实现dict时存放了键和值的引用。
因为 Python 会设法保证大概还有三分之一的表元是空的，所以在快要达到这个阈值的时候，原有的散列表会被复制到一个更大的空间里面

1. hash
   为了将键和值以一定的规律存入哈希表，会对值做一个哈希函数的操作得到哈希值（散列值），也就是要在哈希表中存放这对键值的位置。 哈希值的大小往往远小于原来的键的大小（如做了取余计算），这样使得不需要再大海捞针，查找时只需要通过对键做哈希，再找对应哈希值里存在的内容就行了。大大加快了查找速度。

2. hash冲突
   如果把哈希看成以下函数:
   $value = f(key)$value=f(key)
   由于key是一个内容更大的东西，为了加快查找，通过 f 把他压缩为内容更小的value，那么很显然， 一个value可能对应于不同的key。（但是同一个key永远对应于同一个value）。 有点类似于矩阵里面 $Ax = b$Ax=b, 对于固定的$x$x,对于 每个$A$A，只会等于同一个$b$b， 但是对于每个$b$b，可以是不同的$A$A得到的。

当不同的两个key算出同一个value时，就产生了散列冲突。 这时候有多重解决方法，可以参考百度百科，比如著名的拉链法。
python中的具体对策可以参考流畅的python，相当于再多利用一些hash的信息，来区别第一次算出相同的value的key。

3. hash 的意义
   空间换取时间，用更大的内存，换取更快的查询速度。
   list的实现可以作为对比，可以参考https://www.cnblogs.com/Vito2008/p/5141546.html