当前位置：首页 > news >正文

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

news 2026/6/18 14:07:10

一、先解答上次的思考题

数组[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%10=1，与1冲突 insert(21, 2100); // 21%10=1，继续冲突 printf("哈希表内容：\n"); printHashTable(); int val; if (find(11, &val)) printf("\n找到 key=11，val=%d\n", val); delete(11); printf("\n删除 key=11 后：\n"); printHashTable(); return 0; }

六、运行结果

哈希表内容： [0] [1] → (21:2100) → (11:1100) → (1:100) [2] → (2:200) [3] [4] [5] [6] [7] [8] [9] 找到 key=11，val=1100 删除 key=11 后： [0] [1] → (21:2100) → (1:100) [2] → (2:200) [3] [4] [5] [6] [7] [8] [9]