数据结构查找之哈希表

概念： 哈希表又称为散列表，是一种直接计算记录存放地址的方法，在数据元素的关键码与存储位置之间直接建立了映射。 采用哈希表查找的时间复杂度为O（1）。 哈希函数: 哈希函数是在关键字与记录的存储地址之间建立起的一种对应关系，数学表示可以表示为如下： addr(ai)=H(keyi)(其中H（）称为哈希函数，keyi是元素的关键字，addr(ai)是该元素的存储地址。 哈希查找： 通过哈希函数以及其记录的关键字计算出关键字所对应的数据元素的存储地址然后直接到计算得到的指定的地址进行查找。 哈希表冲突： 不同数据元素的关键字通过哈希函数计算可能得到相同的地址（即不同的数据元素映射到了同一个散列地址上，这种现象称为冲突） 哈希函数： 哈希函数基本要求： （1）简单，能够在较短时间内算出结果； （2）定义域必须包含所有需要存储的数据元素所对应的关键字； （3）值域必须在散列表允许的范围内。 哈希函数举例： （1）直接定址法，哈希函数取关键字的线性函数H=a*key+b （2）数字分析法：假设关键字集合中的每个关键字都是有n位数字组合而成，则可以从中提取分布均匀的若干位或他们的组合作为地址。（比如提取学生的学生号后3位作为地址） （3）平方取中法：对关键字求平方，然后取平方值的中间几位作为存储地址。 （4）折叠法：将关键字分割成位数相同的若干部分（如果长度不同最后部分的位数可以不同），然后取他们的叠加和（舍去进位）为哈希地址。 两种叠加方式： 移位叠加：将分割后的几部分低位对齐相加； 间界叠加：从一端沿着分割界来回折叠，然后对齐相加。 例子如下所示： （5）除留余数法：取关键字被某个不大于哈希表长m的数p除后所得到余数作为哈希地址： H（key）=key MOD p(p<=m) 其中p最好是素数，可以较好的避免哈希冲突。 处理哈希冲突的方法： （本质上是给产生冲突的地址寻找一个新的哈希地址） （1）开放地址法； （2）再哈希法； （3）链地址法（拉链法）： （1）比如通过除留余数法得到的地址已经被占用，则检查下一个地址是否为空如果为空则将其作为自己的哈希地址，如下一个地址仍被占用则继续往后找，直到找到一个属于自己的哈希地址，只要哈希地址的长度能达到数据元素的长度则必定能找到一个属于自己的哈希地址。 优点：只要哈希表有空位则一定能找到一个不发生冲突的地址； 缺点：容易发生“二次聚集”，即在处理冲突的 过程中，又添加了新的冲突，对查找不利。 （2构造若干个哈希函数，当发生冲突时，计算下一个哈希地址直到冲突不再发生。 优点：不易产生聚集； 缺点：计算时间变长； （3）将所有哈希地址相同的记录都链接到同一链表当中。具体结构如下所示： 决定哈希表查找的平均查找长度（ASL）的因素有： 1、选用的哈希函数； 2、选用的处理冲突的方法； 3、哈希表的装填因子（装填因子=表中的记录数/表长）