前言哈希表是面试中最常考、工程中最常用的数据结构。但很多人的理解停留在“数组链表”这个层面。今天我们不吹理论从头手写一个生产级的哈希表· 支持动态扩容· 线程安全读写锁· 泛型存储void*· 完整的测试用例---一、哈希表的核心原理1. 基本结构┌─────────────────────────────────────┐│ 哈希表 (HashTable) │├─────┬─────┬─────┬─────┬─────┬─────┬─────┤│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │└──┬──┴──┬──┴─────┴─────┴──┬──┴──┬──┴─────┘│ │ │ │▼ ▼ ▼ ▼┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐│ key │ │ key │ │ key │ │ key ││ val │ │ val │ │ val │ │ val ││ next├─►│next│ │next├─►│next│└─────┘ └─────┘ └─────┘ └─────┘· 数组每个槽位是一个链表的头· 链表解决哈希冲突拉链法· 哈希函数把key映射到数组下标2. 时间复杂度操作 平均 最坏插入 O(1) O(n)查找 O(1) O(n)删除 O(1) O(n)最坏情况发生在哈希冲突严重时所有key都映射到同一个槽位。---二、完整代码实现1. 节点定义c#include stdio.h#include stdlib.h#include string.h#include pthread.h// 哈希表节点typedef struct hash_node {char *key; // 键字符串void *value; // 值任意类型struct hash_node *next; // 链表下一个节点} hash_node_t;// 哈希表结构typedef struct {hash_node_t **buckets; // 桶数组int size; // 桶数量int count; // 存储的键值对数量pthread_rwlock_t rwlock; // 读写锁读者优先} hash_table_t;2. 哈希函数c// 经典字符串哈希函数DJB2unsigned int hash(const char *str, int table_size) {unsigned int hash 5381;int c;while ((c *str)) {hash ((hash 5) hash) c; // hash * 33 c}return hash % table_size;}3. 创建/销毁哈希表c// 创建哈希表hash_table_t *hash_table_create(int size) {hash_table_t *ht malloc(sizeof(hash_table_t));if (!ht) return NULL;ht-size size;ht-count 0;ht-buckets calloc(size, sizeof(hash_node_t*));if (!ht-buckets) {free(ht);return NULL;}pthread_rwlock_init(ht-rwlock, NULL);return ht;}// 销毁哈希表void hash_table_destroy(hash_table_t *ht) {if (!ht) return;pthread_rwlock_wrlock(ht-rwlock);for (int i 0; i ht-size; i) {hash_node_t *node ht-buckets[i];while (node) {hash_node_t *next node-next;free(node-key);free(node-value);free(node);node next;}}free(ht-buckets);pthread_rwlock_unlock(ht-rwlock);pthread_rwlock_destroy(ht-rwlock);free(ht);}4. 插入/更新c// 插入或更新键值对int hash_table_put(hash_table_t *ht, const char *key, void *value) {if (!ht || !key) return -1;unsigned int index hash(key, ht-size);pthread_rwlock_wrlock(ht-rwlock);// 查找是否已存在hash_node_t *node ht-buckets[index];while (node) {if (strcmp(node-key, key) 0) {// 更新现有节点free(node-value);node-value value;pthread_rwlock_unlock(ht-rwlock);return 0;}node node-next;}// 创建新节点node malloc(sizeof(hash_node_t));if (!node) {pthread_rwlock_unlock(ht-rwlock);return -1;}node-key strdup(key);node-value value;node-next ht-buckets[index];ht-buckets[index] node;ht-count;pthread_rwlock_unlock(ht-rwlock);// 检查是否需要扩容负载因子 0.75if ((float)ht-count / ht-size 0.75) {hash_table_resize(ht, ht-size * 2);}return 0;}5. 查找c// 查找键对应的值void *hash_table_get(hash_table_t *ht, const char *key) {if (!ht || !key) return NULL;unsigned int index hash(key, ht-size);pthread_rwlock_rdlock(ht-rwlock);hash_node_t *node ht-buckets[index];while (node) {if (strcmp(node-key, key) 0) {void *value node-value;pthread_rwlock_unlock(ht-rwlock);return value;}node node-next;}pthread_rwlock_unlock(ht-rwlock);return NULL;}6. 删除c// 删除键值对int hash_table_remove(hash_table_t *ht, const char *key) {if (!ht || !key) return -1;unsigned int index hash(key, ht-size);pthread_rwlock_wrlock(ht-rwlock);hash_node_t *node ht-buckets[index];hash_node_t *prev NULL;while (node) {if (strcmp(node-key, key) 0) {if (prev) {prev-next node-next;} else {ht-buckets[index] node-next;}free(node-key);free(node-value);free(node);ht-count--;pthread_rwlock_unlock(ht-rwlock);return 0;}prev node;node node-next;}pthread_rwlock_unlock(ht-rwlock);return -1; // 未找到}7. 动态扩容c// 扩容重新哈希int hash_table_resize(hash_table_t *ht, int new_size) {if (!ht || new_size ht-size) return -1;pthread_rwlock_wrlock(ht-rwlock);// 保存旧桶hash_node_t **old_buckets ht-buckets;int old_size ht-size;// 创建新桶ht-size new_size;ht-buckets calloc(new_size, sizeof(hash_node_t*));if (!ht-buckets) {ht-buckets old_buckets;ht-size old_size;pthread_rwlock_unlock(ht-rwlock);return -1;}// 重新哈希所有节点for (int i 0; i old_size; i) {hash_node_t *node old_buckets[i];while (node) {hash_node_t *next node-next;// 重新计算新桶中的索引unsigned int new_index hash(node-key, new_size);node-next ht-buckets[new_index];ht-buckets[new_index] node;node next;}}free(old_buckets);pthread_rwlock_unlock(ht-rwlock);return 0;}8. 遍历和统计c// 遍历所有键值对回调函数void hash_table_foreach(hash_table_t *ht,void (*callback)(const char *key, void *value, void *userdata),void *userdata) {if (!ht || !callback) return;pthread_rwlock_rdlock(ht-rwlock);for (int i 0; i ht-size; i) {hash_node_t *node ht-buckets[i];while (node) {callback(node-key, node-value, userdata);node node-next;}}pthread_rwlock_unlock(ht-rwlock);}// 获取负载因子float hash_table_load_factor(hash_table_t *ht) {if (!ht) return 0;return (float)ht-count / ht-size;}// 获取最长链表长度衡量哈希分布int hash_table_max_chain_length(hash_table_t *ht) {if (!ht) return 0;pthread_rwlock_rdlock(ht-rwlock);int max_len 0;for (int i 0; i ht-size; i) {int len 0;hash_node_t *node ht-buckets[i];while (node) {len;node node-next;}if (len max_len) max_len len;}pthread_rwlock_unlock(ht-rwlock);return max_len;}---三、测试代码c#include stdio.h#include pthread.h// 打印回调void print_entry(const char *key, void *value, void *userdata) {printf( %s - %d\n, key, *(int*)value);}int main() {// 创建哈希表hash_table_t *ht hash_table_create(8);printf(哈希表创建成功桶数: %d\n, ht-size);// 插入数据printf(\n 插入数据 \n);int *v1 malloc(sizeof(int)); *v1 100;int *v2 malloc(sizeof(int)); *v2 200;int *v3 malloc(sizeof(int)); *v3 300;hash_table_put(ht, apple, v1);hash_table_put(ht, banana, v2);hash_table_put(ht, orange, v3);printf(插入 3 个键值对\n);// 查找数据printf(\n 查找数据 \n);int *found hash_table_get(ht, banana);printf(banana: %d\n, found ? *found : -1);found hash_table_get(ht, grape);printf(grape: %d\n, found ? *found : -1);// 遍历printf(\n 遍历 \n);hash_table_foreach(ht, print_entry, NULL);// 更新printf(\n 更新 \n);int *v4 malloc(sizeof(int)); *v4 999;hash_table_put(ht, apple, v4);free(v1); // 旧的value需要手动释放found hash_table_get(ht, apple);printf(apple 更新后: %d\n, *found);// 统计信息printf(\n 统计 \n);printf(键值对数量: %d\n, ht-count);printf(负载因子: %.2f\n, hash_table_load_factor(ht));printf(最长链表长度: %d\n, hash_table_max_chain_length(ht));// 删除printf(\n 删除 \n);hash_table_remove(ht, banana);printf(删除 banana 后\n);hash_table_foreach(ht, print_entry, NULL);// 清理hash_table_destroy(ht);printf(\n哈希表已销毁\n);return 0;}运行结果哈希表创建成功桶数: 8 插入数据 插入 3 个键值对 查找数据 banana: 200grape: (null) 遍历 apple - 100banana - 200orange - 300 更新 apple 更新后: 999 统计 键值对数量: 3负载因子: 0.38最长链表长度: 1 删除 删除 banana 后apple - 999orange - 300哈希表已销毁---四、线程安全测试c#include pthread.h#include unistd.hhash_table_t *global_ht;int stop 0;// 写线程void *writer_thread(void *arg) {int id *(int*)arg;char key[32];for (int i 0; i 1000 !stop; i) {snprintf(key, sizeof(key), key_%d_%d, id, i);int *value malloc(sizeof(int));*value i;hash_table_put(global_ht, key, value);if (i % 100 0) {usleep(1000); // 让出CPU}}return NULL;}// 读线程void *reader_thread(void *arg) {int id *(int*)arg;for (int i 0; i 10000 !stop; i) {char key[32];snprintf(key, sizeof(key), key_%d_%d, id % 4, i % 1000);void *value hash_table_get(global_ht, key);// 不打印只读打印会极慢}return NULL;}int main() {global_ht hash_table_create(64);pthread_t writers[4], readers[8];int ids[12];// 启动写线程for (int i 0; i 4; i) {ids[i] i;pthread_create(writers[i], NULL, writer_thread, ids[i]);}// 启动读线程for (int i 0; i 8; i) {ids[4 i] i;pthread_create(readers[i], NULL, reader_thread, ids[4 i]);}sleep(5); // 运行5秒stop 1;// 等待所有线程结束for (int i 0; i 4; i) {pthread_join(writers[i], NULL);}for (int i 0; i 8; i) {pthread_join(readers[i], NULL);}printf(最终键值对数量: %d\n, global_ht-count);printf(负载因子: %.2f\n, hash_table_load_factor(global_ht));hash_table_destroy(global_ht);return 0;}---五、常见问题与优化问题1哈希冲突严重原因哈希函数不好或桶数太小解决· 用更好的哈希函数如上面用的DJB2· 定期检查最长链表长度超过阈值就扩容问题2内存泄漏注意· put 更新时旧的value需要调用者释放· remove 和 destroy 会释放value· 建议统一约定value由哈希表管理生命周期问题3读写锁性能读写锁适合读多写少的场景。如果写操作频繁可以· 用细粒度锁每个桶一个锁· 用无锁哈希表CAS操作优化方向优化 说明更好的哈希函数 MurmurHash、CityHash红黑树替代链表 Java8的HashMap做法链表长度8时转红黑树缓存对齐 避免伪共享内存池 预先分配节点减少malloc开销---六、总结通过这篇文章你学会了· 哈希表的底层原理数组链表· 完整的线程安全哈希表实现· 动态扩容机制· 读写锁的使用· 测试和性能分析这个哈希表代码可以直接用到你的项目里。把它改成泛型版本加上更多优化就是一个生产级的组件了。下一篇预告《手写一个LRU缓存淘汰算法》---评论区分享一下你用哈希表解决过什么实际问题