九.数据结构——哈希表（2）

哈希表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-bucketNULL) { printf(malloc申请空间失败); return false; } for(int i0;ibucket_count,i) { table-bucket[i]NULL; } //初始化其它成员 table-capacitybucket_count; table-size0; if(hfNULL)//如果hf传入的是NULL { table-hash_funcDefaultHashFunc;//就使用默认的hash函数 } return true; }2.判空bool HashTableIsEmpty(const HashTable* table) { assert(table!NULL); return table-sizeNULL; }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(xLOAD_FACTOR) { printf(未达负载因子无需扩容) return true; } //达到了扩容 //这里不能使用realloc因为key算出的位置会因为容量的扩大而改变 //1.申请二倍原空间大小的空间 int newcapacity2*table-capacity; HashNode** new_bucket(HashNode**)malloc(sizeof(HashNode*)*newcapacity); if(new_bucketNULL) { printf(malloc申请扩容空间失败); return false; } //2.全部赋值为NULL for(int i0;inewcapacity;i) { new_bucket[i]NULL; } //3.计算原桶节点的新位置并放入新桶中 for(int i0;itable-capacity;i) { while(table-bucket[i]!NULL) { HashNode* curtable-bucket[i]; table-bucket[i]cur-next; //计算新位置 int posHashPos(table-hash_func(cur-key,cur-val),newcapacity); //头插 cur-nextnew_bucket[pos]; new_bucket[pos]cur; } } 4.释放原桶使用新桶 free(table-bucket); table-bucketnew_bucket; table-capacitynewcapacity; return true; }bool HashTableInsert(HashTable* table, KeyType key, ValType val) { //参数校验 assert(table!NULL); //计算要存放的桶的位置 int posHashPos(table-hash_func(key),table-capacity); //遍历判断该桶中是否存在相同的key的节点 HashNode* curtable-bucket[pos]; while(cur!NULL) { //如果存在修改val直接返回true if(cur-keykey) { cur-valval; return true; } } //如果不存在新建桶节点,头插进该链表 CheckFactor(table);//检测是否达到负载因子 HashNode* pNewHashNode(key,val); p-nexttable-bucket[pos]; table-bucket[pos]p; //数据量加一 table-size; return true; }4.查找数据并保存valbool HashTableFind(const HashTable* table, KeyType key, ValType *val) { //参数校验 assert(table!NULLVAL!NULL); //计算查找位置 int posHashPos(table-hash_fuc(),table-capacity); //查找有无相同的key的节点 HashNode* curtable-bucket[pos]; while(cur!NULL) { //找到了保存值并返回true if(cur-keykey) { *valcur-val; return true; } curcur-next; } //未找到 return false; }5.删除数据bool HashTableRemove(HashTable* table, KeyType key) { //参数校验 assert(table!NULL); //计算位置并查找有无key的节点 int posHashPos(table-hash_func(key),table-capacity); HashNode* curtable-bucket[pos] HashNode* prevNULL;//保存前驱节点 while(cur!NULL) { //存在 if(cur-keykey) { if(prevNULL)//cur为首元节点 { table-bucket[pos]cur-next; }else { prev-nextcur-next; } free(cur); curNULL; table-size--; return true; } prevcur; curcur-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-capacitytable-size0; table-hash_fucNULL; return true; }_____________________________________________________________________________哈希表的相关操作的实现就完成了这只是一个简易的哈希表仅供参考学习感谢您的观看