高级算法设计与分析 学习笔记3 哈希表
首先我们要讨论一个把n个数据放到列表S里面的问题：
但很显然，这些数据的范围有多大这个T就得有多大，而实际上要放的数字可能就几个（比如就放一个1和一个10000000，那我还是要准备一个巨大的T），不好。
为了解决这个问题，哈希表登场了。
哈希表
哈希表的思想
性能分析
n/m就是“装载率”，一个位置平均有几个数字
要找到底，加上一开始调用hash函数的时间。
经典哈希函数
除了除法法以外还有：
这招叫乘法法，m代表有几个位置。
就是说，先让A乘以K，让其后面几位发生变化，然后在用老方法取余。为什么要多此一举？其实就是要让A变大，然后用简单的移位法取余，这样就不用做除法运算了，效率更好。
冲突怎么解决？
位置被占了，那就往下（+i）放。这就叫线性法
更复杂一点的方法，但是性能更好一点。记得这两种方法都要mod m,不要爆了。
