特殊情况：
有时候会产生多个key值在一个桶中的冲突。（鸽巢原理）
函数优秀的特点： （1）确定 （2）快速 （3）满射 （4）均匀
四种函数： 一 除余法：
将M设为素数，可以更加平均。 二 MAD法： 除余法的改进。
除余法的缺陷：（一） 零点为不动点（只有0映射）
（二） 相邻关键码的散列地址也相邻（不在均匀）
MAD = multiply - add - divide 取M为素数， a > 0, b > 0, a % M != 0 hash(key) = ( a * key + b ) % M
三 数字分析：
抽取key中的某几位构成地址，比如取十进制的奇数位 改进： 去key的平方的中间若干位，构成地址。
四 折叠法：
总结：散列函数越是随机、越没有规律就越好。
五 随机数法：
可以将hash的设计套用伪随机数的方法。 关键码转换：
当关键码为数字时，不难将之转换为整数 但当关键码位字符串时，可运用多项式法。
为什么要用如此复杂的方法？
因为如果用每个字母代表一个数字，然后相加求和的话，会导致很多冲突出现（很多字符串字符出现相同，只是顺序不同，或者字符串的和相同）。
每个桶存储多个数据的方法：
利用列表，每一个桶一个列表，动态申请内存 优点：无需预先分配大小，灵活方便。
但这种方法缺点也很大：空间未必连续分布，因此缓存几乎失效；并且动态分配内存需要额外时间。
开放定址策略：
每一个词条对应一个桶序列，按照优先级排序。
即如果优先级最高的桶有空位，则直接放入，如果没有，则向后移，直到找到第一个有空位的桶。
在删除的时候，直接在桶中做一个删除标记，当查找的时候直接略过去，当添加的时候如果找到有删除标记则直接添加。
平方试探：每一次试探不是线性向后移动，而是按照平方来向后移动。
但这时会发生有的空桶怎么也搜索不到而不被利用的情况
定理：在M（素数）个桶单元中，如果用平方探测法，则只会利用M/2取上整个桶。 改进：双向平方探测
先+1^2 再 -1^2 再 +2^2 ……以此类推
这样的方法对特定的素数有效但对其他素数依然无法遍历所有空桶。
4K+3类的素数，可以用此方法。 而4K+1无法。
双平方定理：
任意素数P可以表示为一对整数的平方和，当且仅当P % 4 = 1
——————————————————————————— 桶排序、计数排序 大数据+小范围 数据的取值范围为[0,M) 运用散列表
例如：26个字母的排序 建立26个桶
首先每一个桶中有一个计数器，记录字母出现的次数
只要遍历一次字符集，只要遇到一个字母，就将对应的桶计数器加一，这样一遍即结束。
在遍历的同时，记录字母的累计值 这样就可以得到相应的排序位置。