哈希表入门教程：从零搭建完整结构

一、什么是哈希表1.核心定义哈希表 数组哈希函数冲突解决哈希表是一种通过哈希函数将「键Key」映射到「索引Index」从而实现O (1) 平均时间复杂度查找、插入、删除的数据结构。2.核心三要素1键key 要存储的数据标识如数字、字符串、对象。2哈希函数把 Key 转换成数组下标的函数核心3哈希表底层数组利用数组随机访问特性3.核心优势1平均查找 / 插入 / 删除 O(1)2最坏O (n)3对比数组查找 O (n)链表查找 O (n)二叉搜索树查找 O (logn)哈希表是最快的查找数据结构二、哈希函数和哈希冲突1.哈希函数Hash Function作用key - 数组索引公式index hashkey% 数组长度2.哈希函数高频坑点1不处理负数key-下标越界崩溃// ❌ 错误哈希函数 int bad_hash1(HashTable* ht, int key) { return key % ht-size; // 负数key → 负数下标 }错误原因key -1 % 10 -1→ 数组下标不能为负程序直接崩溃。正确代码// ✅ 正确哈希函数 int good_hash(HashTable* ht, int key) { if (key 0) key -key; // 必须先转正数 return key % ht-size; }2哈希函数分布不均 - 冲突爆炸// ❌ 错误哈希函数所有key都返回同一个下标 int bad_hash2(HashTable* ht, int key) { return 0; // 所有元素都存在下标0 → 链表变成长链O(n)复杂度 }错误原因冲突严重哈希表退化为链表。正确代码// 正确哈希函数保证分布均匀 处理负数 int hash(HashTable* ht, int key) { // 1. 处理负数key避免负数下标越界 if (key 0) { key -key; } // 2. 取余运算将key映射到[0, size-1]的合法下标 // 配合质数大小的哈希表能最大程度保证分布均匀 return key % ht-size; }(3)哈希表大小用偶数 - 冲突增多// ❌ 不推荐 HashTable* ht createHashTable(10); // 偶数取余分布不均 // ✅ 推荐质数大小 HashTable* ht createHashTable(11); // 质数分布均匀冲突最少3.哈希冲突定义两个不同的 Key通过哈希函数算出了同一个索引。无法完全避免只能解决冲突。4.哈希冲突的解决办法1链地址法链表数组数组每个位置存一个链表 / 红黑树冲突时把元素追加到链表后面优点实现简单无空间浪费2开放寻址法纯数组冲突时向后找空位置存放线性探测 / 二次探测优点无链表内存连续缺点删除麻烦容易堆积三、哈希表基本操作总结1.链表节点typedef struct Node{ int key; //键 int value; //值 struct Node* next; //用于解决指针冲突 }Node;2.哈希表结构typedef struct HashTable{ int size; //数组长度 Node** table; //指针数组存链表头 }HashTable;3.哈希函数核心公式正确哈希函数abs(key) % size作用把任意整数 → 合法下标 [0, size-1]必须处理负数否则下标越界崩溃int hash(HashTable* ht, int key) { if (key 0) key -key; // 负数转正数 return key % ht-size; // 取余映射下标 }4.创建哈希表HashTable* createHashTable(int size) { HashTable* ht (HashTable*)malloc(sizeof(HashTable)); ht-size size; ht-table (Node**)malloc(sizeof(Node*) * size); // 初始化所有链表为空 for (int i 0; i size; i) { ht-table[i] NULL; } return ht; }5.创建节点Node* createNode(int key, int value) { Node* node (Node*)malloc(sizeof(Node)); node-key key; node-value value; node-next NULL; return node; }6.插入冲突处理void insert(HashTable* ht, int key, int value) { int index hash(ht, key); // 计算下标 Node* head ht-table[index]; // 遍历key已存在则覆盖 Node* cur head; while (cur) { if (cur-key key) { cur-value value; return; } cur cur-next; } // 头插法新节点放链表头部 Node* newNode createNode(key, value); newNode-next head; ht-table[index] newNode; }7.查找int search(HashTable* ht, int key) { int index hash(ht, key); Node* cur ht-table[index]; // 遍历链表查找 while (cur) { if (cur-key key) return cur-value; cur cur-next; } return -1; // 未找到 }8.删除void deleteKey(HashTable* ht, int key) { int index hash(ht, key); Node* prev NULL; Node* cur ht-table[index]; // 查找节点 while (cur cur-key ! key) { prev cur; cur cur-next; } if (!cur) return; // 不存在直接返回 // 删除节点 if (!prev) ht-table[index] cur-next; // 删头节点 else prev-next cur-next; // 删中间节点 free(cur); }9.销毁防止内存泄露void destroyHashTable(HashTable* ht) { for (int i 0; i ht-size; i) { Node* cur ht-table[i]; while (cur) { Node* temp cur; cur cur-next; free(temp); } } free(ht-table); free(ht); }10.一般经常会使用到的方法int hash[N]{0} 来进行下标映射。四、哈希表算法分类哈希表的核心思想只有一个把 key 转成下标然后快速存、快速查。数组哈希做题比较常用它把 “链表” 扔掉直接用一个数组当下标映射思想还是哈希表key → 下标 → 存值。1.两数之和查找配对// 两数之和数组哈希版适合数据范围小的场景 int* twoSum(int* nums, int numsSize, int target, int* returnSize) { *returnSize 2; int* res (int*)malloc(2 * sizeof(int)); // 数组哈希key数值value下标偏移量处理负数 int hash[200001]; memset(hash, -1, sizeof(hash)); // 初始化为-1表示未访问 for (int i 0; i numsSize; i) { int complement target - nums[i]; int idx complement 100000; // 找到配对的数返回下标 if (hash[idx] ! -1) { res[0] hash[idx]; res[1] i; return res; } // 把当前数存入哈希 int cur_idx nums[i] 100000; hash[cur_idx] i; } return res; }一次遍历哈希表 O (1) 查找时间 O (n)。2.频率统计计数// 小写字母统计26大小 int hash[26] {0}; for (int i 0; i strlen(s); i) { hash[s[i] - a]; // 字符转下标计数1 } // 全ASCII字符统计128大小万能 int hash[128] {0}; for (int i 0; i strlen(s); i) { hash[(unsigned char)s[i]]; }3.去重// 数字去重带偏移量处理负数 int hash[200001] {0}; // 覆盖-100000~100000 for (int i 0; i numsSize; i) { int idx nums[i] 100000; // 负数偏移转正数下标 if (hash[idx]) return true; // 已存在→有重复 hash[idx] 1; // 标记已访问 } return false;4.键值映射bool isIsomorphic(char* s, char* t) { int map_s[128], map_t[128]; memset(map_s, -1, sizeof(map_s)); memset(map_t, -1, sizeof(map_t)); int len strlen(s); for (int i 0; i len; i) { unsigned char c1 s[i], c2 t[i]; // 双向映射不一致返回false if (map_s[c1] ! map_t[c2]) return false; // 建立双向映射 map_s[c1] i; map_t[c2] i; } return true; }5.前缀和哈希表int subarraySum(int* nums, int numsSize, int k) { // 数组哈希记录前缀和出现的次数偏移量处理负数 int hash[200001] {0}; hash[100000] 1; // 初始前缀和为0出现1次 int preSum 0, count 0; for (int i 0; i numsSize; i) { preSum nums[i]; // 查找preSum - k出现的次数 int target preSum - k; int idx target 100000; if (idx 0 idx 200001) { count hash[idx]; } // 更新当前前缀和的次数 int cur_idx preSum 100000; hash[cur_idx]; } return count; }6.滑动窗口去重int lengthOfLongestSubstring(char* s) { int hash[128]; // 记录字符最后出现的位置 memset(hash, -1, sizeof(hash)); int left 0, maxLen 0; int len strlen(s); for (int right 0; right len; right) { unsigned char c s[right]; // 字符已在窗口内移动左指针到重复位置的下一位 if (hash[c] left) { left hash[c] 1; } // 更新字符的最新位置 hash[c] right; maxLen (right - left 1) maxLen ? (right - left 1) : maxLen; } return maxLen; }五、高频出错点1.C 语言必须手动 free → 内存泄漏先 free 链表 → 再 free 数组 → 最后 free 哈希表2.直接访问数组下标 → 空指针崩溃ht-table[index]-key错误必须用search()函数安全查找正确3.插入重复 key 不覆盖 → 数据错误插入前必须遍历检查相同 key 覆盖 value4.认为哈希表永远 O (1) → 认知错误哈希冲突严重时 O (n)