哈希表（1）中我们简单的认识了一下哈希表的相关内容，本章，让我们一起完成哈希表的构建和相关操作的代码实现吧！

代码：

0.结构体的定义（hash表和hash桶节点）

//hash表的默认负载因子 #define LOAD_FACTOR (0.7) typedef int KeyType;//key类型 typedef const char* ValType;//val类型 typedef size_t (*HashFuncType)(KeyType);//定义函数指针类型 //桶节点结构 typedef struct _HashNode{ KeyType key; ValType val; struct _HashNode* next;//实现链表结构 }HashNode; //hash表结构 typedef struct _HashTable { HashNode** bucket;//中控hash桶 int capacity;//桶的容量 int size;//当前数据量 HashFuncType hash_func;//hash函数 }HashTable;

1.初始化

//实现一个默认的hash函数 static size_t DefaultHashFunc(KeyType key) { return key; }

bool HashTableInit(HashTable* table,int bucket_count, HashFuncType hf) { //指针参数校验 assert(table!=NULL); //初始化桶：申请空间，并把指向的地址全部赋值为NULL table->bucket=(HashNode**)malloc(sizeof(HashNode*)*bucket_count); if(table->bucket==NULL) { printf("malloc申请空间失败"); return false; } for(int i=0;i<bucket_count,i++) { table->bucket[i]=NULL; } //初始化其它成员 table->capacity=bucket_count; table->size=0; if(hf==NULL)//如果hf传入的是NULL { table->hash_func=DefaultHashFunc;//就使用默认的hash函数 } return true; }

2.判空

bool HashTableIsEmpty(const HashTable* table) { assert(table!=NULL); return table->size==NULL; }

3.插入数据

//计算最终存放桶的位置 static size_t HashPos(size_t hash_val,int capacity) { //使用hash值对容量进行取模 return hash_val % capacity; }

//新建桶节点函数 static HashNode* NewHashNode(KeyType key, ValType val) { //申请空间，初始化成员 HashNode* node = (HashNode*)malloc(sizeof(HashNode)); if (node == NULL) { LOG("申请新节点空间失败"); return NULL; } node->key = key; node->val = val; node->next = NULL; return node; }

//检测负载率是否达到负载因子 //达到了说明目前该hash表的冲突概率极高，需要进行扩容 bool CheckFactor(HashTable* table) { assert(table!=NULL); double x=(double)table->size/(double)table->capacity; //如果未达到，直接返回 if(x<LOAD_FACTOR) { printf("未达负载因子，无需扩容") return true; } //达到了，扩容 //（这里不能使用realloc，因为key算出的位置会因为容量的扩大而改变） //1.申请二倍原空间大小的空间 int newcapacity=2*table->capacity; HashNode** new_bucket=(HashNode**)malloc(sizeof(HashNode*)*newcapacity); if(new_bucket==NULL) { printf("malloc申请扩容空间失败"); return false; } //2.全部赋值为NULL for(int i=0;i<newcapacity;i++) { new_bucket[i]=NULL; } //3.计算原桶节点的新位置，并放入新桶中 for(int i=0;i<table->capacity;i++) { while(table->bucket[i]!=NULL) { HashNode* cur=table->bucket[i]; table->bucket[i]=cur->next; //计算新位置 int pos=HashPos(table->hash_func(cur->key,cur->val),newcapacity); //头插 cur->next=new_bucket[pos]; new_bucket[pos]=cur; } } 4.释放原桶，使用新桶 free(table->bucket); table->bucket=new_bucket; table->capacity=newcapacity; return true; }

bool HashTableInsert(HashTable* table, KeyType key, ValType val) { //参数校验 assert(table!=NULL); //计算要存放的桶的位置 int pos=HashPos(table->hash_func(key),table->capacity); //遍历判断该桶中是否存在相同的key的节点 HashNode* cur=table->bucket[pos]; while(cur!=NULL) { //如果存在，修改val，直接返回true if(cur->key==key) { cur->val=val; return true; } } //如果不存在，新建桶节点,头插进该链表 CheckFactor(table);//检测是否达到负载因子 HashNode* p=NewHashNode(key,val); p->next=table->bucket[pos]; table->bucket[pos]=p; //数据量加一 table->size++; return true; }

4.查找数据，并保存val

bool HashTableFind(const HashTable* table, KeyType key, ValType *val) { //参数校验 assert(table!=NULL&&VAL!=NULL); //计算查找位置 int pos=HashPos(table->hash_fuc(),table->capacity); //查找有无相同的key的节点 HashNode* cur=table->bucket[pos]; while(cur!=NULL) { //找到了，保存值并返回true if(cur->key==key) { *val=cur->val; return true; } cur=cur->next; } //未找到 return false; }

5.删除数据

bool HashTableRemove(HashTable* table, KeyType key) { //参数校验 assert(table!=NULL); //计算位置并查找有无key的节点 int pos=HashPos(table->hash_func(key),table->capacity); HashNode* cur=table->bucket[pos] HashNode* prev=NULL;//保存前驱节点 while(cur!=NULL) { //存在 if(cur->key==key) { if(prev==NULL)//cur为首元节点 { table->bucket[pos]=cur->next; }else { prev->next=cur->next; } free(cur); cur=NULL; table->size--; return true; } prev=cur; cur=cur->next; } //不存在 printf("数据不存在"); return true; }

6.获取元素个数

int HashTableSize(const HashTable* table) { assert(table!=NULL); return table->size; }

7.销毁

HashTableDestroy(HashTable* table) { assert(table!=NULL); //1.释放桶中所有节点 if (table->bucket != NULL) //不能重复释放 { for (int i = 0; i < table->capacity; i++) { while (table->bucket[i]!=NULL) { HashNode* node = table->bucket[i]; table->bucket[i] = node->next; free(node); } } } //2.释放桶，初始化所有属性 free(table->bucket); table->bucket = NULL; table->capacity=table->size=0; table->hash_fuc=NULL; return true; }

_____________________________________________________________________________

哈希表的相关操作的实现就完成了，这只是一个简易的哈希表，仅供参考学习，感谢您的观看！！