Hash表
散列函数:一个把查找表中的关键字映射层该关键字对应的地址的函数，记为Hash(key) = Addr, 散列 函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为“冲突”，这些发生碰撞的不同 关键字称为同义词。理想情况下，对散列表进行查找的时间复杂度为O(1)，即与表中元素个数无关。
散列函数的构造方法
直接定址法 H(key) = a*key + b
这种方法计算最简单，并且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分
布不连续，空位较多，将造成存储空间的浪费。 除留余数法 H(key) = key%p
假设散列表的?度为m，取一个不大于m但接近或等于m的质数p，除留余数法的关键是选好 p，使得每个关键字转换后等概率地映射到散列空间上的任一地址，从而尽可能减少冲突的可 能性。
数字分析法
设关键字是r进制数，而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀 些，每种数码出现的机会均等;而在某些位上分布不均匀，只有某几种数码经常出现，则应选 取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，如果更换了 关键字，就需要重新构造新的散列函数。
平方取中法
取关键字的平方值的中间几位作为散列地址。适用于关键字的每一位取值都不够均匀或均小于
散列地址所需的位数。 折叠法
将关键字分割成位数相同的几部分(最后一部分的位数可以短一些)，然后取这几部分的叠加 和作为散列地址，这种方法称为折叠法。关键字位数很多，而且关键字中每一位上数字分布大 致均匀时，可以采用折叠法得到散列地址。
处理冲突的方法
1、开放地址法 指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放，公式如下: Hi = (H(key) + di) % m , 其中i=1，2，3，...，k (k <= m-1); m表示散列表表?;di为增量序列， 当取定某一增量序列后，则对应的处理方法时确定的，通常有以下四种取法:
线性探测法
di = 1,2,...,m-1,称为线性探测法。这种方法的特点是:冲突发生时，顺序查看表中下一个单元 (当探测到表尾地址m-1时，下一个探测地址是表首地址0)，知道找到下一个空闲单元(当 表未填满时一定能找到一个空闲单元)或查遍全表。
平方探测法
当di=1^2, -1^2, 2^2, -2^2, ... , k^2, -k^2, 其中k <= m/2， m必须是一个可以表示成4*k + 3的 质数，又称为二次探测法 该方法的优点是可以避免”堆积“问题，缺点是不能探测到散列表上的所有单元，但至少能探测 到一半单元
再散列法
当di=Hash2(Key), 又称为双散列法。需要使用两个散列函数，当通过第一个散列函数H(Key) 得到的地址发生冲突时，则利用第二个散列函数Hash2(Key) 计算该关键字的地址增量，再散 列法中，最多经过m-1次探测会遍历表中所有位置，回到H0位置
伪随机序列法 di等于伪随机数序列
2、拉链法 将所有的同义词存储在一个线性表中，这个线性表由其散列地址唯一标识。
