引言
散列表（Hash Table）是计算机科学中最基础、最高效的数据结构之一，它通过哈希函数将键映射到表中的位置，实现平均 $O(1)$ 时间复杂度的查找、插入和删除操作。本文将用 Java 完整实现两种经典的散列冲突解决策略——链地址法（Separate Chaining）和开放寻址法（Open Addressing），并对它们的性能进行深入分析与对比。
核心原理
哈希函数
哈希函数的作用是将任意类型的键转换为数组索引。一个好的哈希函数应满足：
– 确定性：相同的输入永远产生相同的输出
– 均匀性：输出均匀分布在值域中，减少冲突
– 高效性：计算速度快
Java 中 Object.hashCode() 提供了基础的哈希值，通常需要进一步处理以适应表的大小：
private int hash(K key) {
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
负载因子
负载因子 $\alpha = \frac{n}{m}$，其中 $n$ 为元素个数，$m$ 为表容量。当 $\alpha$ 超过阈值时，需要进行扩容（Rehashing）以保持性能。
链地址法实现
链地址法将冲突的元素存储在同一个索引对应的链表中。当链表过长时，可转换为红黑树（JDK HashMap 的做法）。
import java.util.ArrayList;
import java.util.List;
/**
* 链地址法散列表实现
* @param <K> 键类型
* @param <V> 值类型
*/
public class ChainingHashTable<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final double LOAD_FACTOR_THRESHOLD = 0.75;
private Node<K, V>[] table;
private int size;
private int capacity;
static class Node<K, V> {
final K key;
V value;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
@SuppressWarnings("unchecked")
public ChainingHashTable() {
this.capacity = DEFAULT_CAPACITY;
this.table = new Node[capacity];
this.size = 0;
}
/**
* 哈希函数：将键映射到数组索引
*/
private int hash(K key) {
if (key == null) return 0;
// 使用位运算确保非负，再取模
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
/**
* 插入键值对，如果键已存在则更新值
*/
public void put(K key, V value) {
if ((double) size / capacity >= LOAD_FACTOR_THRESHOLD) {
resize();
}
int index = hash(key);
Node<K, V> head = table[index];
// 遍历链表，查找是否已存在该键
Node<K, V> current = head;
while (current != null) {
if (current.key.equals(key)) {
current.value = value; // 更新已有值
return;
}
current = current.next;
}
// 头插法插入新节点
Node<K, V> newNode = new Node<>(key, value);
newNode.next = head;
table[index] = newNode;
size++;
}
/**
* 根据键查找值
*/
public V get(K key) {
int index = hash(key);
Node<K, V> current = table[index];
while (current != null) {
if (current.key.equals(key)) {
return current.value;
}
current = current.next;
}
return null;
}
/**
* 删除指定键
*/
public boolean remove(K key) {
int index = hash(key);
Node<K, V> current = table[index];
Node<K, V> prev = null;
while (current != null) {
if (current.key.equals(key)) {
if (prev == null) {
table[index] = current.next;
} else {
prev.next = current.next;
}
size--;
return true;
}
prev = current;
current = current.next;
}
return false;
}
/**
* 扩容：将容量翻倍并重新哈希所有元素
*/
@SuppressWarnings("unchecked")
private void resize() {
Node<K, V>[] oldTable = table;
capacity *= 2;
table = new Node[capacity];
size = 0;
// 重新插入所有元素
for (Node<K, V> head : oldTable) {
while (head != null) {
put(head.key, head.value);
head = head.next;
}
}
}
public int size() {
return size;
}
public boolean containsKey(K key) {
return get(key) != null;
}
/**
* 获取所有键的列表
*/
public List<K> keySet() {
List<K> keys = new ArrayList<>();
for (Node<K, V> head : table) {
Node<K, V> current = head;
while (current != null) {
keys.add(current.key);
current = current.next;
}
}
return keys;
}
}
开放寻址法实现
开放寻址法在冲突时探测表中的其他空槽位。常见的探测策略包括线性探测、二次探测和双重哈希。这里实现二次探测，它在聚类问题上表现更好。
/**
* 开放寻址法散列表实现（二次探测）
* @param <K> 键类型
* @param <V> 值类型
*/
public class OpenAddressingHashTable<K, V> {
private static final int DEFAULT_CAPACITY = 16;
private static final double LOAD_FACTOR_THRESHOLD = 0.7;
private static final Object TOMBSTONE = new Object(); // 标记已删除位置
@SuppressWarnings("unchecked")
private K[] keys = (K[]) new Object[DEFAULT_CAPACITY];
@SuppressWarnings("unchecked")
private V[] values = (V[]) new Object[DEFAULT_CAPACITY];
private int size;
private int capacity = DEFAULT_CAPACITY;
private int tombstoneCount;
/**
* 主哈希函数
*/
private int hash(K key) {
if (key == null) return 0;
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
/**
* 二次探测函数：h(k, i) = (h(k) + c1*i + c2*i^2) % m
* 使用 c1=1, c2=1 的标准形式
*/
private int probe(int hash, int i) {
return (hash + i + i * i) % capacity;
}
/**
* 插入键值对
*/
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
if ((double) (size + tombstoneCount) / capacity >= LOAD_FACTOR_THRESHOLD) {
resize();
}
int hash = hash(key);
int firstTombstone = -1;
for (int i = 0; i < capacity; i++) {
int index = probe(hash, i);
if (keys[index] == null) {
// 找到空位
if (firstTombstone != -1) {
index = firstTombstone; // 优先填充墓碑位置
tombstoneCount--;
}
keys[index] = key;
values[index] = value;
size++;
return;
} else if (keys[index] == TOMBSTONE) {
if (firstTombstone == -1) firstTombstone = index;
} else if (keys[index].equals(key)) {
values[index] = value; // 更新已有值
return;
}
}
throw new RuntimeException("Hash table is full");
}
/**
* 查找值
*/
public V get(K key) {
if (key == null) return null;
int hash = hash(key);
for (int i = 0; i < capacity; i++) {
int index = probe(hash, i);
if (keys[index] == null) {
return null; // 遇到空位，说明不存在
} else if (keys[index] != TOMBSTONE && keys[index].equals(key)) {
return values[index];
}
}
return null;
}
/**
* 删除键值对（使用墓碑标记）
*/
public boolean remove(K key) {
if (key == null) return false;
int hash = hash(key);
for (int i = 0; i < capacity; i++) {
int index = probe(hash, i);
if (keys[index] == null) {
return false;
} else if (keys[index] != TOMBSTONE && keys[index].equals(key)) {
keys[index] = (K) TOMBSTONE;
values[index] = null;
size--;
tombstoneCount++;
return true;
}
}
return false;
}
/**
* 扩容并清理墓碑
*/
@SuppressWarnings("unchecked")
private void resize() {
K[] oldKeys = keys;
V[] oldValues = values;
capacity *= 2;
keys = (K[]) new Object[capacity];
values = (V[]) new Object[capacity];
size = 0;
tombstoneCount = 0;
for (int i = 0; i < oldKeys.length; i++) {
if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) {
put(oldKeys[i], oldValues[i]);
}
}
}
public int size() {
return size;
}
public boolean containsKey(K key) {
return get(key) != null;
}
}
性能测试与对比
public class HashTableBenchmark {
public static void main(String[] args) {
final int N = 100_000;
// 测试链地址法
ChainingHashTable<Integer, String> chaining = new ChainingHashTable<>();
long start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
chaining.put(i, "value_" + i);
}
long chainingInsert = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
chaining.get(i);
}
long chainingSearch = System.currentTimeMillis() - start;
// 测试开放寻址法
OpenAddressingHashTable<Integer, String> openAddr = new OpenAddressingHashTable<>();
start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
openAddr.put(i, "value_" + i);
}
long openInsert = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
openAddr.get(i);
}
long openSearch = System.currentTimeMillis() - start;
System.out.println("=== 性能对比 (N=" + N + ") ===");
System.out.println("链地址法插入: " + chainingInsert + "ms");
System.out.println("链地址法查找: " + chainingSearch + "ms");
System.out.println("开放寻址法插入: " + openInsert + "ms");
System.out.println("开放寻址法查找: " + openSearch + "ms");
}
}
复杂度分析
| 操作 | 链地址法（平均） | 链地址法（最坏） | 开放寻址法（平均） | 开放寻址法（最坏） |
|---|---|---|---|---|
| 插入 | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ |
| 查找 | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ |
| 删除 | $O(1)$ | $O(n)$ | $O(1)$ | $O(n)$ |
| 空间 | $O(n + m)$ | $O(n + m)$ | $O(m)$ | $O(m)$ |
其中 $n$ 为元素数量，$m$ 为表容量。在负载因子控制在合理范围内时，两种方法均能达到近似 $O(1)$ 的平均性能。
总结
- 链地址法实现简单，天然支持动态扩容，适合元素数量变化大的场景；但存在链表指针的额外空间开销。
- 开放寻址法无需额外指针，缓存友好性更好；但需要处理聚类问题，删除操作较复杂（需墓碑机制）。
JDK 的 HashMap 采用链地址法并在链表过长时转为红黑树，是工业界的经典实践。理解两种方法的原理与权衡，是掌握高性能数据结构设计的必经之路。
