一、字典
在之前课里，如果我们要实现插入，删除和查找，使用树结构，最好的时间复杂度是AVL下的Ο(log2n)，使用线性结构，最好的复杂度为基数排序Ο(n)。但如果使用字典数据类型去做，时间复杂度可为Ο(1)。下面是对字典和Python中字典的相关内容：
字典本质上就是一个直接可接入的表，每个键内可存放一个数列的items。但因此也有坏处：
- 键不一定为非负整数；
消耗大量内存空间。
为了解决这两个问题，散列表被提出来了。
二、散列表
首先我们看下散列表是怎么解决字典第一个问题：键不一定为非负整数。
散列表使用prehash的方法将键变为非负整数，在Python里，hash(x)就是prehash，但需要注意的是有时候，x ≠ y，也有可能会有hash(x) = hash(y)。
关于字典第二问题：消耗大量内存空间，散列表通过hashing方法解决：
hashing方法可以将全部u个keys，减少为可接受的数量大小m。简单来说就是形成一个散列表，通过散列函数hash(x)，将原来键空间内的键放入散列表中进行存放。因为散列函数本身会有冲突collision（即x ≠ y，但hash(x) = hash(y) ），所以散列表下某个键里可能有多个来自键空间内的items。而为了处理这种情况，拉链法Chaining出现了，它是将散列表每个槽内中的冲突元素进行链接，可视化如下：
如果该散列表是简单平均式散列（即每个键被平均(uniformally)地hash到表内的槽里，并且各键hashing是独立的(independently)），并假设有n个keys和m个槽，那么散列表里链长度为n / m = α = load factor。而运行时间为Ο(1 + |chain|) = Ο(1 + α)， 其中1指计算hash的时间，|chain|是指形成chain的时间等于它的长度。
三、散列函数
该课只讲了三种散列函数：Divison Method，Multiplication Method和Universal Hashing。最后一种比前两种能更好地避免冲突。
（1）Divison Method
h(k) = k mod m (mod为求余)
（2）Multiplication Method
h(k) = [(a * k) mod 2w] >> (w - r) (k为w bits，m=2r， ‘>>’为shift right操作)
最后结果为阴影部分。
（3）Universal Hashing
h(k) = [(a * k + b) mod p] mod m (a和b为从{0,...,p-1}中抽取的随机数，p为大于|u|的质数，质数是只能被1和自身整除的数，u为key space的大小)
对于最差情况k1 ≠ k2下， P{h(k1) = h(k2)} = 1 / m，其小于简单平均式散列下的n / m。
