哈希表（C语言版）

哈希表

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

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

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

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

原理

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

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

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

2. 处理哈希冲突。

   • 开放地址法：线性探测法、平方探测法、再散列法
   • 拉链法

实现(无自动扩容功能)

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

代码

// Hash.h#include <stdint.h>
#define N 10typedef 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，返回原来的valint 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关联的valint 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->tablefree(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，也大量使用了哈希表数据结构。