哈希表实战：从原理到手写实现

一、先解答上次的思考题数组[5,2,8,1,3]建成大顶堆后依次取出堆顶结果8 5 3 2 1二、今天学习目标什么是哈希表、哈希函数、哈希冲突解决冲突链地址法拉链法手写实现一个简易哈希表支持插入、查找、删除操作三、什么是哈希表哈希表Hash Table也叫散列表核心思想用 key 直接计算出存储位置实现近乎 O (1) 的查找。数组下标是数字查找 O (1)哈希表key 可以是数字 / 字符串通过哈希函数转成数组下标关键概念哈希函数把 key 转成数组下标最简单index key % 表长度哈希冲突两个不同 key 算出同一个 index冲突解决最常用链地址法同一位置挂一条链表四、结构设计链地址法数组作为哈希桶每个桶是一个链表存放冲突的元素哈希表结构示意 [0] → (key,val) → NULL [1] → NULL [2] → (key,val) → (key,val) → NULL ...五、完整可运行代码简易哈希表#include stdio.h #include stdlib.h // 哈希表大小 #define SIZE 10 // 链表节点 struct Node { int key; int val; struct Node* next; }; // 哈希表数组存链表头 struct Node* hashTable[SIZE]; // 初始化哈希表 void initHashTable() { for (int i 0; i SIZE; i) hashTable[i] NULL; } // 哈希函数 int hashFunc(int key) { return key % SIZE; } // 插入 key-value void insert(int key, int val) { int index hashFunc(key); struct Node* newNode (struct Node*)malloc(sizeof(struct Node)); newNode-key key; newNode-val val; newNode-next NULL; // 头插法 newNode-next hashTable[index]; hashTable[index] newNode; } // 查找根据 key 找 val找到返回1否则0 int find(int key, int* resVal) { int index hashFunc(key); struct Node* cur hashTable[index]; while (cur ! NULL) { if (cur-key key) { *resVal cur-val; return 1; } cur cur-next; } return 0; } // 删除 key void delete(int key) { int index hashFunc(key); struct Node* cur hashTable[index]; struct Node* pre NULL; while (cur ! NULL cur-key ! key) { pre cur; cur cur-next; } if (cur NULL) return; if (pre NULL) hashTable[index] cur-next; else pre-next cur-next; free(cur); } // 打印哈希表 void printHashTable() { for (int i 0; i SIZE; i) { printf([%d] , i); struct Node* cur hashTable[i]; while (cur ! NULL) { printf(→ (%d:%d) , cur-key, cur-val); cur cur-next; } printf(\n); } } // 主函数测试 int main() { initHashTable(); insert(1, 100); insert(2, 200); insert(11, 1100); // 11%101与1冲突 insert(21, 2100); // 21%101继续冲突 printf(哈希表内容\n); printHashTable(); int val; if (find(11, val)) printf(\n找到 key11val%d\n, val); delete(11); printf(\n删除 key11 后\n); printHashTable(); return 0; }六、运行结果哈希表内容 [0] [1] → (21:2100) → (11:1100) → (1:100) [2] → (2:200) [3] [4] [5] [6] [7] [8] [9] 找到 key11val1100 删除 key11 后 [0] [1] → (21:2100) → (1:100) [2] → (2:200) [3] [4] [5] [6] [7] [8] [9]七、哈希表总结查找 / 插入 / 删除平均复杂度O(1)冲突最坏情况退化为链表O(n)工程常用unordered_map、Redis 哈希、数据库索引八、今日小练习插入 key5,15,25,7打印哈希表观察冲突位置查找 key15删除 key5