引言
哈希表（Hash Table）是计算机科学中最高效的数据结构之一，它通过哈希函数将键映射到表中的位置，使得平均情况下插入、删除和查找操作的时间复杂度都接近O(1)。本文将从零开始用Java实现一个完整的哈希表，讲解链地址法处理冲突、扩容机制，并以词频统计为实际应用场景展示其威力。
哈希表的核心原理
哈希表的核心是哈希函数：将任意类型的键转换为数组索引。理想的哈希函数应满足：
- 确定性：相同的键总是产生相同的哈希值
- 均匀性：键均匀分布到整个数组范围
- 高效性：计算速度快
由于键空间通常远大于数组大小，冲突（不同键映射到同一索引）不可避免。解决冲突的常用方法有链地址法（Separate Chaining）和开放寻址法（Open Addressing）。本文采用链地址法。
哈希表完整实现
import java.util.*;
/**
* 基于链地址法的哈希表实现
* 支持动态扩容，负载因子阈值默认为0.75
*/
public class HashTable<K, V> {
/**
* 链表节点
*/
private 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;
}
}
private Node<K, V>[] table; // 哈希桶数组
private int size; // 键值对数量
private int capacity; // 当前容量
private static final float LOAD_FACTOR = 0.75f;
private static final int DEFAULT_CAPACITY = 16;
@SuppressWarnings("unchecked")
public HashTable() {
this.capacity = DEFAULT_CAPACITY;
this.table = new Node[capacity];
this.size = 0;
}
/**
* 计算哈希索引
* 使用扰动函数减少冲突
*/
private int hash(K key) {
int h = key.hashCode();
// 将高位也参与运算，减少低位相同的冲突
h = (h ^ (h >>> 16)) & 0x7fffffff;
return h % capacity;
}
/**
* 插入键值对
*/
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("键不能为null");
// 检查是否需要扩容
if ((float) size / capacity > LOAD_FACTOR) {
resize();
}
int index = hash(key);
Node<K, V> head = table[index];
// 检查是否已存在相同键
for (Node<K, V> node = head; node != null; node = node.next) {
if (node.key.equals(key)) {
node.value = value; // 更新值
return;
}
}
// 头插法插入新节点
Node<K, V> newNode = new Node<>(key, value);
newNode.next = head;
table[index] = newNode;
size++;
}
/**
* 根据键获取值
*/
public V get(K key) {
if (key == null) return null;
int index = hash(key);
for (Node<K, V> node = table[index]; node != null; node = node.next) {
if (node.key.equals(key)) {
return node.value;
}
}
return null;
}
/**
* 删除键值对
*/
public V remove(K key) {
if (key == null) return null;
int index = hash(key);
Node<K, V> prev = null;
Node<K, V> curr = table[index];
while (curr != null) {
if (curr.key.equals(key)) {
if (prev == null) {
table[index] = curr.next;
} else {
prev.next = curr.next;
}
size--;
return curr.value;
}
prev = curr;
curr = curr.next;
}
return null;
}
/**
* 检查是否包含指定键
*/
public boolean containsKey(K key) {
return get(key) != null;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
/**
* 扩容：容量翻倍，重新哈希所有元素
*/
@SuppressWarnings("unchecked")
private void resize() {
int newCapacity = capacity * 2;
Node<K, V>[] newTable = new Node[newCapacity];
// 重新放置所有节点
for (Node<K, V> head : table) {
while (head != null) {
Node<K, V> next = head.next;
int newIndex = (head.key.hashCode() ^ (head.key.hashCode() >>> 16))
& 0x7fffffff % newCapacity;
head.next = newTable[newIndex];
newTable[newIndex] = head;
head = next;
}
}
table = newTable;
capacity = newCapacity;
}
/**
* 获取所有键
*/
public Set<K> keySet() {
Set<K> keys = new HashSet<>();
for (Node<K, V> head : table) {
for (Node<K, V> node = head; node != null; node = node.next) {
keys.add(node.key);
}
}
return keys;
}
/**
* 获取哈希表统计信息
*/
public void printStats() {
int usedBuckets = 0;
int maxChain = 0;
for (Node<K, V> head : table) {
if (head != null) {
usedBuckets++;
int chainLen = 0;
for (Node<K, V> node = head; node != null; node = node.next) {
chainLen++;
}
maxChain = Math.max(maxChain, chainLen);
}
}
System.out.printf("容量: %d, 元素数: %d, 已用桶: %d, 最大链长: %d, 负载因子: %.2f%n",
capacity, size, usedBuckets, maxChain, (double) size / capacity);
}
}
词频统计应用
/**
* 词频统计器
* 使用自定义哈希表统计文本中每个单词的出现次数
*/
public class WordFrequencyCounter {
/**
* 统计文本词频
*/
public static HashTable<String, Integer> countWords(String text) {
HashTable<String, Integer> freqMap = new HashTable<>();
// 分词：转换为小写，去除标点，按空格分割
String[] words = text.toLowerCase()
.replaceAll("[^a-z\\s]", " ")
.split("\\s+");
for (String word : words) {
if (word.isEmpty()) continue;
Integer count = freqMap.get(word);
if (count == null) {
freqMap.put(word, 1);
} else {
freqMap.put(word, count + 1);
}
}
return freqMap;
}
/**
* 获取出现频率最高的N个单词
*/
public static List<Map.Entry<String, Integer>> getTopN(
HashTable<String, Integer> freqMap, int n) {
// 收集所有条目
List<Map.Entry<String, Integer>> entries = new ArrayList<>();
for (String key : freqMap.keySet()) {
entries.add(new AbstractMap.SimpleEntry<>(key, freqMap.get(key)));
}
// 按频率降序排序
entries.sort((a, b) -> b.getValue().compareTo(a.getValue()));
return entries.subList(0, Math.min(n, entries.size()));
}
/**
* 打印词云风格的词频分布
*/
public static void printWordCloud(HashTable<String, Integer> freqMap, int topN) {
List<Map.Entry<String, Integer>> topWords = getTopN(freqMap, topN);
System.out.println("\n=== 词频Top " + topN + " ===");
int maxFreq = topWords.get(0).getValue();
for (Map.Entry<String, Integer> entry : topWords) {
int barLen = (int) ((entry.getValue() * 50.0) / maxFreq);
String bar = "█".repeat(barLen);
System.out.printf("%-15s %4d %s%n", entry.getKey(), entry.getValue(), bar);
}
}
}
去重与集合操作
/**
* 基于哈希表的简单集合实现
*/
public class HashSet<T> {
private final HashTable<T, Boolean> table;
public HashSet() {
this.table = new HashTable<>();
}
public void add(T item) {
table.put(item, true);
}
public boolean contains(T item) {
return table.containsKey(item);
}
public void remove(T item) {
table.remove(item);
}
public int size() {
return table.size();
}
/**
* 求两个集合的交集
*/
public static <T> List<T> intersect(HashSet<T> a, HashSet<T> b) {
List<T> result = new ArrayList<>();
for (T item : a.table.keySet()) {
if (b.contains(item)) {
result.add(item);
}
}
return result;
}
}
主程序与测试
public class HashTableMain {
public static void main(String[] args) {
// 测试基本操作
System.out.println("=== 哈希表基本操作测试 ===");
HashTable<String, Integer> scores = new HashTable<>();
scores.put("Alice", 95);
scores.put("Bob", 87);
scores.put("Charlie", 92);
scores.put("Diana", 88);
scores.put("Eve", 91);
System.out.println("Alice的分数: " + scores.get("Alice"));
System.out.println("Bob的分数: " + scores.get("Bob"));
System.out.println("表大小: " + scores.size());
scores.printStats();
// 测试更新和删除
scores.put("Alice", 98);
System.out.println("\n更新后Alice的分数: " + scores.get("Alice"));
scores.remove("Bob");
System.out.println("删除Bob后大小: " + scores.size());
// 大规模插入测试扩容
System.out.println("\n=== 扩容测试 ===");
HashTable<Integer, String> bigTable = new HashTable<>();
for (int i = 0; i < 100; i++) {
bigTable.put(i, "value_" + i);
}
bigTable.printStats();
// 词频统计测试
System.out.println("\n=== 词频统计测试 ===");
String sampleText = "The quick brown fox jumps over the lazy dog. " +
"The dog was not so lazy after all. " +
"The fox jumped high and the dog ran fast. " +
"Quick brown foxes and lazy dogs make a strange pair. " +
"The quick fox jumps over the lazy dog again and again.";
HashTable<String, Integer> freq = WordFrequencyCounter.countWords(sampleText);
System.out.println("总词数: " + freq.size());
WordFrequencyCounter.printWordCloud(freq, 10);
// 集合去重测试
System.out.println("\n=== 集合去重测试 ===");
HashSet<String> tags1 = new HashSet<>();
tags1.add("java");
tags1.add("algorithm");
tags1.add("datastructure");
tags1.add("hash");
HashSet<String> tags2 = new HashSet<>();
tags2.add("java");
tags2.add("python");
tags2.add("hash");
tags2.add("machinelearning");
List<String> common = HashSet.intersect(tags1, tags2);
System.out.println("共同标签: " + common);
}
}
哈希函数设计要点
一个好的哈希函数需要平衡计算速度和分布均匀性。本文使用的扰动函数 h ^ (h >>> 16) 借鉴了Java HashMap的设计：
// 原始哈希码的低位可能相同，导致索引冲突
int index = key.hashCode() % capacity; // 冲突多
// 将高16位与低16位异或，让高位也参与索引计算
int h = key.hashCode();
h ^= (h >>> 16);
int index = h % capacity; // 分布更均匀
复杂度分析
| 操作 | 平均时间 | 最坏时间 | 空间 |
|---|---|---|---|
| 插入 put | O(1) | O(n) | O(n) |
| 查找 get | O(1) | O(n) | O(1) |
| 删除 remove | O(1) | O(n) | O(1) |
| 扩容 resize | O(n) | O(n) | O(n) |
最坏情况发生在所有键都冲突到同一索引时，退化为链表遍历。
总结
哈希表通过空间换时间的策略，将查找效率提升到接近常数级别。链地址法实现简单且无需处理复杂的删除逻辑，是工程中的首选方案。理解哈希表的扩容机制、负载因子和冲突处理策略，对于正确使用和调优哈希表至关重要。Java中的HashMap正是基于这些原理构建，掌握底层实现有助于写出更高效的代码。
