无论是顺序表还是树表,查找数据元素时要进行一系列的键值比较的过程,为了减少比较次数,就需要使数据元素的存储位置和键值之间建立某种联系,为此我们就需要使用散列技术动态查找表。首先我们需要熟悉几个基本一概念:
1. 散列函数-数据元素的键值和存储位置之间建立的对应关系。
2. 散列表-用键值通过散列函数获取存储位置的这种存储方式构造的存储结构。
3. 散列地址-由散列函数决定数据元素的存储位置,该位置 称为散列地址。
4. 散列查找-给定关键字,由散列函数进行转换在表中的地址,查看该位置上有无欲查的元素,有则输入该元素,没有则将它插入到该位置上。
理想的情况下,使用的散列函数使每个键值与散列地址是分别对应的,但在实际应用中,这种情况很少出现。若两个元素的键值不相等,但是通过散列函数转换后的散列地址却是一样的,这就形成了冲突,因为散列函数是从键值集合到地址集合的映像,所以一般情况下,冲突只能尽可能的减少,而不能完全避免。因此,采用散列技术时需要考虑两个问题:
第一,如何选择"均匀的"散列函数?
一个好的散列函数应该满足计算简便,运算速度快,随机性好,地址尽可能均匀分布,冲突小。
第二,用什么方法有效解决冲突?
解决冲突的办法将在下面散列表实现中讲解。
1. 数字分析法
数字分析法又称数字选择法,其方法是收集所有可能出现的键值,排列在一起,对键值的每一位进行分析,选择分布较均匀若干位组成散列地址。所取的位数取决于散列表的表长,若表长为100,取2位即可。
假定已知可能出现的键值如下:
对所有的键值分析不难看出,左起的前三位都是“7 1 2”,第5位只能取1、4,第7位只能取6、7、8,所以这5位都不可取。剩下的4、6、8、9位都是分布较均匀的,可考虑将它们或它们中的几位组织起来作为散列地址。
2. 除留余数法
除留余数法是一种简单有效却最常用的构造方法,其方法是选择一个不大于散列表长n的正整数p,以键值除以p所得的余数作为散列地址,值得注意的是,这一方法的关键在于p的选择,若p选择的不合适,容易发生冲突,通常应遵循以下规则:
1. p不取偶数。
2. p不取关键字字符集的n倍。
3. 一般p选为最接近表长的质数。
3. 平方取中法
平方取中法以键值平方的中间几位作为散列地址。这一方法计算简单,是一种较常用的构造散列函数的方法,通常在选定散列函数时不一定能知道键值的分布情况,取其中哪几位也不一定合适,而一个数的平方中间几位与这个数的每一位都有关,所得散列地址比较均匀。
4. 基数转换法
将键值看成另一种进制的数再转换成原来进制的数,然后选其中几位作为散列地址。
例如:对于一个十进制键值443730,先把它看成十三进制的数并转换为十进制的数,然后根据散列表的长度从中选取几位作散列地址。
由于冲突不可避免,所以采用散列技术需要考虑的第二个问题是如何解决冲突。
在遇到冲突时,会按照一定的规则选择该地址的下一个址,如果仍然冲突,则继续按规则选择下一个地址,以此类推直到不发生冲突为止。
通常用来解决冲突的办法有以下几种:
1. 线性探测法
对任何键值 key,设H(key) = d,设散列表的容量为m,则线性探测法生成的后继散列地址为:
d+1,d+2,...,m-1,0,1,...,d-1
例如:如下图所示,长度为13的散列表,其散列函数为H(key) = key mod 13,在表中已填入键值分别为16,30,54的元素。现要插入其键值 为29的元素,散列函数求出散列地址为3,在地址3上已有元素16,发生冲突。应用线性探测法,得到下一个地址为d+1=4,仍冲突,则再求下一个地址d+2 = 5,这个位置上没有元素,将元素填入散列表中序号为5的单元。
从上面的例子可以看出,用线性探测法生成后继散列地址计算简单,但由于探测的是一个连续的地址续列,这样容易导致非同义词之间对同一个散列地址出现争夺现象,俗称"堆积",为了减小堆积的机会,应设法使后继散列地址尽量均匀的分布在整个散列表中。
2. 二次探测法
二次探测法的基本思想:生成的后继散列地址不是连续的,而是跳跃式的,以便为后续数据元素留下空间而减少堆积。按照二次探测法,键值key的散列地址序列为:
其中m为散列表的表长,i = 1^2,-1^2,2^2,-2^2,...,k^2,-k^2,其中k<=m/2
例如:仍然使用线性探测法中的散列表和散列函数,插入键值为29的元素,当发生冲突时,使用二次探测法,得到下一个地址d1 = (3+1^2) mod 13 = 4,仍然冲突,则再求一下地址d2 = (3-1^2) mod 13 = 2,仍然冲突,直到散列地址为d3 = (3+2^2) mod 13 = 7时其位置没有元素,所以将元素填入散列表中序号为7的位置。
二次探测法的缺点是不易探测到整个散列表的空间,也就是说,上述后继散列地址可能难以包括散列表的所有存储位置。
3.链地址法
链地址法是对每一个同义词都建一个单链表来解决冲突。
设选定的散列函数H,H的值域(即散列地址的范围)为0~(n-1)。设置一个指针向量Pointer HP[n],其中每个指针HP[i]指向一个单链表,该单链表用于存储散列地址为i的数据元素,每一个这样的单链表称为一个同义词子表。
例如:若选定的散列函数为 H(key) = key mod 13,已存入的键值为26、41、25、05、07、15、12、49、51、31、62的散列表。
4. 多重散列法
此法要求设立多个散列函数Hi,i=1,...,k,当给定值key与散列表中的某个值是相对于某个散列函数 Hi 的同义词而发生冲突时,继续计算这个给定值key在下一个散列函数H(i+1)下的散列地址,直到不再产生冲突为止。这种方法的优点是不易产生"堆积",缺点是计算量较大。
5. 公从溢出区法
这种方法的散列表由两个一维数组组成。一个称为基本表,它实际上就是上面所说的散列表,另一个称为溢出表。插入首先在基本表上进行,假如发生冲突,则将同义词存入溢出表。这样,基本表不可能发生冲突。
1. 链地址法散列表
类型定义
// 定义表长
const int n=20;
typedef struct TagNode{
KeyType key;
struct TagNode *next;
}*Pointer ,Node;
typedef Pointer LinkHash[n];
查找算法
Pointer SeahchLinkHash(KeyType key,LinkHash HP){
// 计算key的散列地址
int i = H(key);
// 将同义词子表表头指针传给p
p = HP[i];
if(p==NULL){
return NULL;
};
// 循环扫描
while((p!=NULL) && (p->key!=key)){
p = p->next;
};
return p
}
插入算法
void InsertLinkHash(KeyType key, LinkHash HP){
if (SearchLinkHash(key, HP) == NULL){
int i = H(key);
// 生成新结点
q = Pointer malloc(size(Node));
q->key = key;
// 将新结点插到同义子表的表头结点之后,原表首结点之前
q->next = HP[i];
HP[i] = q;
}
}
删除算法
void DeleteLinkHash(KeyType key, LinkHash HP){
int i=H(key);
if(HP[i]==NULL){
// 同义词子表为空则返回
return;
}else{
p = HP[i];
// 待删结点位于子表表首
if(p->key == key){
HP[i] = p->next;
free(p);
return;
}else{
// 循环子表
while(p->next!=NULL){
q = p;
p = p->next;
if(p->key == key){
q->next = p->next;
free(p);
return;
}
}
}
}
}
2. 线性探测法散列表
类型定义
const int MaxSize = 20;
typedef struct{
KeyType key;
}Element;
typedef Element OpenHash[MaxSize];
查找算法
int SearchOpenHash(KeyType key,OpenHash HL){
// 计算散列地址
int d = H(key);
int i = d;
while((HL[i].key!=NULL) && (HL[i].key!=key)){
i = (i+1)%m;
};
if(HL[i].key ==key){
// 查找成功
return i;
}else{
// 查找失败
return 0;
}
}