网络编程之 哈希表原理讲解来自老司机的源码

鉴于博主很久没由跟新过数据结构的内容了,所以博主打算给大家讲解一下哈希表的操作

下面的内容来自于一位老司机 martin的源码,博主在这里借用一下,目的是突出哈希表的原理,明天博主就周末了,也能腾出时间来给上传自己的哈希表的应用。

这个是可以插入字符串的哈希表，一般的都是对数字的操作，所以这个的逼格是很高的！！！！（难点剖析放在最后）

#pragma once #define DEFAULT_SIZE 16 /*哈希表元素定义*/ typedef struct _ListNode{ struct _ListNode *next; int key; void *data; }ListNode; typedef ListNode *List; typedef ListNode *Element; /*哈希表结构定义*/ typedef struct _HashTable{ int TableSize; List *Thelists; }HashTable; /*哈希函数*/ int Hash(void *key, int TableSize); /*初始化哈希表*/ HashTable *InitHash(int TableSize); /*哈希表插入*/ void Insert(HashTable *HashTable, int key, void *value); /*哈希表查找*/ Element Find(HashTable *HashTable, const int key); /*哈希表销毁*/ void Destory(HashTable *HashTable); /*哈希表元素中提取数据*/ void *Retrieve(Element e); hash_table.cpp #include <stdio.h> #include <stdlib.h> #include <string.h> #include"hash_table.h" /*根据 key 计算索引，定位 Hash 桶的位置*/ int Hash(int key, int TableSize) { return (key%TableSize); //返回索引值 } /*初始化哈希表*/ HashTable *InitHash(int TableSize){ //传入 哈希桶的个数,在函数内部给哈希表分配空间,再将初始化好了的哈希表传出去。 int i = 0; HashTable *hTable = NULL; if (TableSize <= 0) { //如果用户恶意输入数字,那么我们就可以把哈希表的个数定为我们最初的 16个 TableSize = DEFAULT_SIZE; } hTable = (HashTable *)malloc(sizeof(HashTable)); if (NULL == hTable){ //如果地址分配失败 printf("HashTable malloc error.\n"); return NULL; } hTable->TableSize = TableSize; //为 Hash 桶分配内存空间，其为一个指针数组 hTable->Thelists = (List *)malloc(sizeof(List)*TableSize); //hTable->Thelists其实就是可以来指向哈希表里面的与元素了 if (NULL == hTable->Thelists){ //分配空间失败,打印错误,然后返回 printf("HashTable malloc error\n"); free(hTable); return NULL; } //为 Hash 桶对应的指针数组初始化链表节点 for (i = 0; i < TableSize; i++){ hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));//也就是给头节点分配空间地,这样后续就能完成插入了 if (NULL == hTable->Thelists[i]){ //如果分配失败,那我们就释放之前分配了的空间地址,以免造成内存泄漏 printf("HashTable malloc error\n"); free(hTable->Thelists); free(hTable); return NULL; } else { memset(hTable->Thelists[i], 0, sizeof(ListNode)); //将好小标指向的元素全部清空。主要是防止意外情况。 } } return hTable; } Element Find(HashTable *HashTable, int key) { int i = 0; //目的接受调用HashTable函数返回的索引值 List L = NULL; //定位到(第几个哈希桶)指针数组里面的第几个头结点。 Element e = NULL; //指向定位到的(第几个哈希桶)的第一个节点（第一个节点是不包括头结点的哦）。 i = Hash(key, HashTable->TableSize); L = HashTable->Thelists[i]; e = L->next; while (e != NULL && e->key != key) //目的是为了遍历对应的哈希桶是否存在相同的key值。 e = e->next; return e; //返回两种情况,找到了就返回e对应的结构体,失败了就返回NULL } /*哈希表插入元素，元素为键值对*/ void Insert(HashTable *HashTable, int key, void *value) { Element e = NULL, tmp = NULL; //e用来接收查找后的e,tmp是用来插入的 List L = NULL; //定位到第几个哈希桶,和我们的find中的L的作用是一样的。 e = Find(HashTable, key); //现在就找到了对应的第几个哈希桶的第一个节点了。或者是NULL if (NULL == e){ //如果接收到的e为空的话我们就可以进行插入元素的操作了 tmp = (Element)malloc(sizeof(ListNode)); // 因为我们接收到的是NULL所以非配空间为了插入 if (NULL == tmp) { printf("malloc error\n"); return; } L = HashTable->Thelists[Hash(key, HashTable->TableSize)]; //\定位到第几个哈希桶 //经典的头插法 tmp->data = value; tmp->key = key; tmp->next = L->next; L->next = tmp; } else printf("the key already exist\n"); } /*哈希表删除元素，元素为键值对*/ void Delete(HashTable *HashTable, int key){ //key是你要删除的第几个位置的键值对 Element e = NULL, last = NULL; List L = NULL; int i = Hash(key, HashTable->TableSize); //找到对应的i是第几个 L = HashTable->Thelists[i]; //找到对应的第几个哈希桶 last = L; //让last 等于 对应的第几个哈希桶的头结点 e = L->next; //e指向对应的第几个哈希桶的第一个节点。 while (e != NULL && e->key != key) { //遍历对应的哈希桶的全部链表,结束条件是 找到了要删除的key或者是遍历完成 last = e; //last为e也就是以后要删除的结点的上一个结点 e = e->next; //指向后面的结点 } if (e) {//如果键值对存在,那么就可以删除了。 last->next = e->next; delete(e); } } /*哈希表元素中提取数据*/ void *Retrieve(Element e) //在元素e存在的情况下降找到的 e->data 返回出去 { return e ? e->data : NULL; //三目运算符 } /*销毁哈希表*/ void Destory(HashTable *HashTable) { int i = 0; List L = NULL; Element cur = NULL, next = NULL; for (i = 0; i < HashTable->TableSize; i++) //将所有的哈希桶都遍历完成 { L = HashTable->Thelists[i]; cur = L->next; while (cur != NULL) //将对应的链表全部销毁,跳出之后只有头结点没有销毁了 { next = cur->next; free(cur); cur = next; } free(L); //释放那一个头结点 } //完成之后所有的哈希桶全部销毁 free(HashTable->Thelists); //释放那个二级指针 free(HashTable); //释放哈希表。 } int main(void) { char *elems[] = { "翠花","小芳","苍老师" }; int i = 0; HashTable *HashTable; HashTable = InitHash(31); Insert(HashTable, 1, elems[0]); Insert(HashTable, 2, elems[1]); Insert(HashTable, 3, elems[2]); Delete(HashTable, 1); for (i = 0; i < 4; i++) { Element e = Find(HashTable, i); if (e) { printf("%s\n", (const char *)Retrieve(e)); } else { printf("Not found [key:%d]\n", i); } } system("pause"); return 0; }

希望大家能好好的观看我的注释,相信一定能给你收获的。

如果觉得代码太长的,博主在这里给大家将模块分解了。大家也可以观看分解之后的代码，这样 压力会小一点。 头文件就不用说了相信大家都能看明白，就只是声明和定义结构体的类型而已。

哈希函数

/*根据 key 计算索引，定位 Hash 桶的位置*/ int Hash(int key, int TableSize) { return (key%TableSize); //返回索引值 }

哈希表的初始化

/*初始化哈希表*/ HashTable *InitHash(int TableSize){ //传入 哈希桶的个数,在函数内部给哈希表分配空间,再将初始化好了的哈希表传出去。 int i = 0; HashTable *hTable = NULL; if (TableSize <= 0) { //如果用户恶意输入数字,那么我们就可以把哈希表的个数定为我们最初的 16个 TableSize = DEFAULT_SIZE; } hTable = (HashTable *)malloc(sizeof(HashTable)); if (NULL == hTable){ //如果地址分配失败 printf("HashTable malloc error.\n"); return NULL; } hTable->TableSize = TableSize; //为 Hash 桶分配内存空间，其为一个指针数组 hTable->Thelists = (List *)malloc(sizeof(List)*TableSize); //hTable->Thelists其实就是可以来指向哈希表里面的与元素了 if (NULL == hTable->Thelists){ //分配空间失败,打印错误,然后返回 printf("HashTable malloc error\n"); free(hTable); return NULL; } //为 Hash 桶对应的指针数组初始化链表节点 for (i = 0; i < TableSize; i++){ hTable->Thelists[i] = (ListNode *)malloc(sizeof(ListNode));//也就是给头节点分配空间地,这样后续就能完成插入了 if (NULL == hTable->Thelists[i]){ //如果分配失败,那我们就释放之前分配了的空间地址,以免造成内存泄漏 printf("HashTable malloc error\n"); free(hTable->Thelists); free(hTable); return NULL; } else { memset(hTable->Thelists[i], 0, sizeof(ListNode)); //将好小标指向的元素全部清空。主要是防止意外情况。 } } return hTable; }

哈希表中插入元素:

/*哈希表插入元素，元素为键值对*/ void Insert(HashTable *HashTable, int key, void *value) { Element e = NULL, tmp = NULL; //e用来接收查找后的e,tmp是用来插入的 List L = NULL; //定位到第几个哈希桶,和我们的find中的L的作用是一样的。 e = Find(HashTable, key); //现在就找到了对应的第几个哈希桶的第一个节点了。或者是NULL if (NULL == e){ //如果接收到的e为空的话我们就可以进行插入元素的操作了 tmp = (Element)malloc(sizeof(ListNode)); // 因为我们接收到的是NULL所以非配空间为了插入 if (NULL == tmp) { printf("malloc error\n"); return; } L = HashTable->Thelists[Hash(key, HashTable->TableSize)]; //\定位到第几个哈希桶 //经典的头插法 tmp->data = value; tmp->key = key; tmp->next = L->next; L->next = tmp; } else printf("the key already exist\n"); }

哈希表中查找元素:

Element Find(HashTable *HashTable, int key) { int i = 0; //目的接受调用HashTable函数返回的索引值 List L = NULL; //定位到(第几个哈希桶)指针数组里面的第几个头结点。 Element e = NULL; //指向定位到的(第几个哈希桶)的第一个节点（第一个节点是不包括头结点的哦）。 i = Hash(key, HashTable->TableSize); L = HashTable->Thelists[i]; e = L->next; while (e != NULL && e->key != key) //目的是为了遍历对应的哈希桶是否存在相同的key值。 e = e->next; return e; //返回两种情况,找到了就返回e对应的结构体,失败了就返回NULL }

哈希表中删除元素:

/*哈希表删除元素，元素为键值对*/ void Delete(HashTable *HashTable, int key){ //key是你要删除的第几个位置的键值对 Element e = NULL, last = NULL; List L = NULL; int i = Hash(key, HashTable->TableSize); //找到对应的i是第几个 L = HashTable->Thelists[i]; //找到对应的第几个哈希桶 last = L; //让last 等于 对应的第几个哈希桶的头结点 e = L->next; //e指向对应的第几个哈希桶的第一个节点。 while (e != NULL && e->key != key) { //遍历对应的哈希桶的全部链表,结束条件是 找到了要删除的key或者是遍历完成 last = e; //last为e也就是以后要删除的结点的上一个结点 e = e->next; //指向后面的结点 } if (e) {//如果键值对存在,那么就可以删除了。 last->next = e->next; delete(e); } }

哈希表中提取元素以及销毁哈希表:

/*哈希表元素中提取数据*/ void *Retrieve(Element e) //在元素e存在的情况下降找到的 e->data 返回出去 { return e ? e->data : NULL; //三目运算符 } /*销毁哈希表*/ void Destory(HashTable *HashTable) { int i = 0; List L = NULL; Element cur = NULL, next = NULL; for (i = 0; i < HashTable->TableSize; i++) //将所有的哈希桶都遍历完成 { L = HashTable->Thelists[i]; cur = L->next; while (cur != NULL) //将对应的链表全部销毁,跳出之后只有头结点没有销毁了 { next = cur->next; free(cur); cur = next; } free(L); //释放那一个头结点 } //完成之后所有的哈希桶全部销毁 free(HashTable->Thelists); //释放那个二级指针 free(HashTable); //释放哈希表。 }

博主认为比较难的就是： 指针数组里面存放的是每个哈希桶的头结点，通过求余来锁定要查找或删除的值在哪一个哈希桶里（认为就是这个最难理解，理解了之后其实哈希就不难了）。其他的就是链表的操作了。

明天上传自己敲得代码