什么是哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

散列技术是记录的存储位置和它的关键字之间建立一个确定的对应关系t，使得每个关键字key对应一个存储位置f(key)。当查找时根据这个对应关系找到给定值key的映射f(key)，若查找集合中存在这个记录，则必定在f(key)的位置上。

哈希函数的构造方法

构造哈希函数的方法有很多，首先需要明确什么是“好”的哈希函数？
若相对于关键字集合中的人一个键字，经哈希函数映像到地址集合中任何一个地址的概率是相等的，则称为此类哈希函数为均匀的哈希函数。换句话说，就是使关键字经过哈希函数得到一个随机的地址，一遍使一组关键字的哈希地址均匀分布在整个地址取件中，从而减小冲突。

直接定址法

取关键字或关键字的某个线性函数值为散列地址。即
H(key)=key或H(key) = a·key + b，
其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key）中已经有值了，就往下一个找，直到H(key）中没有值了，就放进去。

数字分析法

数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

平方取中法

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址

折叠法

将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加

保留余数法

选择一随机函数，取关键字的随机值作为散列地址，即H(key)=random(key)其中random为随机函数,通常用于关键字长度不等的场合。

随机数法

选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key)，其中random为随机函数，通常，当关键字不等时采用此法构造哈希函数较恰当。

实际工作中虚视不同的情况采用不同的哈希函数，通常考虑因素有：

1. 计算哈希函数所需时间；
2. 关键字的长度；
3. 哈希表的打消；
4. 关键字的分布情况；
5. 记录的查找频率；

处理冲突的方法

开发寻址法

Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1）
其中H(key）为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

• di=1,2,3，…，m-1，称线性探测再散列；
• di=1^2,-12,2^2,-22，⑶^{2，…，±（k)}2,(k<=m/2）称二次探测再散列；
• di=伪随机数序列，称伪随机探测再散列。

再哈希法

Hi=RHi(key),i=1,2，…，k
RHi均是不同的哈希函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

链地址法

将所有关键字为同义词的记录存储在同一线性表中。

建立一个公共溢出区

假设哈希函数的值域为[0, m - 1]，则设向量HashTable[0..m - 1]为基本表，每个分量存放一个记录，另设向量OverTable[o..v]为溢出表，所有关键字和基本表中关键字为同义词的记录，不管他们有哈希函数得到的哈希地址是什么，一旦发生冲突，都填入溢出表。