哈希表：从O(1)查找到冲突解决全解析

引言在前面的数据结构系列中我们学习了各种树结构——BST、AVL、红黑树、B 树、B 树。它们通过比较来查找最优能做到 O(log n)。今天要讲的哈希表走的是完全不同的路线通过映射函数把键直接映射到存储位置理想情况下查找只需O(1)。哈希表是计算机科学中最实用的数据结构之一。你用的unordered_map、Redis 的键值存储、数据库的哈希索引、布隆过滤器……底层全都是哈希表的变体。第一部分哈希表的基本概念一、核心三要素要素说明示例键 (Key)待存储数据的标识张三、1001、user_id哈希函数把键映射成数组下标的函数hash(张三) 5桶数组实际存储数据的数组arr[5] 90理想情况不同的键映射到不同的下标查找就是 O(1) 的数组访问。现实问题键的空间远大于数组大小冲突不可避免——两个不同的键可能映射到同一个下标。二、哈希表的核心问题第二部分哈希函数一、好的哈希函数的特征计算快O(1) 时间内完成分布均匀尽量避免不同的键映射到同一位置确定性同一个键总是得到同一个哈希值二、常见哈希函数1. 除留余数法最常用// 取模运算m 通常选质数 int hash(int key, int m) { return key % m; }为什么 m 选质数如果 m 10非质数键以 0 结尾的全都映射到 0分布不均匀。m 选质数能减少这种规律性冲突。2. 乘法哈希// 乘以一个常数 A0 A 1取小数部分 × m // 常用 A (√5 - 1) / 2 ≈ 0.6180339887 int hash(int key, int m) { double A 0.6180339887; double frac key * A - (int)(key * A); // 取小数部分 return (int)(m * frac); }3. 字符串哈希BKDR Hash// seed 常用 31、131、1313、13131 等 unsigned int BKDRHash(const char* str) { unsigned int seed 131; unsigned int hash 0; while (*str) { hash hash * seed (*str); } return hash; }为什么用 3131 是质数hash * 31可以被编译器优化为(hash 5) - hash计算极快。第三部分解决冲突一、拉链法Chaining—— 最常用思路每个桶存放一个链表或其他容器冲突的元素挂在同一链表中。特点实现简单删除方便负载因子可以 1桶数可以小于元素数最坏情况退化为链表 O(n)二、开放定址法Open Addressing思路冲突时在数组中找下一个空位置。线性探测// 冲突后依次检查 i1, i2, i3... int probe(int hash, int i, int m) { return (hash i) % m; }二次探测// 冲突后检查 i1², i2², i3²... int probe(int hash, int i, int m) { return (hash i * i) % m; }双哈希// 冲突后用第二个哈希函数计算步长 int probe(int hash1, int hash2, int i, int m) { return (hash1 i * hash2) % m; }方法插入查找删除问题线性探测O(1) 均摊O(1) 均摊需标记删除一次聚集连续占用二次探测O(1) 均摊O(1) 均摊需标记删除二次聚集双哈希O(1) 均摊O(1) 均摊需标记删除实现稍复杂拉链法O(1) 均摊O(1) 均摊直接删需要额外指针空间第四部分负载因子与扩容一、负载因子冲突解决方法推荐 α 上限拉链法0.75 ~ 1.0线性探测0.5 ~ 0.7二次探测0.5二、扩容时机当 α 超过阈值时创建更大的数组将所有元素重新哈希Rehash到新数组。扩容的代价是 O(n)但均摊下来每次插入仍是 O(1)。// 扩容伪代码 if (count / capacity LOAD_FACTOR) { new_capacity capacity * 2; // 扩容为原来 2 倍 new_table 创建新数组(new_capacity); for (旧表中的每个元素) { 重新哈希插入到 new_table; } 释放旧表; 使用新表; }第五部分完整代码实现拉链法#include stdio.h #include stdlib.h #include string.h #define INIT_CAPACITY 8 #define LOAD_FACTOR 0.75 // 键值对节点 typedef struct HashNode { int key; int value; struct HashNode* next; } HashNode; // 哈希表 typedef struct { HashNode** buckets; int capacity; int size; } HashMap; // 哈希函数 int hash(int key, int capacity) { return key % capacity; } // 创建哈希表 HashMap* createHashMap() { HashMap* map (HashMap*)malloc(sizeof(HashMap)); map-capacity INIT_CAPACITY; map-size 0; map-buckets (HashNode**)calloc(INIT_CAPACITY, sizeof(HashNode*)); return map; } // 插入或更新 void put(HashMap* map, int key, int value) { int idx hash(key, map-capacity); // 查找是否已存在 HashNode* cur map-buckets[idx]; while (cur) { if (cur-key key) { cur-value value; // 更新 return; } cur cur-next; } // 不存在头插法插入新节点 HashNode* node (HashNode*)malloc(sizeof(HashNode)); node-key key; node-value value; node-next map-buckets[idx]; map-buckets[idx] node; map-size; } // 查找返回 value未找到返回 -1 int get(HashMap* map, int key) { int idx hash(key, map-capacity); HashNode* cur map-buckets[idx]; while (cur) { if (cur-key key) return cur-value; cur cur-next; } return -1; } // 删除 void removeKey(HashMap* map, int key) { int idx hash(key, map-capacity); HashNode* cur map-buckets[idx]; HashNode* prev NULL; while (cur) { if (cur-key key) { if (prev NULL) { map-buckets[idx] cur-next; // 删除头节点 } else { prev-next cur-next; // 删除中间节点 } free(cur); map-size--; return; } prev cur; cur cur-next; } } // 释放 void freeHashMap(HashMap* map) { for (int i 0; i map-capacity; i) { HashNode* cur map-buckets[i]; while (cur) { HashNode* tmp cur; cur cur-next; free(tmp); } } free(map-buckets); free(map); } // 测试 int main() { HashMap* map createHashMap(); put(map, 1, 100); put(map, 2, 200); put(map, 9, 900); // 和 1 冲突如果 capacity8都映射到 1 printf(key1 → %d\n, get(map, 1)); // 100 printf(key2 → %d\n, get(map, 2)); // 200 printf(key9 → %d\n, get(map, 9)); // 900 printf(key3 → %d\n, get(map, 3)); // -1不存在 removeKey(map, 2); printf(删除后 key2 → %d\n, get(map, 2)); // -1 freeHashMap(map); return 0; }第六部分哈希表的实际应用应用说明unordered_map/unordered_setC STL 哈希容器Redis 键值存储全局哈希表存储所有 key数据库哈希索引MySQL Memory 引擎的哈希索引布隆过滤器判断元素是否可能存在用多个哈希函数LRU 缓存unordered_map 双向链表负载均衡一致性哈希第七部分哈希表 vs 平衡树对比项哈希表平衡树红黑树查找O(1) 平均O(log n)插入O(1) 平均O(log n)删除O(1) 平均O(log n)有序遍历❌ 无序✅ 有序范围查询❌ 不支持✅ 支持内存占用较大桶数组链表指针较小只存数据和左右指针最坏情况O(n)O(log n)C 对应unordered_mapmap总结一、核心要点要点内容哈希函数把键映射成数组下标要求计算快、分布均匀冲突解决拉链法链表和开放定址法线性探测/二次探测/双哈希负载因子元素数/桶数超过阈值需要扩容并 Rehash时间复杂度均摊 O(1)最坏 O(n)全部冲突到同一桶二、一句话记忆哈希表用哈希函数把键映射成数组下标实现 O(1) 查找通过拉链法或开放定址法解决冲突负载因子过大时扩容并重新哈希所有元素。