哈希法及其解决冲突的方法

哈希法又称散列法,相应的表称为哈希表。
基本思想:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的。
冲突:当关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,即 k1≠k2 ,但 f(k1) =f(k2),此时称k1和k2为同义词。实际中,冲突是不可避免的,只能通过改进哈希函数的性能来减少冲突。

 

因此哈希法需要注意两个问题:

 

① 如何构造哈希函数 

 

② 如何处理冲突

 

 

 

构造哈希函数的原则主要有两个:

 

③ 函数本身便于计算;

 

④ 计算出来的地址分布均匀,即对任一关键字k,f(k) 对应不同地址的概率相等,目的是尽可能减少冲突。

 

 

 

通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。常用的解决冲突方法主要有三种:

 

① 开放定址法(再散列法):

 

基本思想:当关键字k的哈希地址p=f(k) 出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。

 

这种方法有一个通用的再散列函数形式:fi = (f(k) + di) % m,i = 1, 2, …, n,其中f(k)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同,主要有以下3种:

 

a. 线性探测再散列:di = 1, 2, …, m - 1,冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

 

b. 二次探测再散列:di = 12, -12, 22, -22, …, k2, -k2(k <= m / 2),冲突发生时,在表的左右进行跳跃式探测,比较灵活。

 

c. 伪随机探测再散列:di = 伪随机数序列,建立一个伪随机数发生器,如i = (i + p) % m,并给定一个随机数做起点。

 

② 再哈希法

 

同时构造多个不同的哈希函数,当哈希地址f1(k) 发生冲突时,再计算f2(k),…,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

 

③ 链地址法

 

基本思想:将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.duanlonglong.com/qdjy/417.html