目录
1.概念
哈希表:关键字与存储位置有函数关系的表。只要给出关键字的值,我们就可以计算出该关键字在哈希表中的存储位置,方便查找。
冲突:两个或多个不同的关键字根据函数关系计算得到的存储位置一致。关键字个数大于存储位置的个数,就不可避免产生冲突,所以我们需要寻找处理冲突的方法。
同义词:产生冲突的关键字互称同义词。
2.哈希表的构造方法
随机关键字在哈希表上分布的越均匀,发生冲突的概率也越低,这是构造哈希表要遵循的原则,还有计算的函数要尽量简单,不然会拖慢运行速度。
设关键字为key,H(key)为存储位置
2.1直接定址法
直接定址法适用于连续的关键字,它的构造函数是线性的,H(key)=a*key+b
a为缩放系数,b为平移系数
如关键字9到18,取a=1,b=-9,存储位置为0到9.
2.2除留余数法
H(key)=key%p
p取不大于m且最接近m的素数(或不包含小于20的质因子的合数?)
m为哈希表地址区间长度。
2.3折叠法
折叠法就是将关键字分割成位数相同的若干部分,然后叠加求和(舍弃进位),得到的值就是存储位置。
叠加求和又分为移位叠加和Z形叠加。
举个栗子,关键字31 4159 2689,哈希表m=10000,故按4位分割,比m少一位,这样得到的地址是4位的。
移位叠加就是0031+4159+2689,Z形叠加就是0031+9514+2689
移位叠加实现如下
//移位叠加
int hash_m(long key){
int i,j=1,sum=0;
for(i=0;i<4;i++)j*=10; //按4位分割,可改成其他位数
while(key!=0){
i=key%j;
sum+=i;
if(sum>=j)sum%=j; //舍弃进位
key/=j;
}
return sum;
}
2.4平方取中法
平方取中法先取关键字的平方,然后根据哈希表地址区间长度m来取平方数中间若干位作为存储位置。如m=1000,则取平方数中间3位作为存储位置,比m少一位。
取关键字平方值的万千百三位的哈希函数如下
int hash_3(int key){
long temp;
temp=key*key/100; //除去个十位
if(temp>=1000) //如果平方数大于或等于5位数
temp-=temp/1000*1000;
return temp;
}
3.处理冲突的方法
3.1链地址法
链地址法将关键字为同义词的记录链接在同一个单链表中。
3.2开放定址法
开放定址法是当发生冲突时,通过某种探测技术在哈希表计算得到另一个地址,然后插入,如果又产生冲突,则继续寻找下一个地址,直到能成功插入为止。
查找和插入的过程一样,先查找初始位置,没找到则按探测技术寻找下一个地址,没找到则继续下一个地址,直到探测到空闲地址,若仍找不到,则说明表中无要查的关键字。
而常用的探测方法有线性探测法和二次探测法两种。
3.2.1线性探测法
算法思路:把哈希表看成一个循环空间,哈希表地址区间长度为m,先根据哈希函数求出关键字key的初始存储位置,若产生冲突,则寻找下一个地址(H(key)+1)%m,若仍然冲突,则再寻找下一个地址(H(key)+2)%m,即按线性寻找下一个地址,重复操作,直到地址(H(key)+m-1)%m,再往下寻找就会回到初始位置。适用于关键字数量比地址区间长度小的情况。
3.2.2二次探测法
算法思路:同样先根据哈希函数求出关键字key的初始存储位置,若产生冲突,则寻找下一个地址(H(key)+1*1)%m,还是冲突,下一个寻找地址为(H(key)-1*1)%m,然后接着是(H(key)+2*2)%m,……,(H(key)+(m-1)*(m-1))%m,(H(key)-(m-1)*(m-1))%m。在H(key)两边跳跃寻找,故叫二次探测。
4.哈希表的实现
4.1链地址哈希表的实现
typedef int KeyType; //定义KeyType为int型,方便修改
typedef struct{
KeyType key; //关键字
……
}RcdType;
typedef struct Node{
RcdType r; //数据域
struct Node *next; //指针域
}Node; //结点
typedef struct{
Node **rcd; //rcd[size]内存放的是指针
int size; //哈希表容量
int count; //当前表内记录的个数
int (*hash)(KeyType key,int hashSize); //函数指针变量,指针hash指向哈希函数,hashSize表示
}HashTable; //哈希表地址区间长度
//链地址哈希表的初始化
Status InitHash(HashTable &H,int size,int (*hash)(KeyType,int)){
int i;
H.rcd=(Node**)malloc(size*sizeof(Node*)); //分配长度为size的空间,元素类型为指针Node*
for(i=0;i<size;i++)H.rcd[i]=NULL; //置空
H.size=size;
H.hash=hash;
H.count=0;
return OK;
}
//链地址哈希表的查找
int hash(KeyType key,int hashSize){ //至于为什么是hash,我也有点乱
return (3*key)%hashSize;
}
Node* SearchHash(HashTable &H,int key){ //查找关键字为key的记录
int p=H.hash(key,H.size); //key对应的初始存储位置
Node *np;
for(np=H.rcd[p];np!=NULL;np=np->next)
if(key==np->r.key)return np;
return NULL;
}
//链地址哈希表的插入(先查找再插入)
Status InsertHash(HashTable &H,RcdType e){
int p;
Node *np;
if((np=SearchHash(H,e.key))==NULL){ //若没找到,则np=NULL
p=H.hash(e.key,H.size);
np=(Node*)malloc(sizeof(Node)); //创建结点
if(NULL==np)return OVERFLOW;
np->r=e;
np->next=H.rcd[p]; //插入
H.rcd[p]=np; //头指针移动
H.count++;
return OK;
}
return ERROR;
}
//哈希表的销毁
Status DestroyHash(HashTable &H){
int i;
Node *p,*q;
for(i=0;i<H.size;i++){
p=H.rcd[i];
while(p!=NULL){
q=p;
p=p->next;
free(q); //释放内存
q=NULL; //指针置空
}
}
free(H);
H=NULL;
return OK;
}
4.2开放定址哈希表的实现
typedef char KeyType;
typedef struct{
KeyType Key;
……
}RcdType;
typedef struct{
RcdType *rcd;
int size; //哈希表容量
int count; //当前表内元素个数
int *tag; //tag[]=0为空,1为有效,-1为已删除
int (*hash)(KeyType key,int hashSize); //函数指针变量,指针指向哈希函数
void (*collision)(int &hashValue,int hashSize); //处理冲突的函数
}HashTable;
//之所以tag[]=-1表示已删除,是因为如果删除一个记录后用tag[]=0表示的话,那么如果哈希表内
//确定有关键字key,但不在初始位置hash(key,H.size)上,如果删除key前面一个记录,tag[]=0;
//查找到前面那个结点时,认为有空闲位置,故查找结束,判断没有key这个关键字,就会导致出错。
//线性探测法处理冲突
void collision(int &hashValue,int hashSize){
hashValue=(hashValue+1)%hashSize;
}
//开放定址哈希表的初始化
Status InitHash(HashTable &H,int size,int *tag,int (*hash)(KeyType,int),void (*collision)(int &,int)){
int i;
H.rcd=(RcdType*)malloc(size*sizeof(RcdType));
H.tag=(int*)malloc(size*sizeof(int));
if(NULL==H.rcd||NULL==H.tag)return OVERFLOW;
for(i=0;i<H.size;i++)H.tag[i]=0; //标记置空
H.size=size;
H.count=0;
H.hash=hash;
H.collision=collision;
return OK;
}
//开放定址哈希表的查找
Status SearchHash(HashTable H,KeyType key,int &p,int &c){
//若查找成功,p表示查找记录在表中的位置,查找失败则为可插入位置
//c表示发生冲突的次数,当达到一定阈值时,需要重新构造哈希表
p=H.hash(key,H.size);
while(H.tag[p]!=0){
if(1==H.tag[p]&&H.rcd[p].key==key)return SUCCESS; //1==H.tag[p]不可省,因为删除并未置空
collision(p,H.size);
c++;
}
return UNSUCCESS;
}
//开放定址哈希表的插入
//存疑,尽管是教科书上的代码,感觉应该tag[]=-1的内存也能用来插入新记录
//开放定址法哈希表网上代码不同的定义太繁杂,只能存疑标一下,没找到能参考的同类定义
Status InsertHash(HashTable &H,RcdType e){
int j,c=0;
if(SUCCESS==SearchHash(H,e.key,j,c))return -1;
else{
H.rcd[j]=e;tag[j]=1;count++;
}
return c;
}
//开放定址哈希表的删除
Status DeleteHash(HashTable &H,RcdType e){
int j,c=0;
if(SearchHash(H,e.key,j,c)!=SUCCESS)return UNSUCCESS;
else{
e=H.rcd[j];H.tag[j]=-1;H.count--; //感觉要将H.rcd[j]置空
}
return SUCCESS;
}