1．基本概念(散列函数)

2．散列函数

3．处理冲突的方法(线性探查法 向散列表中插入一个元素： 从散列表中查找一个元素： 平方探查法 双散列函数探查法)

4．散列表的运算

1．基本概念

散列函数

：在进行查找时，在记录的存储位置与它的关键字之间建立一个确定的对应关系h,以线性表中每个元素的关键字K为自变量，通过函数h(K)计算出该元素的存储位置，我们将h函数称为散列函数或哈希函数。h(K)的值称为散列地址或哈希地址。

例：

假定一个线性表为A=(18,75,60,43,54,90,46)，选取散列函数为：

h(K)=K%m 取m=13

则得每个元素散列地址：

h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4

h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7

根据散列地址，实现元素的存储映象H[m]：

0　1　2　3　4　5　6　7　8　9　10　11　12

H　 　 　54　 　43　18　 　46　60　 　75　 　90

冲突：在实际应用中，通常可能出现一个待插入元素的散列地址单元已被占用情况，使得该元素无法直接存入此单元，这种情况称为冲突。

同义词：具有不同关键字而具有相同散列地址的元素称为同义词，即key1≠key2，但h(key1)=h(key2)。由同义词引起的冲突称作同义词冲突。

例：如向下表中再插入元素70时，70%13=5，则出现了冲突

0　1　2　3　4　5　6　7　8　9　10　11　12

H　　　　　54　　　43　18　　　46　60　　　75　　　90

装填因子(α)：指散列表中已存入的元素数n与散列表空间大小m的比值,即：α=n/m。当α越小时，冲突可能性就越小，但同时，存储空间利用率就越低。

散列表：根据设定的哈希函数及处理冲突的方法将一组关键字映象到一个有限的连续的地址集上，即把记录存放在表中映象的位置上，这种表便称为散列表(哈希表)。

一个散列表的好坏与三个因素有关：

装填因子所采用的散列函数解决冲突的方法

2．散列函数

构造散列函数的目标是使散列地址尽可能均匀分布在散列空间上，同时使计算尽可能简单，以节省计算时间。

直接定址法

以关键字K本身或关键字加上某个数值常量C作为散列地址的方法，对应的散列函数：

h(K)=K+C (C为常数)

例：有一个解放后出生的人口调查表，关键字是年份，h(K)=K+(-1948)，如表所示：

地址 01 02 03 … 22 …

年份　1949 1950 1951 … 1970 …

人数　 … … … 15000 ...

除留余数法

以关键字K除以散列长度m所得余数作为散列地址的方法，对应的散列函数：

h(K)=K%m

m为散列表长，取m=13,得散列表：

0　1　2　3　4　5　6　7　8　9　10　11　12

H　　　　　54　　　43　18　　　46　60　　　75　　　90

取m为奇数比取m为偶数好确保m的值大于等于待散列的线性表的长度n当关键字K为字符串时，需转换为整数(先求K长，接着把每个字符的ASCII码累加到无符号整型量h上，并且每次累加前，h值左移3位，扩大8倍)

int Hash(char * K, int m)

{

//把字符串K转换为0～m-1之间的一个值作为对应记录的散列地址

int len=strlen(K); //求字符串K的长度

unsigned int h=0;

for(int i=0;i<len;i++)

{

//采用一种方法计算K所对应的整数

h<<=3; //h的值左移3位

h+=K[i];

}

return h%m;

}

数字分析法

取关键字中某些数值较分散的数字位作为散列地址的方法，适用于所有关键字已知，并对关键字中每一位的取值分布情况作了分析。

例：有一组关键字如下：

92326875

92739628

92343634

92706816

92774638

92381262

92394220

通过分析：每个关键字从左到右第1、2、3位和第6位取值较集中，不宜作散列地址，其余的第4、5、7、8位取值分散，可以选择，若取最后两位作散列地址，得：

(2,75,28,34,16,38,62,20)

平方取中法

取关键字平方的中间几位作为散列地址的方法，由平方取中法得到的散列地址同关键字的每一位都有关，使得散列地址有较好分散性。

它适用于关键字中每一位取值都不够分散或者较分散的位数小于散列地址所需要的位数的情况。

折叠法：

首先将关键字分割成位数相同的几段(最后一段位数可少一些)，然后将它们的叠加和(舍去最高位进位)作为散列地址的方法。

例：有一关键字：K=68242324，散列地址3位，将此关键字从左到右每三位一段划分后相叠加得：

3．处理冲突的方法

开放定址法

思路：从发生冲突的那个单元开始，按照一定次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元的一类处理冲突的方法。

在使用该方法处理冲突的散列表中，查找一个元素的过程是：先根据给定关键字K，利用与插入时使用的同一散列函数h(K)计算出散列地址(设下标为d),然后用K同d单元的关键字比较，若相等则查找成功，否则按插入时处理冲突的相同次序，依次用K同所查单元的关键字比较，直到查找成功或查找到一空单元(表明查找失败)为止。

三种方法：

线性探查法

是用开放定址法处理冲突的一种最简单的探查方法。

从发生冲突的d单元起,依次探查下一个单元,直到碰到一个空闲单元或探查完所有单元为止探查时,当达到下标为m-1的表尾单元时,下一个探查的单元是下标为0的表首单元。

探查序列为d,d+1,d+2……，表示为(d+i)%m (0≤i≤m-1)。

例如：构取m=13,线性表为A=(18,75,60,43,54,90,46)，构造的散列表如下：

0　1　2　3　4　5　6　7　8　9　10　11　12

H　 　 　54　 　43　18　 　46　60　 　75　 　90

现向表中再插入关键字为31和58的两个元素,用线性探查法解决冲突。

先插入31，h(31)=31%13=5,因H[5]被占用，探查下一个即下标为6的单元，空闲，插入31。

0　1　2　3　4　5　6　7　8　9　10　11　12

H　　　　　54　　　43　18　31　46　60　　　75　　　90

再插入58，h(58)=58%13=6,因H[6]被占用，探查下一个即下标为7的单元，因H[7]仍不空闲，再接着向下探查，当探查到下标为9的单元时，空闲，插入58。

0　1　2　3　4　5　6　7　8　9　10　11　12

H　　　　　54　　　43　18　31　46　60　58　75　　　90

利用线性探查法处理冲突易造成元素的“堆积”(聚集)

0　1　2　3　4　5　6　7　8　9　10　11　12

H　　　　　54　　　43　18　　　46　60　　　75　　　90

向散列表中插入一个元素：

int Insert (hashlist1 HT,int m,ElemType item)

{

//向长度为m的散列表HT中插入一个元素

int d=H(item.key,m); //可选一种合适的构造散列函数的方法，计算散列地址

int temp=d;

while(HT[d].key != NullTag)

{

//当d单元不空时继续向后查找空位置

d=(d+1)%m;

if(d==temp) return 0;

}

HT[d]=item; //将新元素插入到下标为d的位置

return 1;

}

从散列表中查找一个元素：

int Search (hashlist1 HT,int m, ElemType item)

{

//从长度为m的散列表HT中查找

int d=H(item.key, m);

int temp=d;

while(HT[d].key!=NullTag)

{

//当散列地址中的关键字域不为空则循环

if(HT[d].key==item.key) return d;

else d=(d+1)%m;

if(d==temp) return -1;

}

return -1;

}

平方探查法

探查序列为d,d+1,d+2……,表示为(d+i2)%m(0≤i≤m-1)。递推公式为：

优点：它是一种较好的处理冲突的方法，可以较好避免堆积现象

缺点：不能探查到散列表上所有单元。

例：当d0=5,m=17时，只能探查到下标依次为5、6、9、14、4、13、7、3、1的单元。

d0=5;

d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;

d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;

d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;

d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1;

双散列函数探查法

思路：

该方法使用两个散列函数h1和h2，其中h1和前面的h(K)一样，以关键字为自变量，产生一个0～m-1之间的数作散列地址;h2也以关键字为自变量，产生一个1～m-1之间的、并和m互素的数作散列地址。它的探查序列为：

利用双散列法，按一定的距离，跳跃式地寻找“下一个”桶，减少了“堆积”的机会，最多经过m-1次探查，它会遍历表中所有位置，回到H0 位置。

例：给出一组表项关键码{22,41,53,46,30,13,01,67}。散列表为HT[0..10]，m = 11。

散列函数为：

Hash(x)=(3x) % 11

再散列函数为：

ReHash(x) = (7x) % 10 +1

Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2,

H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6

H0(30) = 2 冲突H1 = (2+1) = 3 ,H0(13) = 6 冲突H1 = (6+2) = 8

H0(01) = 3 冲突H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5

H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 冲突, H1 = (3+10) = 2 H2 = (2+10) = 1

搜索成功的平均搜索长度：

链接法

思路：就是把发生冲突的同义词元素(结点)用单链表链接起来的方法。

例：假定一个线性表B为：B=(18,75,60,43,54,90,46,31,58,73,15,34)。

设采用的散列函数为h(K)=K%13,采用链接法处理：

在该例中，查找成功时平均查找长度为：

ASL=(8×1+3×2+1×3)/12≈1.42

若线性探查法处理冲突进行散列存储，得到：

查找成功时平均查找长度为：

ASL=(7×1+1×2+1×4+1×4+1×2+1×6)/12≈2.1

多种方法分析

在散列表的插入和查找算法中，平均查找长度与表的大小m无关，只与选取的散列函数、α值和处理冲突的方法有关,若假定所选取的散列函数能够使任一关键字等概率地映射到散列空间的任一地址上，理论上证明：

当采用线性探查法处理冲突时，ASL=

当采用链地址法处理冲突时，ASL=

当采用平方探查法、双散列函数法处理冲突时，ASL=

散列存储优缺点

插入与查找的速度相当快根据关键字计算散列地址需要开销一定计算时间占用存储空间较多在散列表中只能按关键字查找元素线性表中元素的逻辑关系无法在散列表中体现

4．散列表的运算

设用HashMaxSize常量表示待定义的散列表类型的长度。假定采用开放定址法,其散列表类型用hashlist1表示,类型定义为：

typedef ElemType hashlist1[HashMaxSize];

若采用链接表，其散列表类型用hashlist2表示，类型定义为：

typedef LNode * hashlist2[HashMaxSize];

Lnode 定义如下：

struct Lnode

{

ElemType data;

Lnode *next;

}

在类型为hashlist1的散列表上进行的运算

类型定义：typedef ElemType hashlist1[HashMaxSize];

初始化散列表

void InitHashList (hashlist1 HT)

{

//把散列表HT中每一单元的关键字key域都置空

for(int i=0;i<HashMaxSize;i++)

HT[i].key=NullTag; //NullTag常量表示空标志，

}

清空一个散列表

void ClearHashList (hashlist1 HT)

{

//把散列表HT中每一单元的关键字key域都置空

for(int i=0;i<HashMaxSize;i++)

HT[i].key=NullTag;

}

向散列表中插入一个元素

int Insert (hashlist1 HT,int m,ElemType item)

{

//向长度为m的散列表HT中插入一个元素item

int d=H(item.key,m);

int temp=d;

while(HT[d].key != NullTag)

{

//当d单元不空时继续向后查找空位置

d=(d+1)%m;

if(d==temp) return 0;

}

HT[d]=item; //将新元素插入到下标为d的位置

return 1;

} //返回1表示插入成功

从散列表中查找一个元素

int Search (hashlist1 HT,int m, ElemType item)

{

//从长度为m的散列表HT中查找关键字为item.key的一个元素

int d=H(item.key, m);

int temp=d;

while(HT[d].key!=NullTag)

{

//当散列地址中的关键字域不为空则循环

if(HT[d].key==item.key) return d; //查找成功则反回下标d

else d=(d+1)%m;

if(d==temp) return -1; //查找失败反回-1

}

return -1;

}

从散列表中删除一个元素

int Delete (hashlist1 HT,int m, ElemType item)

{

//从长度为m的散列表HT中删除关键字为item.key的一个元素

int d=H(item.key, m);

int temp=d;

while(HT[d].key!=NullTag)

{

if(HT[d].key==item.key)

{

HT[d].key=DeleteTag;//DeleteTag常量为一删除标记

return 1;

}

else d=(d+1)%m; //继续向后探查

if(d==temp) return 0;

}

return 0; //删除失败返回0

}

在类型为hashlist2的散列表上进行的运算

类型定义：

struct Lnode

{

ElemType data;

Lnode *next;

}

typedef LNode * hashlist2[HashMaxSize];

初始化散列表

void InitHashList(hashlist2 HT)

{

//把散列表HT中每一元素均置为空标志

for(int i=0;i<HashMaxSize;i++)

HT[i].i=NULL;

}

清空一个散列表

void ClearHashList(hashlist2 HT)

{

//清除HT散列表,即回收每个单链表中的结点

LNode * p;

for(int i=0;i<HashMaxSize;i++)

{

p=HT[i];

while(p!=NULL)

{

HT[i]=p->next;

delete p;

p=HT[i];

}

}

}

向散列表中插入一个元素

int Insert(hashlist2 HT,int m,ElemType item)

{

//向长度为m的带连接的散列表HT中插入一个元素item

int d=Hash(item.key,m);

LNode *p=new LNode;//为新元素分配存储结点

if(p==NULL) return0;

p->data=item;//把新结点插入到d单链表的表头

p->next=HT[d];

HT[d]=p;

return 1;

}

从散列表中查找一个元素

ElemType* Search(hashlist2 HT,int m,ElemType item)

{

//从长度为m的带链接的散列表HT中查找元素

int d=Hash(item.key,m);

LNode* p=HT[d];

while(p!=NULL)

{

if(p->data.key==item.key) return &(p->data);

else p=p->next;

}

return NULL; //查找失败返回空指针

}

从散列表中删除一个元素

int Delete(hashlist2 HT,int m,ElemType item)

{

//从长度为m的带链接的散列表HT中删除元素

int d=Hash(item.kye,m);

LNode* p=HT[d],* q;

if (p==NULL) return 0;

if (p->data.key==item.key)

{

HT[d]=p->next;

delete p;

return 1;

}

//从第二个结点起查找被删除的元素

q=p->next;

while(q!=NULL)

{

if(q->data.key)==item.key）

{

p->next=q->next;

delete q;

return 1;

}

else

{

p=q;q=q->next;

}

}

//返回0表示删除失败;

return 0;

}