散列表的基本概念
散列函数也称哈希函数，是一个把查找表中关键字映射成关键字对应的地址的函数。
记为Hash(key)=Addr(地址可以是数组下标，索引或者内存地址等)
（一个关键字对应一个地址，但一个地址却可能会与多个关键字相配适。）
散列函数可能会把两个或两个以上的不同关键字映射到同一地址，这种情况被称为冲突，这些发生冲突的不同关键字称为同义词(指经过Hash函数处理之后，得到的地址值相等的一组key值)
例：
Hash（key）=key%13
对于 key1=1 和 key2=14 来说，Hash函数得出的地址值都为 “1”
所以称key1和key2为同义词
好的Hash函数应该尽量减少这样的冲突；另一方面，由于这样的冲突是无法避免的，所以还需要设计好处理冲突的方法。
散列表（哈希表）：根据关键字而直接进行数据访问的数据结构，散列表直接建立了关键字与存储地址之间的一种直接映射关系。
（上面我们介绍了Hash函数的工作原理，就是输入关键字，得出对应的地址值。
所以当我们使用Hash表存储数据的时候，只需要知道数据元素中的关键字和具体的Hash函数，就能找到存储该数据元素的地址。）
哈希函数的构造方法
构造哈希函数的时候，需要注意的点：
1.散列函数的定义域（输入给哈希函数的全部关键字）必须包含全部关键字，而值域（Hash函数得出的地址可以存放的范围）的范围则依赖于散列表的大小。
2.散列函数计算出的地址应尽可能均匀地分布在整个地址空间，尽可能减少冲突。
3.散列函数应尽量简单，能在较短时间内计算出任意一个关键字对应的散列地址。（散列函数复杂的话，会对访存速度产生影响）
下面介绍常用的散列函数。
1.直接定址法
直接取某个线性函数为散列地址，散列函数为：
H(key)=key或H(key)=a*key+b
a与b都为常数，这种方法计算最简单，且不会产生冲突，它适合关键字的分布基本连续的情况，若关键字的分布不连续，空位较多，则会造成存储空间的浪费。
2.除留余数法
这是一种最简单，最常用的方法，假定散列表表长为m，取一个不大于m但最接近或等于m的质数p（这是为了能让关键字尽可能均匀地分布在hash表上，减少冲突的发生）散列函数为：
H(key)=key%p
3.数字分析法
设关键字是r进制数（如十进制或二进制），而r个数码在各个位上出现的频率不一定相同。如果某些位上r个数码分布不均匀，只有某几种数码经常出现，选择这些数码作为散列地址的话，发生冲突的可能性就相对较高；同样，或许在某些位上，r个数码的分布十分均匀，此时选取这些位数作为散列地址的话，发生冲突的可能性就相对较小。（适用于关键字中的某几位，数字分布均匀）
例如：
电话号码前三位，156或者186等前缀总是大批量重合，如果将这三位作为散列地址，那么出现冲突的概率就很高；与之相对，电话号码的后四位，各个数码分布较为均匀，选择它们作为散列地址，散列表发生冲突的概率就相对较小。
4.平方取中法
顾名思义，这种方法取关键字的平方的中间几位作为散列地址，具体取多少位，哪几位。。。要视情况而定。这种方法得到的散列地址与关键字的每一位都有关系，因此使得散列地址分布比较均匀。（适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。）
tip：均小于散列地址所需的位数，那么关键字平方之后位数会变多，足够散列地址需要的位数。
处理冲突的方法
1.开放定址法
所谓开放地址法，是指表中可存放新表项的空闲地址，既可以向它的同义词表项开放，也可以向它的非同义词表项开放。（也就是说，当key1和key2两个同义词发生冲突的时候，作为最先确定散列地址的key1可以稳坐钓鱼台，key2需要去找其他空闲的地址作为其散列地址）
Hi=（H（key）+di）%m
H（key）为散列函数
i=1，2....，k（k<=m-1）
m表示散列表长
di表示增量序列（出现同义词发生冲突的话，原位置无法分配散列地址，这时就需要在原地址的基础上再加一个增量di，确定其他同义词的散列地址）
下面介绍四种处理冲突的方法，其本质都是发生冲突时，针对增量序列di的确认方法。
1）线性探测法
又称线性探测再散列法。
di=1,2,....,m-1
它的特点是：冲突发生时，顺序表查看表中下一个单元，如果空闲则插入，不空闲则继续向后查看（探测到表尾地址m-1时，下一个探测地址是表首地址0），直到找出一个空闲单元或查遍全表。
线性探测虽然是考研爱考的重点，但作为处理冲突的方法，却并不怎么优秀。
线性探测法，可能使第i个散列地址的同义词，存入第i+1个散列地址；而第i+1个散列地址的同义词，就需要争夺第i+2个同义词的散列地址……从而造成大量元素在相邻的散列地址上聚集（或堆积），大大降低了查找的效率。
2）平方探测法
又称二次探测法。
di=1^2, -1^2, 2^2 -2^2.....,k^2, -k^2 (其中k<=m/2)
注意：散列表的长度m必须是一个可以表示成4k+3的素数，只有这样才可以保证空间不被浪费。
平方探测法是一种较好的处理冲突的方法，可以避免“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半。
3）双散列法
di=i*Hash2（key）
需要使用两个散列函数，当通过第一个散列函数H（key）得到的地址发生冲突时，利用第二个散列函数Hash2（key）计算关键字的地址增量。具体形式如下：
Hi=（H（key）+i*Hash2（key））%m
初始探测位置H0=H（key）%m
4）伪随机序列法
di=伪随机序数序列
ps：不管是哪种方法，只要采取开放地址法，就不能随便物理表中已有的元素，否则会阶段其他同义词元素的查找路径。
例如：key1=1，key2=14，key3=27
Hash（key）=key%13
那么key1，key2，key3是同义词，采用线性探测法的话，他们的散列表地址将依次为1，2，3。
现在查找key3，我们将首先找到散列表上地址为1的位置，与key1匹配不上，接下来找地址为2的位置，与key2依旧匹配不上，最后才找到了key3.
如果我们贸然删除散列地址为2的key2的话，再想查找key3，就会因为散列地址2处为空，而判断表中没有key3.
所以当我们要删除一个元素的时候，应该做一个标记删除，进行逻辑删除。将散列地址上原本的key值替换成一个“关键字已死，有事烧纸” 标记，它不同于空值，可以告诉我们“这里曾经存储过一个关键字”的事实。
但这样做有一个副作用：散列表看起来很满，但其实存储有效信息的位置比看上去要少很多，很多位置都没有得到利用。
2拉链法（链接法，chaining）
显然，对于不同关键字可能会通过散列表映射到同一地址，为了避免非同义词发生冲突，可以把所有同义词存储在一个线性链表上，这个线性链表由其散列地址唯一标识。
假设散列地址为i的同义词链表的头指针，存放在散列表的第i个单元中，因而查找，插入和删除操作主要在同义词链中进行。
拉链法适用于经常进行插入和删除的情况。
散列查找及其性能分析
散列表的查找函数与构造散列表的过程基本一致。对于一个给定的关键字key，根据散列函数可以计算出其散列地址：
初始化，我们直到要查找信息的关键字key，以及Hash函数的具体内容，可以据此得出散列地址Addr：Addr=Hash（key）
1.检查表中地址为Addr位置上是否有记录，若无记录，返回查找失败；若有记录，比较它与key的值，相等的话则返回“查找成功”标志，否则执行步骤2.
2.根据之前的学习，我们知道如果不同关键字分配散列地址的时候发生了冲突，那么需要使用给定的处理冲突方法（就是我们之前学到的那几个中的任意一种）以计算“下一个散列地址”并把Addr置为此地址。
平均查找长度ASL为：
