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

《流畅的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冲突 如果把哈希看成以下函数: v a l u e = f ( k e y ) value = f(key) value=f(key) 由于key是一个内容更大的东西，为了加快查找，通过 f 把他压缩为内容更小的value，那么很显然， 一个value可能对应于不同的key。（但是同一个key永远对应于同一个value）。 有点类似于矩阵里面 A x = b Ax = b Ax=b, 对于固定的 x x x,对于 每个 A A A，只会等于同一个 b b b， 但是对于每个 b b b，可以是不同的 A A A得到的。

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

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