C语言哈希表

目录

1.概念

2.哈希表的构造方法

2.1直接定址法

2.2除留余数法

2.3折叠法

2.4平方取中法

3.处理冲突的方法

3.1链地址法

3.2开放定址法

3.2.1线性探测法

3.2.2二次探测法

4.哈希表的实现

4.1链地址哈希表的实现

4.2开放定址哈希表的实现

---

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;
}