@Author  : Spinach | GHB
@Link    : http://blog.csdn.net/bocai8058

文章目录

常用的hash函数

直接取余法

取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。

maxM一般是不太接近 2^t 的一个质数。

乘法取整法

主要用于实数。

平方取中法

平方后取中间的,每位包含信息比较多。

直接寻址法

取关键字或关键字的某个线性函数值为散列地址。

数字分析法

分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相同,这样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用后面的数字来构成散列地址,则冲突的几率会明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

折叠法

将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。

随机数法

选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。

处理冲突的方法

hash冲突在所难免,解决冲突是一个复杂问题。冲突主要取决于:

  • 与散列函数有关,一个好的散列函数的值应尽可能平均分布。
  • 与解决冲突的哈希冲突函数有关。
  • 与负载因子的大小。太大不一定就好,而且浪费空间严重,负载因子和散列函数是联动的。

解决冲突的办法:

  1. 开放定址法:线性探查法、平方探查法、伪随机序列法、双哈希函数法。
  2. 拉链法:把所有同义词,即hash值相同的记录,用单链表连接起来。

开放定址法

开放寻址法;Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长,di为增量序列

线性探查法
平方探查法
伪随机序列法
双哈希函数法(再散列法)

链地址法(拉链法)

将所有哈希地址相同的记录都链接在同一表中。

建立一个公共溢出区

把冲突的都放在另一个地方,不在表里面。


10-07 11:12