数据结构 - 哈希表
哈希表（Hash Table）是一种通过哈希函数将键映射到数组中特定位置，从而实现平均 O(1) 时间复杂度查找、插入和删除操作的数据结构。
哈希函数与哈希冲突
哈希表原理 — 哈希函数映射
key=1
key=2
key=11
→
hash(key) = key % 10
→
[0]
[1] 1,11
[2] 2
[3]
[4]
[5]
[6]
[7]
[8]
[9]
红色槽位 = 冲突！key=1 和 key=11 映射到同一位置
哈希函数的设计目标是将任意输入（键）转换为一个固定范围内的整数（数组下标）。
一个好的哈希函数应具备计算速度快、结果分布均匀的特点。
然而，由于哈希表的容量总是有限的，哈希冲突——两个不同的键被映射到同一位置——是不可避免的现象。
冲突解决方法
哈希冲突解决 — 链地址法 vs 开放寻址法
链地址法
每槽位存链表，冲突键追加
优点：实现简单，删除方便
缺点：指针开销，缓存不友好
负载因子可超过 1.0
开放寻址法
冲突时探测下一个空位
优点：无指针，缓存友好
缺点：删除需惰性标记
负载因子需 ≤ 0.7
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 链地址法 | 每个槽位存一个链表，冲突的键追加到链表中 | 实现简单、删除方便、负载因子可大于 1 | 额外指针开销、缓存不友好 |
| 开放寻址法 | 冲突时按探测规则在数组中寻找下一个空位 | 无需指针，缓存友好 | 删除复杂（需惰性删除）、负载因子需控制 |
开放寻址法中，删除元素时不能简单地将槽位置空，否则会破坏后续元素的查找链。通常的做法是使用"惰性删除"——标记该位置为"已删除"而非"空"。
链地址法实现
实例
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* 哈希表容量 */
/* 哈希表节点 */
struct HashNode {
int key;
int value;
struct HashNode* next; /* 指向同一槽位的下一个节点 */
};
/* 哈希函数：简单的取模法 */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* 插入键值对（链地址法）
时间复杂度：O(1) 平均，O(n) 最坏（所有键映射到同一槽） */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* 头插法 */
table[index] = newNode;
}
/* 查找：根据键获取值
先计算哈希值定位槽位，再遍历链表查找匹配的键 */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* 找到 */
}
cur = cur->next;
}
return -1; /* 未找到 */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* 初始化所有槽为空 */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — 与 key=1 冲突！ */
printf("key=1 → %d\n", search(table, 1)); /* 输出: 100 */
printf("key=2 → %d\n", search(table, 2)); /* 输出: 200 */
printf("key=11 → %d\n", search(table, 11)); /* 输出: 300 (链地址法正确处理了冲突) */
printf("key=99 → %d\n", search(table, 99)); /* 输出: -1 (未找到) */
return 0;
}
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* 哈希表容量 */
/* 哈希表节点 */
struct HashNode {
int key;
int value;
struct HashNode* next; /* 指向同一槽位的下一个节点 */
};
/* 哈希函数：简单的取模法 */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* 插入键值对（链地址法）
时间复杂度：O(1) 平均，O(n) 最坏（所有键映射到同一槽） */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* 头插法 */
table[index] = newNode;
}
/* 查找：根据键获取值
先计算哈希值定位槽位，再遍历链表查找匹配的键 */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* 找到 */
}
cur = cur->next;
}
return -1; /* 未找到 */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* 初始化所有槽为空 */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — 与 key=1 冲突！ */
printf("key=1 → %d\n", search(table, 1)); /* 输出: 100 */
printf("key=2 → %d\n", search(table, 2)); /* 输出: 200 */
printf("key=11 → %d\n", search(table, 11)); /* 输出: 300 (链地址法正确处理了冲突) */
printf("key=99 → %d\n", search(table, 99)); /* 输出: -1 (未找到) */
return 0;
}
应用场景
| 场景 | 说明 |
|---|---|
| 字典/Map | 键值对的存储与快速查找，如 Python 的 dict、Java 的 HashMap |
| 缓存系统 | LRU Cache 等缓存系统的底层实现 |
| 数据库索引 | 哈希索引实现等值查询的 O(1) 查找 |
| 编译器符号表 | 记录变量名、函数名及其类型的映射关系 |