链地址法（Separate Chaining）是哈希表解决冲突的经典方法：将哈希值相同的元素存储在同一个链表中，数组的每个位置都是一个链表的头指针。当发生哈希冲突时，新元素追加到对应链表中，查找时遍历链表匹配。

定义与核心原理

哈希表通过哈希函数将关键字映射到数组下标，但不同关键字可能映射到同一位置（冲突）。链地址法的解决方式是：

• 数组：存储链表头指针，数组大小 P（通常取素数）
• 链表：每个数组位置挂一个链表，存储所有哈希值相同的元素

数据结构定义（C语言）

#define Elemtype int    // 关键字元素类型
#define P 13            // 哈希表大小（取素数，12个关键字取13）

typedef struct HashNode {
    Elemtype data;     // 数据域
    HashNode* link;    // 指针域，指向下一个链表元素
} HashNode;

typedef HashNode* HashTable[P];  // 哈希数组，每个元素为指针

操作步骤

1. 哈希函数

int hash(int key) {
    return key % P;  // 除留余数法
}

2. 插入

void insert(HashTable ht, int key) {
    int idx = hash(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    node->data = key;
    node->link = ht[idx];   // 头插法
    ht[idx] = node;
}

3. 查找

HashNode* search(HashTable ht, int key) {
    int idx = hash(key);
    HashNode* p = ht[idx];
    while (p && p->data != key) {
        p = p->link;
    }
    return p;  // 找到返回节点指针，未找到返回 NULL
}

完整示例（P=13，12个关键字）

插入元素：{01, 10, 11, 14, 19, 20, 23, 27, 55, 68, 79, 84}，哈希函数 key % 13：

桶下标	哈希值	链表内容
0	-	空（∧）
1	1%13=1, 14%13=1, 27%13=1, 79%13=1	01 → 14 → 27 → 79 → ∧
2	-	空（∧）
3	55%13=3, 68%13=3	55 → 68 → ∧
4	-	空（∧）
5	-	空（∧）
6	19%13=6, 84%13=6	19 → 84 → ∧
7	20%13=7	20 → ∧
8	-	空（∧）
9	-	空（∧）
10	10%13=10, 23%13=10	10 → 23 → ∧
11	11%13=11	11 → ∧
12	-	空（∧）

装填因子 α = 12/13 ≈ 0.92（偏高，实际应用建议控制在 0.7 以下，超过则扩容）。

复杂度分析

操作	平均时间	最坏时间	说明
插入	O(1)	O(n)	头插法，冲突多时遍历链表
查找	O(1+α)	O(n)	α 为装填因子 = 元素数/表长
删除	O(1+α)	O(n)	需找到前驱节点

装填因子 α：α 越小，冲突越少，但空间浪费越大。通常控制 α 在 0.7 左右，超过则扩容（rehash）。

实践应用

• 通用哈希表：C++ STL 的 unordered_map / unordered_set 底层即链地址法
• 字典/符号表：编译器的符号表实现
• 缓存系统：LRU Cache 中哈希表+双向链表
• 数据库索引：哈希索引的实现方式之一

常见误区

1. P 不取素数：哈希表大小应取素数，减少冲突聚集。12 个关键字取 P=13
2. 忘记 malloc：C 语言中节点需手动申请内存，配合 #include<cstdlib>
3. 头插法 vs 尾插法：头插法 O(1) 但元素顺序与插入相反；尾插法需遍历到尾部
4. 装填因子过高：α > 0.7 时性能急剧下降，应扩容 rehash

一句话总结

链地址法用"数组挂链表"解决冲突，插入头插 O(1)，查找平均 O(1+α)；表长 P 取素数，装填因子 α 超过 0.7 就该扩容 rehash。

相关概念

• 桶排序
• 快速排序
• 最小生成树