一、哈希函数和哈希冲突的基本概念

1.哈希函数：

哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表成为哈希表。

基本思想：首先在元素的关键字K和元素的位置P之间建立一个对应关系f，使得P=f(K),其中f成为哈希函数。

创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元；

查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K).

2.哈希冲突：

当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2)，这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

二、哈希函数的构造方法 

哈希函数的构造原则是：函数本身便于计算、计算出来的地址分布均匀（即对任意K，f(K)对应不同地址的概率相等）。

1.数字分析法：

如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。

2.平方取中法：

当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。

 3.分段叠加法：

这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。

4.除留余数法：

假设哈希表长为m，p为小于等于m的最大素数，则哈希函数为 h（k）=k  %  p ，其中%为模p取余运算。

 

三、处理冲突的方法

1.开放定址法

当发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入其中。基本公式为：hash(key) = （hash(key)+di）mod TableSize。其中di为增量序列，TableSize为表长。根据di的不同我们又可以分为线性探测，平方（二次）探测、随机探测。 

其中 m 为表的长度

对增量di有三种取法：

• 线性探测再散列   di = 1 , 2 , 3 , … , m-1
• 平方探测再散列   di = 1^2 , -1^2 , 2^2 , -2^2 , 3^2 , -3^2 , … , k^2 ,  -k^2 
  
  （平方探测再散列是加1的平方；减1的平方，加2的平方，减2的平方，加3的平方，减3的平方。。。加k的平方，减k的平方。)
   
• 随机探测再散列   利用伪随机数列

 

举例：线性探测

以增量序列 1，2，……，（TableSize -1）循环试探下一个存储地址，即di = i。如果table[index+di]为空则进行插入，反之试探下一个增量。但是线性探测也有弊端，就是会造成元素聚集现象，降低查找效率。具体例子如下图： 

 

2.链地址法

 

3.再哈希法

当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。

比如按照姓首字母进行哈希，如果产生冲突可以按照姓字母首字母第二位进行哈希，再冲突，第三位，直到不冲突为止；

4.建立一个公共溢出区域

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