数据结构 ——哈希表

1、哈希表的概念
概念参考 算法数据结构基础——哈希表（Hash Table）

2、代码实现
下面是用数组实现哈希结构，开放地址法解决冲突的简单哈希表操作

#include <stdio.h>
#include <stdlib.h>
#include <string.h>//数组实现哈希结构，开放地址法解决冲突
typedef struct pair
{int key;//构造一个键出来，充当哈希地址的求解 key,element(存放字符串)char element[20];//存放字符串
}data;typedef struct hashTable
{data **table;//二级指针方便初始化int divisor;//除因子 H（key）=key%divisorint curSize;//当前表大小
}hash;
//创表
hash *createHashTable(int divisor)
{hash *ht = (hash *)malloc(sizeof(hash));if(ht == NULL)return NULL;ht->curSize = 0;ht->divisor = divisor;ht->table=(data **)malloc(sizeof(data *) *(ht->divisor));//分配divisor块4字节的内存放指针if(ht->table == NULL){free(ht);//申请失败，返回前释放前面申请的内存return NULL;}//指针数组初始化1#if 0for (int i = 0; i < divisor; i++){ht->table[i] = NULL;//每块指针指向空}#endif//指针数组初始化2,直接把指针数组的内存全部置零，即初始化为NULLmemset(ht->table,0,sizeof(data *)*ht->divisor);return ht;
}
//找存储当前元素的地址
int search(hash *ht,int key) 
{int pos=key % ht->divisor;//不存在冲突，直接存放//开放地址法解决冲突int curPos=pos;do{//key相同，采用覆盖的数据方式if((ht->table[curPos]==NULL) || (ht->table[curPos]->key==key))return curPos;curPos=(curPos+1)%ht->divisor;} while (curPos!=pos);//从原位置的下一个位置开始找空位，若再次回到原位置，说明没有空间了return curPos;
}   
//插入元素 传参不一样
#if 0
void insert(hash *ht,data data)
{int pos=search(ht,data.key);//找存储当前元素的地址if(ht->table[pos]==NULL){//当前位置为空，直接插入ht->table[pos]=malloc(sizeof(data));if(ht->table[pos]==NULL)return;memcpy(ht->table[pos],&data,sizeof(data));ht->curSize++;}else{//key相同，采用覆盖的数据方式if(ht->table[pos]->key==data.key){strcpy(ht->table[pos]->element,data.element);}else {//如果表满了，会返回原来的位置，但原来的位置与传进来的key会不匹配printf("hashTable is full\n");return;}}
}
#endifvoid insert(hash *ht,data *d)
{int pos=search(ht,d->key);//找存储当前元素的地址if(ht->table[pos]==NULL){//当前位置为空，直接插入ht->table[pos]=malloc(sizeof(data));if(ht->table[pos]==NULL)return;//内存申请失败memcpy(ht->table[pos],d,sizeof(data));ht->curSize++;}else{//key相同，采用覆盖的数据方式if(ht->table[pos]->key==d->key){strcpy(ht->table[pos]->element,d->element);}else {//如果表满了，会返回原来的位置，但原来的位置与传进来的key会不匹配printf("hashTable is full\n");return;}}
}
//遍历哈希表
void travel(hash *ht)
{for (int i = 0; i < ht->divisor; i++){if(ht->table[i]!=NULL)printf("%d:%s\n",ht->table[i]->key,ht->table[i]->element);elseprintf("NULL\n");}
}
//销毁
void destroy(hash *ht)
{for (int i = 0; i < ht->divisor; i++){if(ht->table[i]!=NULL){free(ht->table[i]);ht->table[i]=NULL;}}free(ht->table);
}int main()
{hash *ht=createHashTable(10);data arr[6]={1,"hello",1,"hellomy",3,"women",4,"lucky",5,"money",11,"world123"};for(int i=0;i<6;i++){//arr[i]是具体元素，&arr[i]是才是地址，指针insert(ht,&arr[i]);}travel(ht);destroy(ht);return 0;
}

3、邻接表法实现哈希结构

• 参考文章 哈希表的C语言实现
• 哈希表的通用库参考文章 C语言实现的数据结构之------哈希表