哈希表（C语言版）

文章目录 哈希表原理实现(无自动扩容功能)代码运行结果 分析应用

哈希表

如何统计一段文本中，小写字母出现的次数?

显然，我们可以用数组 int table[26] 来存储每个小写字母出现的次数，而且这样处理，效率奇高。假如我们想知道字母’k’出现的次数，直接访问元素 table['k' - 'a'] 即可，时间复杂度为O(1)。

在现实生活中，我们经常需要存储键值对(key-value)数据，比如上面的 ‘a’:10, ‘b’:6，再比如账号:个人信息，关键字:网页等等。如果键的取值范围很小(比如上面的例子)，那么我们可以用数组存储，为每一个键绑定一个索引。

但是，如果键的取值范围很大，那么数组的方式就行不通了。哈希表就是被设计用来解决这样一个问题的~

原理

哈希表的核心设计分为两个部分：

哈希函数。哈希函数将 key 转换为数组中的一个索引。理想情况下不同的 key 都能转换成不同的索引值。当然这只是理想情况，所以我们还需要处理两个或者多个 key 都散列到相同索引值的情况 (哈希冲突)。

优秀的哈希函数需要满足这些特性(拓展)： a. 运算速度快。 b. 尽量使键平均分布 c. 逆向非常困难 d. 对数据非常敏感 e. 哈希冲突的概率非常小 哈希函数：模拟等概率随机分布事件。

处理哈希冲突。

开放地址法：线性探测法、平方探测法、再散列法拉链法 实现(无自动扩容功能)

这里，我们也采用常用的拉链法来解决哈希冲突，如下图所示：

代码 // Hash.h #include <stdint.h> #define N 10 typedef char* K; typedef char* V; typedef struct node { K key; V val; struct node* next; } Node; typedef struct { Node* table[N]; int size; int capacity; uint32_t hashseed; // 哈希种子 保证哈希桶位置映射的随机性 } HashMap; HashMap* hashmap_create(); void hashmap_destroy(HashMap* map); V hashmap_put(HashMap* map, K key, V val); V hashmap_get(HashMap* map, K key); void hashmap_delete(HashMap* map, K key); // Hash.c #include "hash.h" #include <stdlib.h> #include <stdio.h> #include <string.h> #include <time.h> HashMap* hashmap_create() { // calloc 方法 HashMap* hashmap = (HashMap*)calloc(1, sizeof(HashMap)); if (hashmap) { hashmap->size = 0; hashmap->capacity = N; hashmap->hashseed = time(NULL); } return hashmap; } // hashfunc() /* murmurhash2 */ uint32_t hash(const void* key, int len, uint32_t seed) { const uint32_t m = 0x5bd1e995; const int r = 24; uint32_t h = seed ^ len; const unsigned char* data = (const unsigned char*)key; while (len >= 4) { uint32_t k = *(uint32_t*)data; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; data += 4; len -= 4; } switch (len) { case 3: h ^= data[2] << 16; case 2: h ^= data[1] << 8; case 1: h ^= data[0]; h *= m; }; h ^= h >> 13; h *= m; h ^= h >> 15; return h; } V hashmap_put(HashMap* map, K key, V val) { // a. 如果key不存在，添加key-val，并返回NULL // b. 如果key存在，更新key关联的val，返回原来的val int idx = hash(key, strlen(key), map->hashseed) % map->capacity; // 确定哈希桶 Node* cur = map->table[idx]; while (cur) { if (strcmp(cur->key, key) == 0) { // 如果key存在 V oldVal = cur->val; cur->val = val; printf("有重复key, 已将旧值：%s 更换为新值：%s\n", oldVal, val); return oldVal; } cur = cur->next; } // cur == NULL // key不存在的情况，插入新的键值对 Node* newNode = (Node*)malloc(sizeof(Node)); newNode->key = key; newNode->val = val; newNode->next = map->table[idx]; // 头插法 map->table[idx] = newNode; // 更新哈希桶的地址 map->size++; printf("插入键值对 key: %s val: %s\n", key, val); return NULL; } V hashmap_get(HashMap* map, K key) { // a. 如果key不存在，返回NULL // b. 如果key存在，返回key关联的val int idx = hash(key, strlen(key), map->hashseed) % map->capacity; // 确定哈希桶 Node* cur = map->table[idx]; while (cur) { if (strcmp(cur->key, key) == 0) { // key 存在 printf("找到了目标键：%s 对应的值为：%s\n", cur->key, cur->val); return cur->val; } cur = cur->next; } // key不存在 printf("没找到目标键 %s 对应的键值对\n", key); return NULL; } void hashmap_delete(HashMap* map, K key) { int idx = hash(key, strlen(key), map->hashseed) % map->capacity; // 确定哈希桶 Node* cur = map->table[idx]; Node* prev = NULL; while (cur) { if (strcmp(cur->key, key) == 0) { // 找到了目标键 if (prev == NULL) // 第一个结点 map->table[idx] = cur->next; else prev->next = cur->next; printf("键值对 key: %s val: %s 已释放\n", cur->key, cur->val); free(cur); map->size--; return; } prev = cur; cur = cur->next; } // 没有找到目标键 printf("没找到目标键 %s 对应的键值对，无法删除\n", key); } void hashmap_destroy(HashMap* map) { // 1. 释放所有结点 printf("即将释放哈希表中共 %d 对键值对\n", map->size); for (int i = 0; i < map->capacity; i++) { Node* cur = map->table[i]; while (cur) { Node* freeNode = cur; cur = cur->next; printf("键值对 key: %s val: %s 已释放\n", freeNode->key, freeNode->val); free(freeNode); } // cur == NULL } // 2. 释放map->table free(map->table); // 3. 释放map结构体 free(map); printf("哈希表释放成功\n"); } // main.c #include "hash.h" #include <stdlib.h> #include <stdio.h> int main(void) { HashMap* map = hashmap_create(); hashmap_put(map, "1", "tom"); hashmap_put(map, "2", "jack"); hashmap_get(map, "1"); hashmap_put(map, "1", "jane"); hashmap_get(map, "1"); hashmap_get(map, "100"); hashmap_delete(map, "1"); hashmap_get(map, "1"); hashmap_put(map, "3", "musk"); hashmap_put(map, "4", "musk"); hashmap_put(map, "5", "musk"); hashmap_put(map, "6", "musk"); hashmap_destroy(map); return 0; } 运行结果

分析

在哈希函数保证 key 平均分布的前提下，那么哈希表的性能就取决于链表的平均长度 (L)。

put : O(L)

​ 先对 key 进行哈希，找到对应的链表，然后遍历链表，判断是添加结点还是更新结点。

get : O(L)

​ 先对 key 进行哈希，找到对应的链表，然后遍历链表，找到对应的结点。

delete : O(L)

​ 先对 key 进行哈希，找到对应的链表，然后遍历链表，删除对应的结点。

如果我们想在常数时间复杂度内, 完成哈希表的增删查操作，那么我们就得控制链表的平均长度不超过某个值。这个值我们称之为加载因子(load factor)，也就是链表平均长度可以达到的最大值。

因此，当元素个数达到一定的数目的时候，我们就需要对数组进行扩容（哈希种子也需要重新生成，防止极端情况：所有结点都在一个哈希桶中），然后把所有元素重新映射到哈希表中。

应用

哈希表的应用很广，比如 C++ 中的 unordered_map , unordered_set 和 Java 中的 HashMap, HashSet 底层的数据结构都是哈希表。再比如，常用的缓存中间件 Redis，也大量使用了哈希表数据结构。