//移位叠加

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