问题:
前面的查找不可避免的要进行比较,是否能直接通过关键字key得到要查找的元素位置?
解决方法:
散列技术
通过记录的存储位置和关键字建立一个确定的对应关系f,使得每个关键字key对应一个存储位置f(key)
f为散列函数/哈希函数
散列表/哈希表(Hash table)--采用散列技术实现数据存储的一块连续的存储空间
散列过程:
1)存储时,散列函数计算数据的散列地址,并按照该散列地址存储该数据
2)查找时,散列函数计算数据的散列地址,按照散列地址访问该记录。
散列适用于:查找
散列技术不适用的情况:
1)同样的关键字,对应很多记录的
2)范围查找
散列函数的设计要素:
计算简单:关键字不会冲突,不超过其它查找技术与关键字的比较时间
散列地址分布均匀
算法时间复杂度:O(1)
散列函数的构造:
1)直接定址法
f(key)=a*key+b (a,b为常数)
特点:简单、均匀不会产生冲突
需要事先知道关键字key的分布情况
适用:查找表较小且连续的情况,现实中不常用
2)数字分析法
抽取关键字的一部分计算散列地址
适用:关键字位数较大情况,事情知道关键字分布、且关键字的若干位分布较均匀
3)平方取中法
先平方再取中间的位数
适用:不知道关键字分布、位数不是很大的情况
4)折叠法
关键字从左到右分割成位数相等的几部分,然后几部分叠加求和、按照散列表表长取后几位作为散列地址
适用:关键字分布未知、关键字位数较多的情况
5)除留余数法
f(key)=key mod p(p<=m)
p选择不好会产生同义词
p的选择:若散列表表长为m,则p<=m的最小质数或不包含小于20质因子的合数
6)随机数法
选择一个随机数,取关键字key的随机函数值作为它的散列地址
f(key)=random(key)
适用:关键字的长度不等情况
散列冲突的处理方法:
关键字key1!=key2 但有散列地址f(key1)=f(key2)
1)开放定址法
线性探测法:
一旦发生冲突、寻找下一个空的散列地址(散列表足够大,空散列地址总可以找到)
fi(key)=(f(key)+di)mod m (di=1,2,3.....,m-1)
不是同义词却争夺一个地址--堆积
二次探测法:(双向寻找)
增加平方运算的目的是不让关键字集聚在某一块区域
fi(key)=(f(key)+di)mod m (di=1^2 ,-1^2 ,2^2 ,-2^2 ,.....,q^2,-q^2, q<m/2)
随机探测法:
冲突时,对于位移量di采用随机函数计算得到
fi(key)=(f(key)+di)mod m (di为随机数列)
2)再散列函数法
准备多个散列函数--当前散列函数发生冲突则换另一个
fi(key)=RHi(key)(i=1,2,3,.....,k)
RHi为不同的散列函数
3)链地址法
将所有关键字为同义词的记录存储在一个单链表中
发生冲突时,在当前位置给单链表增加结点
示意图
查找时需要遍历单链表的性能损耗
4)公共溢出区法
分为基本表和溢出表,发生冲突的存放在溢出表中
基于除留余数法+开放定址法的散列表实现:
1)散列表结构定义
2)初始化散列表
3)散列函数计算(采用除留余数法)
4)插入关键字进散列表(散列冲突的处理采用开放定址法)
5)散列表查找关键字(散列冲突的处理采用开放定址法)
#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 #define NULLKEY -32768 //散列表结构定义 typedef struct { int *elem;//数据元素存储基址,动态分配数组 int count;//当前数据元素个数 }HashTable;
int m=0;//散列表长 //初始化散列表 Status InitHashTable(HashTable *H) { int i; m=HASHSIZE; H->count=m; H->elem=(int*)malloc(m*sizeof(int)); for(i=0;i<m;i++) H->elem[i]=NULLKEY; return OK; } //散列函数 int Hash(int key) { return key%m;//除留余数法 } // 插入关键字进散列表 void InsertHash(HashTable *H,int key) { int addr=Hash(key);//求散列地址 while(H->elem[addr]!=NULLKEY)//如果不为空,则冲突 addr=(addr+1)%m;// 开放地址法线性探测 H->elem[addr]=key;//有空位后插入关键字 } //散列表查找关键字 Status SearchHash(HashTable H,int key,int *addr) { *addr=Hash(key); while(H.elem[*addr]!=key)//判断hash地址对应的值是否和关键字key相等 { *addr=(*addr+1)%m;//开放地址线性探测 if(H.elem[*addr]==NULLKEY || *addr==Hash(key)) { return UNSUCCESS; } } return SUCCESS; }