哈希函数

哈希函数

1

基本原理

我们使用一个下标范围比较 大的数组来存储元素。

可以设计一个函数

（哈希函数，

，

也叫做散列函数）

使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也

可以简单的理解为，按照关键字为每一个元素

分 类

，然后将这个元素存储在相应

类

所对应的地方。

但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同 的元素，却

计算出了相同的函数值，这样就产生了

冲突

，换句话说，就是把不同的元素分在了相同的< /p>

类

之中。后

面我们将看到一种解决

冲突

的简便做法。

总的来说，< /p>

直接定址

与

解决冲突

是哈希表 的两大特点。

2

函数构造

构造函数的常用方法（下面为了叙述简洁，设

h(k)

表示关键字为

k

的元素所对应的函数值）

：

a)

除余法：

选择一个适当的正整数

p

，令

h(k ) = k mod p

这里，

p

如果选取的是比较大的素数，

效果 比较好。

而且此法非常容易实现，

因此是最常用的方法。

b)

数字选择法：

如果关键字的位数比较 多，超过长整型范围而无法直接运算，可以选择其中数字分布比较均匀的若干

位，所组成 的新的值作为关键字或者直接作为函数值。

3

冲突处理

线性重新散列技术易于实现 且可以较好的达到目的。

令数组元素个数为

S

，

则当

h(k)

已经存储了元

素的时候，依次探查

(h(k)+i) mod S , i=1,2,3……

， 直到找到空的存储单元为止（或者从头到尾扫描一圈

仍未发现空单元，这就是哈希表已经 满了，发生了错误。当然这是可以通过扩大数组范围避免的）

。

4

支持运算

哈希表支持的运算主要有：初始化

(makenull)

、哈 希函数值的运算

(h(x))

、插入元素

(insert)

、查找元素

(member)

。

设插入的元素的关键字为

x

，

A

为存储的数组。

初始化比较容易，例如

const empty=maxlongint; //

用非常大的整数代表这个位置没有存储元素

p=9997;

//

表的大小

procedure makenull;

var i:integer;

begin

for i:=0 to p-1 do

A[i]:=empty;

End;

哈希函数值的运算根据函 数的不同而变化，例如除余法的一个例子：

function h(x:longint):Integer;

begin

h:= x mod p;

end;

我们注意到，插入和查找 首先都需要对这个元素定位，即如果这个元素若存在，它应该存储在什么位

置，因此加入 一个定位的函数

locate

function locate(x:longint):integer;

var orig,i:integer;

begin

orig:=h(x);

i:=0;

while (ix)and(A[(orig+i)mod S]<>empty) do

inc(i);

//

当这 个循环停下来时，要么找到一个空的存储单元，要么找到这个元

//

素存储的单元，要么表已经满了

locate:=(orig+i) mod S;

end;

插入元素

procedure insert(x:longint);

var posi:integer;

begin

posi:=locate(x);

//

定位函数的返回值

if A[posi]=empty then A[posi]:=x

else error; //error

即为发生了错误，当然这是可以避免的

end;

查找元素是否已经在表中

procedure member(x:longint):boolean;

var posi:integer;

begin

posi:=locate(x);

if A[posi]=x then member:=true

else member:=false;

end;

这些就是建立在哈希表上的常用基本运算。

哈希表

基本概念

若结构中存在关键字和

K

相等的记录，则必定在

f(K)

的存储位置上。由此，不需比较便可直接取得所

查记录。称这个对应关系

f

为散列函数

(Hash function)

，按这个思想建立的表为散列表。

*

对不同的关键字可能得到同一散列 地址，即

key1≠key2

，而

f( key1)=f(key2)

，这种现象称冲突。具

有相同函数 值的关键字对该散列函数来说称做同义词。

综上所述，

根据散列 函数

H(key)

和处理冲突的方法

将 一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的

“

象

”

作为记录在表中

的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

经散列函数映象到地址集合中任何一个地址的概率是相等的，

*

若对于关键字集合中的任一个关键字，< /p>

则称此类散列函数为均匀散列函数

(Uniform Hash function)

，这就是使关键字经过散列函数得到一个

“

随机

的地址

”

，从而减少冲突。

常用的构造

散列函 数

的方法

．．．．

< br>散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位