c 中的哈希表

1. 哈希是一种可以接受各种类型、大小的输入，输出一个固定长度整数的过程。
2. 你可以将哈希理解成一种特殊的映射，哈希映射，将一个理论无限的集合A映射到有限整数集合B上。

哈希函数：哈希函数是哈希过程的核心，它决定了哈希映射过程的规则。

哈希冲突：哈希是一种化无限为有限的映射，允许出现多对一，但绝不允许出现一对多。若映射中出现多对一，就是哈希冲突。哈希冲突可以减少，但绝不可能没有。

哈希函数

/* murmur_hash2 */
static 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;
}

 

MurmurHash 是一种非加密哈希函数，适用于一般的哈希检索操作。它以高运行速度和分布均匀性而闻名。其中uint32_t表示无符号 32 位整型，要想使用它需要包含头文件<stdint.h>。

该函数调用需要三个参数：

1. void* key，也就是需要计算哈希值的key元素。此形参的类型是void*，这意味着它可以传入任何类型的数据，提高了函数的通用性。

   1. 如果key是基本数据类型，那就传入指向基本数据类型的指针
   2. 如果key本身就是一个指针类型，比如字符串，那么就直接传入这个指针就可以了。
2. int len，表示哈希函数要处理的key的大小长度。key若是字符串可以使用函数strlen计算，若是其它类型可以使用sizeof计算。

3. uint32_t seed，种子值。

   1. 此哈希函数会根据key和seed共同生成一个哈希值
   2. 不同的种子值会导致相同的数据产生不同的哈希值。需要注意的是，在程序一次运行中，同一个哈希表应该具有相同的种子值！
   3. 最常见的设置种子值的方式就是用时间戳，也就是time(NULL);函数调用。这对于大家而言，应该都比较熟悉了。

 拉链法实现固定容量的哈希表

#ifndef HASH_MAP_H
#define HASH_MAP_H#include <stdint.h> // 包含它是为了使用别名uint32_t
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define HASHMAP_CAPACITY 10 // 哈希表中数组的长度固定是10// 此时哈希表用于存储字符串类型的键值对
typedef char *KeyType;
typedef char *ValueType;// 键值对结点
typedef struct node_s {KeyType key;ValueType val;struct node_s *next;
} KeyValueNode;typedef struct {// 哈希桶KeyValueNode *buckets[HASHMAP_CAPACITY];    // 直接给定哈希桶的数量是10个// 哈希函数需要的种子值uint32_t hash_seed;
} HashMap;// 创建一个固定容量的哈希表
HashMap *hashmap_create();
// 销毁一个哈希表
void hashmap_destroy(HashMap *map);
// 插入一个键值对
ValueType hashmap_put(HashMap *map, KeyType key, ValueType val);
// 查询一个键值对
ValueType hashmap_get(HashMap *map, KeyType key);
// 删除某个键值对
bool hashmap_remove(HashMap *map, KeyType key);#endif // !HASH_MAP_H

 

实现创建哈希表

// 创建一个固定容量的哈希表
HashMap *hashmap_create() {HashMap *map = calloc(1, sizeof(HashMap));if (map == NULL) {printf("error: calloc failed in hashmap_create.\n");exit(-1);}map->hash_seed = time(NULL);return map;
}

 

实现哈希表销毁

// 销毁一个哈希表
void hashmap_destroy(HashMap *map) {// 遍历数组,然后销毁哈希桶中的链表,最后销毁HashMap结构体for (size_t i = 0; i < HASHMAP_CAPACITY; i++) {KeyValueNode *curr = map->buckets[i];while (curr != NULL) {KeyValueNode *tmp = curr->next;free(curr);curr = tmp;}}free(map);
}

 

实现插入键值对

// 插入一个键值对
ValueType hashmap_put(HashMap *map, KeyType key, ValueType val) {// 1.计算哈希值确定哈希桶的位置int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;// 2.遍历哈希桶，查找Key是否重复KeyValueNode *curr = map->buckets[idx];while (curr != NULL) {// 比较字符串if (strcmp(key, curr->key) == 0) {// key已存在,更新value,并返回旧valueValueType old_val = curr->val;curr->val = val;return old_val;}curr = curr->next;}// 3.只要Key不重复肯定都要插入，于是无脑使用链表头插法插入结点KeyValueNode *new_node = malloc(sizeof(KeyValueNode));if (new_node == NULL) {printf("Error: malloc failed in hashmap_put.\n");exit(1);}new_node->key = key;    // key和val都是指针类型，可以直接"="赋值new_node->val = val;// 链表头插法new_node->next = map->buckets[idx]; // 新结点指向原本的第一个结点map->buckets[idx] = new_node;   // 更新头指针// 没有更新键值对返回空指针return NULL;
}

 

实现键值对查询

// 查询一个键值对
ValueType hashmap_get(HashMap *map, KeyType key) {// 1.计算哈希值确定哈希桶的位置int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;// 2.遍历哈希桶，查找Key是否存在KeyValueNode *curr = map->buckets[idx];while (curr != NULL) {// 比较字符串if (strcmp(key, curr->key) == 0) {// 已找到目标键值对return curr->val;}curr = curr->next;}// 目标键值对不存在return NULL;
}

 

实现键值对删除

// 删除某个键值对
bool hashmap_remove(HashMap *map, KeyType key) {// 1.计算哈希值确定哈希桶的位置int idx = hash(key, strlen(key), map->hash_seed) % HASHMAP_CAPACITY;// 2.初始化两个指针,用于删除结点KeyValueNode *curr = map->buckets[idx];KeyValueNode *prev = NULL;// 3.遍历链表查找目标Keywhile (curr != NULL) {// 比较字符串if (strcmp(key, curr->key) == 0) {// 已找到目标键值对if (prev == NULL) {// 删除的是第一个结点map->buckets[idx] = curr->next;}else{// 删除的不是第一个结点prev->next = curr->next;}// free结点free(curr);return true;    // 删除成功}prev = curr;        // 更新prev为当前节点curr = curr->next;  // 当前结点向后移动}// 没找到目标键值对,删除失败return false;
}

 

负载因子(Load Factor ）

 一般来说，负载因子在0.7/0.75以下时，哈希表处在健康、性能优秀的状态。但一旦超出这个阈值，就意味着哈希冲突会增多，链表平均长度变长，从而导致性能下降。

1. 在最佳情况下，即哈希函数均匀分布且冲突较少时，哈希表的插入、查询和删除操作的效率非常高，接近 O(1)。
2. 在最坏情况下，特别是哈希冲突很多导致链表过长时，这些操作的效率会降低，接近 O(L)，因为此时的哈希表访问几乎相当于链表的访问。

 实现动态哈希表

头文件

#ifndef DYNAMIC_HASHMAP_H
#define DYNAMIC_HASHMAP_Htypedef char *KeyType;
typedef char *ValueType;#include <stdint.h>typedef struct node_s {KeyType key;ValueType val;struct node_s *next;
} KeyValueNode;typedef struct {KeyValueNode **buckets;     // 此时哈希桶是一个动态数组，指向char*元素的指针，所以是一个二级指针int size;               // 键值对的个数int capacity;           // 数组的长度uint32_t hash_seed;     // 哈希函数需要的种子值
} DynamicHashMap;// 创建一个固定容量的哈希表
DynamicHashMap *hashmap_create();
// 销毁一个哈希表
void hashmap_destroy(DynamicHashMap *map);
// 插入一个键值对
ValueType hashmap_put(DynamicHashMap *map, KeyType key, ValueType val);
// 查询一个键值对
ValueType hashmap_get(DynamicHashMap *map, KeyType key);
// 删除某个键值对
bool hashmap_remove(DynamicHashMap *map, KeyType key);#endif // !DYNAMIC_HASHMAP_H

 

实现创建和销毁动态哈希表

#include "dynamic_hashmap.h"
#define DEFAULT_CAPACITY 8  // 哈希表的初始默认容量是8// 创建一个固定容量的哈希表
DynamicHashMap *hashmap_create() {DynamicHashMap *map = malloc(sizeof(DynamicHashMap));if (map == NULL) {printf("Error: malloc failed in hashmap_create\n");exit(1);}map->buckets = calloc(DEFAULT_CAPACITY, sizeof(KeyValueNode *));if (map->buckets == NULL) {// 不要忘记先free结构体free(map);printf("Error: calloc failed in hashmap_create\n");exit(1);}// 初始化其它成员map->size = 0;map->capacity = DEFAULT_CAPACITY;map->hash_seed = time(NULL);return map;
}// 销毁一个哈希表
void hashmap_destroy(DynamicHashMap *map) {// 1.先遍历动态数组销毁链表的每一个结点for (int i = 0; i < map->capacity; i++) {KeyValueNode *curr = map->buckets[i];while (curr != NULL) {KeyValueNode *tmp = curr->next;free(curr);curr = tmp;}}// 2.再销毁动态数组free(map->buckets);// 3.最后销毁哈希表结构体free(map);
}

 

实现插入和扩容功能

#define LOAD_FACTOR_THRESHOLD  0.75     // 负载因子的阈值
#define CAPACITY_THRESHOLE 1024     // 数组容量的阈值/* murmur_hash2 */
static 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;
}static void rehash(KeyValueNode *curr, KeyValueNode **new_table, int new_capacity, uint32_t seed) {// 计算 key 的哈希值int len = strlen(curr->key);int idx = hash(curr->key, len, seed) % new_capacity;// 头插法curr->next = new_table[idx];new_table[idx] = curr;
}// 对哈希表进行扩容操作
static void grow_capacity(DynamicHashMap *map) {/** 扩容策略：* 1.如果容量没有达到阈值，那就每次将长度扩大为原先的2倍* 2.如果容量达到阈值，此时哈希表已经很长了，为了避免扩容过程性能损耗过大*   所以扩容保守一些，每次只扩容阈值长度的容量** 扩容的过程：* 1.每个键值对结点都要重新计算哈希值，重新映射到新哈希桶中(新数组)* 2.原先的动态数组的链表很复杂，难以进行重哈希操作，建议直接丢弃它* 重新创建一个新动态数组*/int new_capacity =(map->capacity <= CAPACITY_THRESHOLE) ?(map->capacity << 1) :(map->capacity + CAPACITY_THRESHOLE);// 动态数组扩容需要使用 callocKeyValueNode **new_buckets = calloc(new_capacity, sizeof(KeyValueNode *));if (new_buckets == NULL) {printf("Error: calloc failed in grow_capacity\n");exit(1);}// 每次扩容都更改一次哈希种子，提高安全性uint32_t seed = time(NULL);// 将所有键值对重新映射到新数组中for (int i = 0; i < map->capacity; i++) {KeyValueNode *curr = map->buckets[i];while (curr != NULL) {KeyValueNode *next = curr->next;// 重新进行哈希映射rehash(curr, new_buckets, new_capacity, seed);curr = next;}}// 将旧动态数组free，但是注意不要free键值对结点，结点已经被链接到新数组中了。free(map->buckets);// 更新 HashMap 的信息map->buckets = new_buckets;map->capacity = new_capacity;map->hash_seed = seed;
}// 插入一个键值对
// 1. 如果key不存在，则添加键值对结点
// 2. 如果key存在，则更新val，将旧的val返回
ValueType hashmap_put(DynamicHashMap *map, KeyType key, ValueType val) {// 计算key的哈希值确定存储位置int idx = hash(key, strlen(key), map->hash_seed) % (map->capacity);// 遍历链表KeyValueNode *curr = map->buckets[idx];while (curr != NULL) {if (strcmp(key, curr->key) == 0) {// 更新 key 关联的 val, 并将旧的value返回ValueType old_val = curr->val;curr->val = val;return old_val;}curr = curr->next;} // while循环结束时, curr是一个NULL// 键值对不存在，即需要将键值对插入// 插入操作前需要计算当前哈希表的负载因子double load_factor = (1.0 * map->size) / (map->capacity);if (load_factor >= LOAD_FACTOR_THRESHOLD) {// 当前哈希表负载因子已达到阈值，将动态数组进行扩容grow_capacity(map);// 数组长度已变，需要再哈希确定当前键值对的存储位置idx = hash(key, strlen(key), map->hash_seed) % (map->capacity);}// 开始插入新键值对KeyValueNode *new_node = malloc(sizeof(KeyValueNode));if (new_node == NULL) {printf("Error: malloc failed in hashmap_put\n");exit(1);}// 初始化结点new_node->key = key;new_node->val = val;// 链表的头插法new_node->next = map->buckets[idx];map->buckets[idx] = new_node;// 不要忘记更新sizemap->size++;return NULL;
}

 

访问和删除键值对

// 查询一个键值对
ValueType hashmap_get(DynamicHashMap *map, KeyType key) {// 计算key的哈希值，从而确定哈希桶int idx = hash(key, strlen(key), map->hash_seed) % map->capacity;// 遍历哈希桶的链表，判断 key 是否存在KeyValueNode *curr = map->buckets[idx];while (curr != NULL) {if (strcmp(key, curr->key) == 0) {// 找到目标键值对return curr->val;}curr = curr->next;} // curr == NULL// 没找到目标键值对return NULL;
}// 删除某个键值对
bool hashmap_remove(DynamicHashMap *map, KeyType key) {// 计算key的哈希值，从而确定哈希桶int idx = hash(key, strlen(key), map->hash_seed) % map->capacity;// 初始化两个指针，一个指向链表当前结点，一个指向当前结点的前驱KeyValueNode *prev = NULL;KeyValueNode *curr = map->buckets[idx];while (curr != NULL) {if (strcmp(key, curr->key) == 0) {// 找到了要删除的节点if (prev == NULL) {// 删除的是哈希桶的第一个节点，于是更新头指针map->buckets[idx] = curr->next;}else {// 删除的是哈希桶中的非第一个节点，只需要让当前结点的前驱结点指向当前结点的后继prev->next = curr->next;}free(curr);map->size--;return true;}// 继续遍历链表prev = curr;curr = curr->next;}// 没找到指定key的节点return false;
}

 

扩展：利用哈希表判断单链表有环

头文件

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>#define CAPACITY 10  // 哈希表的底层数组长度是10typedef struct node {int data;struct node *next;
}Node;  // 哈希表当中存储的链表结点类型// 此哈希表只存储键,不存储value
// key值存储链表结点的指针
typedef Node *KeyType;// 键值对结点，此时无需存储值了
typedef struct node_s {KeyType key;    // 键struct node_s *next;
} HashNode; // 键值对结点类型typedef struct {HashNode *buckets[CAPACITY];uint32_t hash_seed;
} HashMap;    // 哈希表结构体类型// 创建一个固定容量的哈希表
HashMap *hashmap_create();
// 销毁哈希表
void hashmap_destroy(HashMap *map);/*尝试将链表结点的指针(地址)插入哈希表若发现结点已存入哈希表, 则函数返回true若结点未存入, 则将结点地址存入哈希表并返回false
*/
bool hashmap_put(HashMap *map, KeyType key);

该哈希表的实现代码如下所示：

#include "hash_map.h"/* murmur_hash2 */
static 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;
}// 创建一个固定容量的哈希表
HashMap *hashmap_create() {HashMap *map = calloc(1, sizeof(HashMap));if (map == NULL) {printf("error: calloc failed in hashmap_create.\n");return NULL;}map->hash_seed = time(NULL);return map;
}// 销毁哈希表
void hashmap_destroy(HashMap *map) {// 遍历每一个哈希桶(也就是遍历数组的每一个元素)，逐一销毁链表结点，最后销毁结构体自身for (int i = 0; i < CAPACITY; i++) {HashNode *curr = map->buckets[i];while (curr != NULL) {HashNode *tmp = curr->next;free(curr);curr = tmp;}}free(map);
}/*该函数会将链表结点的地址作为一个结点key值,存入哈希表当中在存入的过程中,如果发现key值重复,说明有环,直接返回true如果key值不重复,那就将key结点正常存入哈希表,并且返回false
*/
bool hashmap_put(HashMap *map, KeyType key) {// 1.根据key这个结点地址数据来计算哈希值,确定哈希桶的位置int idx = hash(key, sizeof(KeyType), map->hash_seed) % CAPACITY;// 2.遍历哈希桶,确定这个结点地址是否已经出现HashNode *curr = map->buckets[idx];while (curr != NULL) {if (key == curr->key) {// 当前结点已经重复出现了,说明有环return true;}curr = curr->next;}// 3.key是不存在的,于是新增这个结点HashNode *new_node = malloc(sizeof(HashNode));if (new_node == NULL) {printf("error: malloc failed in hashmap_put.\n");exit(-1);}new_node->key = key;    // 由于key是Node结点指针类型,是地址,所以可以直接用=赋值// 4.执行链表的头插法,将新结点链接到链表中new_node->next = map->buckets[idx];map->buckets[idx] = new_node;return false;   // 表示当前结点还没有重复,所以插入哈希表成功了
}

// 利用哈希表来判断单链表有环
bool has_circle(Node *head) {// 1.创建一个哈希表HashMap *map = hashmap_create();// 2.遍历整条单链表,并且将每一个结点的地址存入哈希表Node *curr = head;while (curr != NULL) {if (hashmap_put(map, curr)) {// 已经存储了重复结点,有环hashmap_destroy(map);return true;}curr = curr->next;}// 如果while循环能够结束,且能够执行到这里,说明链表没环hashmap_destroy(map);return false;
}