数据结构与算法 / 系统课时
链地址法
链地址法
链地址法把发生哈希冲突的键保存在同一个桶的链表中。本课将从桶结构、装载因子和复杂度出发,实现一个支持插入、更新、查找与删除的整数键哈希表,并通过可重复的冲突数据验证链表如何化解冲突。
学习目标
- 理解桶数组与链表协同解决冲突的过程。
- 能够实现链地址哈希表的核心操作。
- 能够用装载因子分析平均操作成本和扩容时机。
问题定义与核心思路
哈希函数会把大量可能的键映射到有限个桶,因此不同键得到同一桶下标是正常现象。链地址法让每个桶保存一条链表:桶下标负责快速定位候选集合,链表负责区分落入同一桶的键。
查找键 key 时,先计算桶下标,再沿链表比较键。插入时若链表中已有相同键,则更新值;否则创建新节点。删除时区分桶头与其他位置。后一分支也适用于尾节点,此时前驱的 next 变为 null。

装载因子与复杂度
设元素数量为 ,桶数量为 ,装载因子为 。链地址法允许 大于 1,因为一个桶可以容纳多个节点。把所有桶(包括空桶)的链长取算术平均,恰好是 。但查询会访问哪个桶取决于键的分布。下表的期望成本假设哈希分布足够均匀且单次键比较为常数。
| 操作 | 平均时间复杂度 | 最坏时间复杂度 |
|---|---|---|
| 查找 | ||
| 插入或更新 | ||
| 删除 |
空间复杂度为 。当装载因子持续升高时,链表变长,常数级定位的优势会减弱。扩容可以降低平均装载率,但集中冲突还要检查散列质量。本例仅取模,若大量键相差容量的倍数,即使装载率很低也可能集中到一条链。
完整实现与验证
下面的 Java 17 示例使用固定容量和非空值。get 与 remove 用 null 表示未命中,因此 put 先拒绝空值,containsKey 才能通过 get 判定。键 1、6、11 在容量为 5 时都会进入桶 1。
import java.util.Arrays;
import java.util.Locale;
import java.util.Objects;
public class ChainHashTableDemo {
private static final class Node {
private final int key;
private String value;
private Node next;
private Node(int key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private static final class ChainHashTable {
private final Node[] buckets;
private int size;
private ChainHashTable(int capacity) {
if (capacity <= 0) {
throw new IllegalArgumentException("capacity must be positive");
}
this.buckets = new Node[capacity];
}
public void put(int key, String value) {
Objects.requireNonNull(value, "value must be non-null");
int index = bucketIndex(key);
Node current = buckets[index];
while (current != null) {
if (current.key == key) {
current.value = value;
return;
}
current = current.next;
}
// 新节点放到链表头部,插入本身只需要常数次指针修改。
buckets[index] = new Node(key, value, buckets[index]);
size++;
}
public String get(int key) {
Node current = buckets[bucketIndex(key)];
while (current != null) {
if (current.key == key) {
return current.value;
}
current = current.next;
}
return null;
}
public String remove(int key) {
int index = bucketIndex(key);
Node current = buckets[index];
Node previous = null;
while (current != null) {
if (current.key == key) {
if (previous == null) {
buckets[index] = current.next;
} else {
previous.next = current.next;
}
size--;
return current.value;
}
previous = current;
current = current.next;
}
return null;
}
public boolean containsKey(int key) {
return get(key) != null;
}
public int size() {
return size;
}
public double loadFactor() {
return (double) size / buckets.length;
}
public int[] bucketSizes() {
int[] result = new int[buckets.length];
for (int i = 0; i < buckets.length; i++) {
Node current = buckets[i];
while (current != null) {
result[i]++;
current = current.next;
}
}
return result;
}
private int bucketIndex(int key) {
return Math.floorMod(key, buckets.length);
}
}
public static void main(String[] args) {
ChainHashTable table = new ChainHashTable(5);
table.put(1, "A");
table.put(6, "B");
table.put(11, "C");
table.put(2, "D");
table.put(6, "B2");
System.out.println("bucket sizes = " + Arrays.toString(table.bucketSizes()));
System.out.println("get(11) = " + table.get(11));
System.out.println("get(6) = " + table.get(6));
System.out.println("remove(1) = " + table.remove(1));
System.out.println("containsKey(1) = " + table.containsKey(1));
System.out.println("size = " + table.size());
System.out.printf(Locale.ROOT, "load factor = %.2f%n", table.loadFactor());
}
}将代码保存为 ChainHashTableDemo.java,然后编译并运行:
javac -encoding UTF-8 ChainHashTableDemo.java
java ChainHashTableDemo预期输出
bucket sizes = [0, 3, 1, 0, 0]
get(11) = C
get(6) = B2
remove(1) = A
containsKey(1) = false
size = 3
load factor = 0.60常见错误与实践建议
删除桶头节点时,必须修改 buckets[index];只修改局部变量 current 不会改变桶中的链表。更新已有键时不要增加 size,否则装载因子会被重复键污染。
哈希下标不要直接使用 key % capacity,因为负键可能产生负数下标。示例使用 Math.floorMod(key, buckets.length),对正容量能得到 0 到 capacity−1 的结果,包括 Integer.MIN_VALUE。
固定容量适合教学验证,但长期运行的哈希表应在装载因子超过阈值后扩容。扩容时必须重新计算所有键的桶下标,因为桶数量变化会改变哈希映射结果。
本课练习
- 为示例增加
clear()方法,要求释放所有桶链表并把size重置为0,验收条件是清空后所有桶长度为0。 - 增加自动扩容:当装载因子大于
0.75时把桶数量扩大为原来的两倍,并重新散列已有节点,验收条件是扩容前后的键值查询结果一致。
本课总结
- 链地址法用桶数组缩小查找范围,用链表保存同桶冲突元素。
- 平均操作成本与装载因子 相关,分布均匀时约为 。
- 删除、重复键更新、负键下标和扩容重散列是实现中的关键边界。
下一课预告
下一课将学习“开放寻址法”,把冲突元素直接存入桶数组,并比较线性探测、二次探测和双重哈希的探测路径。