简单说明
hashtable是根据key查询value的一种数据结构，使用数组结构来存储所有的元素，使用一种方式将key映射到数组的不同下标，查询时key就可以直接映射到value，时间复杂度为O(1),因此，hashtable结构经常用于查询的目的。
要实现hashtable，主要有以下2点
1.寻找一种隐射关系，将key映射到数组的某个下标，本文使用简单的取余方式来得 到key在元素中的下标，如果为了hashtable映射更具有一致性 （尽可能的多隐射到不同的下标，少产生冲突），请自行阅读更多的资料 2.不同的key可能会映射到数组的同一个下标，那么如何处理这种冲突，
本文不对理论做过多说明，只用代码说明是如何实现的，如果觉得实现有问题，欢迎拍砖。
实现
头文件
#ifndef LINKED_HASHTABLE_H #define LINKED_HASHTABLE_H #include <stdint.h> typedef void (*free_hashtable_func)(void *); ///< 释放函数指针声明 /************************************************************************** * @file linked_hashtable.h * @brief 使用链表方式处理冲突的哈希表 * @author liqiang * @date 2021.6.8 * @modify 2022.5.25 * @version v1.0 **************************************************************************/ #define CKEYHASHTABLESIZE 8317 /**< hash桶元素的最大值*/ #define HASH_TABLE_OUT_MEMORY -1 #define HASH_TABLE_NO_CUR_ELEMENT -2 //不存在当前元素 #define HASH_TABLE_NO_CUR_KEY -3 //不存在当前元素的key #define HASH_TABLE_NO_EXIST -4 #define HASH_TABLE_NO_KEY_ELEMENT -5 //table中不存在对应key的元素 #define HASH_TABLE_KEYALREADYEXISTS -6 //table中不能插入key存在的值 struct key_hash_table; struct key_hash_element; /************************************************************************** * @brief hash_table_new 创建hashtable对象 * @param table 要创建的table * @param cover_old_value[in] 如果为0，则添加时，新值不能覆盖旧值，如果为其他，则可以 * 覆盖 * @return 成功创建返回0,否则返回 HASH_TABLE_OUT_MEMORY **************************************************************************/ int hash_table_new(struct key_hash_table **table, int cover_old_value); /************************************************************************** * @brief hash_table_free 清空表的元素和响应的内存空间 * @param table **************************************************************************/ void hash_table_free(struct key_hash_table *table); /************************************************************************** * @brief hash_table_custom_free 释放表及其元素的相关内存，元素的释放工作 * 由free_func指定 * @param table 要释放的table * @param free_func 释放元素的操作函数指针 **************************************************************************/ void hash_table_custom_free(struct key_hash_table *table, free_hashtable_func free_func); /************************************************************************** * @brief hash_table_goto_first_element 设置hashtable 指向第一个元素 * @param table **************************************************************************/ void hash_table_goto_first_element(struct key_hash_table *table); /************************************************************************** * @brief hash_table_goto_last_element 设置hashtable 指向最后一个元素 * @param table **************************************************************************/ void hash_table_goto_last_element(struct key_hash_table *table); /************************************************************************** * @brief hash_table_has_cur_element 判断hashtable 当前元素是否存在 * @param table * @return 存在返回1,否则返回0 **************************************************************************/ int hash_table_has_cur_element(struct key_hash_table *table); /************************************************************************** * @brief hash_table_del_cur_element 删除hashtable 当前元素 * @param table * @return 成功返回0，否则返回小于0的错误码（HASH_TABLE_NO_CUR_ELEMENT） **************************************************************************/ int hash_table_del_cur_element(struct key_hash_table *table); /************************************************************************** * @brief hash_table_get_cur_element 返回hashtable 当前元素的value * @param table * @return 如果table不为空，返回hashtable 当前元素的value，否则返回NULL **************************************************************************/ void *hash_table_get_cur_element(struct key_hash_table *table); /************************************************************************** * @brief hash_table_get_cur_key 返回hashtable 当前元素的key * @param table * @return 如果table存在，返回当前元素的key，否则返回 HASH_TABLE_NO_CUR_KEY **************************************************************************/ uint32_t hash_table_get_cur_key(struct key_hash_table *table); /************************************************************************** * @brief hash_table_goto_key_element hashtable当前指针指向hashtable * 指定key对应的的元素 * @param table * @param key 指定的key * @return 找到返回0，没找到返回错误码 **************************************************************************/ int hash_table_goto_key_element(struct key_hash_table *table,const uint32_t key); /************************************************************************** * @brief hash_table_has_key_element 根据key判断对应的hash桶的下标是否存在对应的元素 * @param table[in] * @param key[in] 指定的key * @return 存在key的元素返回TRUE,不存在对应key返回0 **************************************************************************/ int hash_table_has_key_element(struct key_hash_table *table, const uint32_t key); /************************************************************************** * @brief hash_table_add_element 往hashtable中添加元素 * @param table[in] * @param key[in] 添加的key * @param value[in] 添加的value值 * @param b_need_free_value[in] 是否需要删除元素值的内存 * @return 添加成功返回0，否则返回错误码 **************************************************************************/ int hash_table_add_element(struct key_hash_table* table,const uint32_t key, void *value,int b_need_free_value); /************************************************************************** * @brief hash_table_goto_next_element 获取当前元素的下一个元素 * @param table[in] **************************************************************************/ void hash_table_goto_next_element(struct key_hash_table* table); /************************************************************************** * @brief hash_table_goto_prev_element 获取当前元素的前一个元素 * @param table[in] **************************************************************************/ void hash_table_goto_prev_element(struct key_hash_table* table); /************************************************************************** * @brief hash_table_del_key_element 从hashtable中删除指定key的元素 * @param table[in] * @param key[in] 指定的key * @return 成功返回0，否则返回错误码 **************************************************************************/ int hash_table_del_key_element(struct key_hash_table *table,const uint32_t key); #endif //
C文件
#include <stdio.h> #include <assert.h> #include <stdint.h> #include <stdlib.h> #include <string.h> #include "linked_hashtable.h" /**************************************************************************** *brief RtpKeyHashElement为 hashtable的元素结构 **************************************************************************/ typedef struct key_hash_element { int hashindex; /**< 元素占用的下标位置 */ int b_need_free_value; /**< 是否需要删除元素value的内存 */ uint32_t key; /**< 元素的key(使用无符号32位作为元素的key)*/ void* value; /**< 元素的value */ struct key_hash_element *hashprev,*hashnext; /**< hash桶的前后元素指针（横向列表,不同的key得到相同的hash值，链表连接这些元素） */ struct key_hash_element *listprev,*listnext; /**< 哈希桶的纵向数组的列表(寻找不同下标的元素) */ }key_hash_element_t; /************************************************************************** *brief RtpKeyHashTabale为 hashtable 结构 **************************************************************************/ typedef struct key_hash_table { key_hash_element_t *element_table[CKEYHASHTABLESIZE]; /**< 指针数组:有CKEYHASHTABLESIZE个指针元素的数组，每个指针指向一个key_hash_element_t特有的元素）*/ key_hash_element_t *firsthashelem,*lasthashelem; /**< table第一个元素和最后一个元素的指针*/ key_hash_element_t *curhashelem; /**< 当前元素的指针*/ int cover_old_value;/**< 添加时，该变量用于记录是否用新值覆盖旧值，1-覆盖，0-不覆盖*/ }key_hash_table; /************************************************************** * @brief getRtpHashTableIndex 根据key获取下标index(hash函数) * @param key 元素key * @return 返回元素key的index **************************************************************/ static inline int get_hash_table_index(const uint32_t key) { return key % CKEYHASHTABLESIZE; } int hash_table_new(key_hash_table **table, int cover_old_value) { key_hash_table *temp = *table; if(temp != 0) memset(temp,0,0); else { temp = (key_hash_table *)calloc(1, sizeof(key_hash_table)); } if(temp == NULL) return HASH_TABLE_OUT_MEMORY; temp->cover_old_value = cover_old_value; *table = temp; return 0; } void hash_table_free(key_hash_table *table) { if(table == NULL) return; key_hash_element_t *list_tmp = NULL,*list_tmp_next = NULL;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp用于保存哈希桶下一个元素（用于纵向列表） /** * 释放hashtable所有元素的内存空间 */ list_tmp = table->firsthashelem; while(list_tmp != 0)//释放元素内存空间 { key_hash_element_t *hash_tmp,*hash_next_tmp; //用于保存横向hashtable的元素，可能多个不同的key，hash值是一样的，这时候就需要在桶中的同一个元素使用链表标识 hash_tmp = list_tmp->hashnext;// while(hash_tmp != 0) { hash_next_tmp = hash_tmp->hashnext; if(hash_tmp->b_need_free_value) //如果需要删除元素内容空间 { free(hash_tmp->value); hash_tmp->value = NULL; } free(hash_tmp); hash_tmp = hash_next_tmp; } list_tmp_next = list_tmp->listnext;//获取hashtbale的下一个元素 if(list_tmp->b_need_free_value) { free(list_tmp->value); list_tmp->value = NULL; } free(list_tmp); list_tmp = list_tmp_next; } table->firsthashelem = 0; table->lasthashelem = 0; table->curhashelem = 0; for (int i = 0 ; i < CKEYHASHTABLESIZE ; i++) table->element_table[i] = NULL; free(table);//释放table自身 } int hash_table_del_cur_element(key_hash_table *table) { if(table == NULL) return 0; if (table->curhashelem) { key_hash_element_t *list_tmp,*list_tmp_next;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp_next用于保存下一个元素（用于纵向列表） int index; /** *在hash桶中重新设置连接 */ index = table->curhashelem->hashindex;//获取下标位置 list_tmp = table->curhashelem->hashprev;//横向的前一个元素 list_tmp_next = table->curhashelem->hashnext; if (list_tmp == 0) { table->element_table[index] = list_tmp_next;//设置为当前元素的下一个元素 if (list_tmp_next != 0)//如果存在，则设置前一个元素为空，如果不存在下一个元素，相当于table[index] = 0 list_tmp_next->hashprev = 0; } else // { list_tmp->hashnext = list_tmp_next; if (list_tmp_next != 0) list_tmp_next->hashprev = list_tmp; } /** *在hash桶中重新设置连接 */ list_tmp = table->curhashelem->listprev; list_tmp_next = table->curhashelem->listnext; if (list_tmp == 0) //要删除的元素为hash桶中为第一个元素 { table->firsthashelem = list_tmp_next; //将要删除元素的下一个元素设置为第一个元素 if (list_tmp_next != 0)//如果下一个元素存在，设置下一个元素的前一个元素为空 list_tmp_next->listprev = 0; else //要删除的元素同时也是最后一个元素，说明只有一个元素，这时候相当于头和尾都设置为空 table->lasthashelem = 0; } else { list_tmp->listnext = list_tmp_next; if (list_tmp_next != 0) list_tmp_next->listprev = list_tmp; else // table->curhashelem 为列表中的最后一个元素 table->lasthashelem = list_tmp; } //删除当前元素所指向的内存 if(table->curhashelem->b_need_free_value) { free(table->curhashelem->value); } free(table->curhashelem); table->curhashelem = list_tmp_next; // 设置当前元素指向下一个元素 } else return HASH_TABLE_NO_CUR_ELEMENT; return 0; } void hash_table_custom_free(key_hash_table *table, free_hashtable_func free_func) { if(table == NULL) return; key_hash_element_t *list_tmp = NULL,*list_tmp_next = NULL;//用于存放hashtable桶的元素：list_tmp从第一个开始，list_tmp_next用于保存下一个元素（用于纵向列表） /** * 释放hashtable所有元素的内存空间 */ list_tmp = table->firsthashelem; while(list_tmp != 0)//释放元素内存空间 { key_hash_element_t *hash_tmp,*hash_next_tmp; //用于保存横向hashtable的元素，可能多个不同的key，hash值是一样的，这时候就需要在桶中的同一个元素使用链表标识 hash_tmp = list_tmp->hashnext;// while(hash_tmp != 0) { hash_next_tmp = hash_tmp->hashnext; free_func(hash_tmp->value); free(hash_tmp); hash_tmp = hash_next_tmp; } list_tmp_next = list_tmp->listnext;//获取hashtbale的下一个元素 free_func(list_tmp->value); free(list_tmp); list_tmp = list_tmp_next; } table->firsthashelem = 0; table->lasthashelem = 0; table->curhashelem = 0; for (int i = 0 ; i < CKEYHASHTABLESIZE ; i++) table->element_table[i] = NULL; free(table);//释放table自身 } int hash_table_add_element(key_hash_table* table,const uint32_t key,void *value,int bNeedFreeValue) { if(table == NULL) return HASH_TABLE_NO_EXIST; key_hash_element_t *e,*newelem; int index = get_hash_table_index(key);//不同的元素可能获取到相同的index e = table->element_table[index]; int found = 0; while(!found && e != 0) { if (e->key == key) found = 1; else e = e->hashnext; } if(!found) { //元素key不存在，往hash table中添加新元素 newelem = (key_hash_element_t*)calloc(1, sizeof(key_hash_element_t)); newelem->value = value; newelem->key = key; newelem->hashindex = index; newelem->b_need_free_value = bNeedFreeValue; if (newelem == 0) return HASH_TABLE_OUT_MEMORY; e = table->element_table[index]; table->element_table[index] = newelem; newelem->hashnext = e; if (e != 0) e->hashprev = newelem; if (table->firsthashelem == 0)// hash列表中还不存在元素 { table->firsthashelem = newelem; table->lasthashelem = newelem; } else //hash列表中已经存在一些元素 { table->lasthashelem->listnext = newelem; newelem->listprev = table->lasthashelem; table->lasthashelem = newelem; } }else { if (table->cover_old_value)//替换元素 { hash_table_goto_key_element(table, key); table->curhashelem->value = value; } else { return HASH_TABLE_KEYALREADYEXISTS; } } return 0; } int hash_table_goto_key_element(key_hash_table *table,const uint32_t key) { if(table == NULL) return HASH_TABLE_NO_EXIST; int index = get_hash_table_index(key);//获取下标位置（hash 函数-如何根据key来得到hash的位置） table->curhashelem = table->element_table[index]; int found = 0; while(!found && table->curhashelem != 0) { if (table->curhashelem->key == key) found = 1; else table->curhashelem = table->curhashelem->hashnext; } if (!found) return HASH_TABLE_NO_KEY_ELEMENT; return 0; } int hash_table_has_key_element(key_hash_table *table, const uint32_t key) { if(table == NULL) return 0; key_hash_element_t *tmp; int index = get_hash_table_index(key); tmp = table->element_table[index]; int found = 0; while(!found && tmp != 0) { if (tmp->key == key) found = 1; else tmp = tmp->hashnext; } return found; } int hash_table_del_key_element(key_hash_table *table, const uint32_t key) { if(table == NULL) return HASH_TABLE_NO_EXIST; int status; status = hash_table_goto_key_element(table,key); if (status < 0) return status; return hash_table_del_cur_element(table); } void hash_table_goto_first_element(key_hash_table *table) { if(table != NULL) table->curhashelem = table->firsthashelem; } void hash_table_goto_prev_element(key_hash_table *table) { if(table && table->curhashelem) table->curhashelem = table->curhashelem->listprev; } void hash_table_goto_last_element(key_hash_table *table) { if(table != NULL) table->curhashelem = table->lasthashelem; } void hash_table_goto_next_element(key_hash_table *table) { if(table && table->curhashelem) table->curhashelem = table->curhashelem->listnext; } uint32_t hash_table_get_cur_key(key_hash_table *table) { if(table != NULL && table->curhashelem != NULL) return table->curhashelem->key; return HASH_TABLE_NO_CUR_KEY; } void *hash_table_get_cur_element(key_hash_table *table) { if(table != NULL) return table->curhashelem->value; return NULL; } int hash_table_has_cur_element(key_hash_table *table) { if(table != NULL) return (table->curhashelem == 0)? 0 : 1; return 0; }
调用例子
void test_hashtable() { struct key_hash_table *hashtable = NULL; hash_table_new(&hashtable, 1); int a = 1; int b = 2 ; hash_table_add_element(hashtable,1,&a,0); hash_table_add_element(hashtable,1,&b,0); hash_table_add_element(hashtable,2,&b,0); hash_table_add_element(hashtable,3,&a,0); hash_table_del_key_element(hashtable,1); hash_table_del_key_element(hashtable,3); hash_table_del_key_element(hashtable,3); hash_table_goto_first_element(hashtable); while(hash_table_has_cur_element(hashtable)) { int *c = (int *) hash_table_get_cur_element(hashtable); printf("c::%d\n", *c); hash_table_goto_next_element(hashtable); } hash_table_free(hashtable); }
