Java:实现使用双哈希作为冲突解决技术的哈希表算法（附带源码）
一、项目背景详细介绍
在计算机科学与软件工程领域，哈希表（Hash Table）因其高效的查找、插入和删除性能（平均 O(1)）而被广泛应用。Java 标准库提供的 HashMap、HashSet 等基于链式法（Separate Chaining）或红黑树优化的哈希表实现，已很好地满足了大多数使用场景。但对于理解哈希冲突处理原理、底层性能权衡，以及在特定场景下进行自定义扩展和优化，手动实现各种开放寻址策略仍具有重要的学习意义。
开放寻址方法（Open Addressing）通过在发生哈希冲突时，将元素放置于表中其他空闲槽位来解决冲突。常见策略有线性探测（Linear Probing）、二次探测（Quadratic Probing）和双重哈希（Double Hashing）。其中，双重哈希使用两个不同的哈希函数生成两个探测步长，具有更好的分散性与更低的聚集风险，适用于对性能和负载因子更高要求的场景。
本项目聚焦于使用双重哈希作为冲突解决技术，实现一个通用的、可扩容、支持 put、get、remove、遍历等操作的 Java 哈希表。通过本项目，读者可以深入理解双重哈希的原理、装载因子对性能的影响、扩容策略、删除处理等核心技术细节。
二、项目需求详细介绍
-
功能需求
-
插入（put(K key, V value)）：若键不存在，将键值对插入；若存在，则更新其值。
-
查找（get(K key)）：根据键返回对应值，若不存在返回
null。 -
删除（remove(K key)）：移除给定键的键值对，并保证后续探测链完整性。
-
动态扩容（resize）：当装载因子超过阈值时，将容量扩展为原来的两倍。
-
遍历（keys() / values()）：提供迭代器接口，遍历所有存储的键和值。
-
-
性能需求
-
平均复杂度：插入、查找、删除均为 O(1)（摊销）。
-
负载因子阈值：默认为 0.5，可配置；高负载因子下性能可能下降。
-
-
设计需求
-
模块化：实现一个通用类
DoubleHashingHashTable<K, V>。 -
安全性：校验输入合法性（如键非空）。
-
健壮性：在各种边界情况下行为正确（如扩容、删除后再查找）。
-
可配置性：允许自定义初始容量与装载因子。
-
三、相关技术详细介绍
-
哈希函数
-
Java 对象的默认
hashCode()用于生成初级哈希值，保证分布均匀。 -
为避免负值，取正值：
h1 = (hashCode & 0x7fffffff) % capacity。 -
第二哈希函数
h2应与capacity互质，常取：
-
h2 = R - (hashCode & 0x7fffffff) % R
-
-
其中 R 是比 capacity 小的质数（如 capacity/2 取下一个质数），保证探测步长与表长互质，以遍历全表。
-
-
双重哈希（Double Hashing）探测策略
-
在第 i 次探测时，计算索引：
-
idx = (h1 + i * h2) % capacity
-
-
它结合了两种哈希函数的优点：第一哈希决定簇的初始位置，第二哈希决定簇内步长。
-
能够有效避免线性探测的初级聚集问题与二次探测的二级聚集。
-
-
装载因子（Load Factor）与扩容
-
定义：
α = N / M（N：已存元素数，M：表容量）。 -
若装载因子过高，冲突增多，查找/插入性能下降；过低，则空间利用率低。
-
当
α > threshold时，自动扩容至2*M并重新哈希所有元素。
-
-
删除处理
-
直接将槽置空会导致后续探测链断裂，查找失败。
-
解决方案：删除后将后续遇到的所有元素暂存并重新插入；或使用“已删除标记”（tombstone）并在必要时重建表。
-
本实现采用“重插”策略，保证表中无 tombstone 的概念，简化实现。
-
四、实现思路详细介绍
-
类成员定义
private K[] keys; // 键数组
private V[] values; // 值数组
private int capacity; // 表容量
private int size; // 当前元素数
private final double loadFactor; // 装载因子阈值
private final int R; // 用于第二哈希函数的质数
-
构造函数
-
默认构造：
capacity=16，loadFactor=0.5，R=13（小于 capacity 的最大质数）。 -
自定义构造：允许传入初始容量和装载因子，并根据容量计算 R。
-
-
主流程
-
put(K key, V value)
-
校验
key非null。 -
若
(size + 1)/capacity > loadFactor，调用resize(2*capacity)。 -
计算
h1、h2。 -
对
i = 0, 1, 2…：-
计算
idx = (h1 + i * h2) % capacity。 -
若
keys[idx] == null，插入新键值对并size++；返回。 -
若
keys[idx].equals(key)，更新values[idx]；返回。
-
-
-
get(K key)
-
校验
key非null。 -
同上计算
h1、h2，并线性遍历至空槽返回null或找到后返回值。
-
-
remove(K key)
-
查找目标元素索引
idx。 -
若不存在，返回
null。 -
否则置
keys[idx]=values[idx]=null，size--，
然后idx = (idx + h2) % capacity一直遍历后续元素，暂存后清除并重新put。
-
-
resize(int newCap)
-
保存原数组，创建新数组和新
capacity。 -
重新计算新的
R。 -
遍历原数组，依次
put。
-
-
-
遍历与工具方法
-
hash1(K key)、hash2(K key)：分别实现两个哈希函数。
-
keys() / values()：返回跳过
null的懒加载Iterable。 -
size() / isEmpty()：基础信息接口。
-
五、完整实现代码
// 文件：DoubleHashingHashTable.java
package com.example.hashtable;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 双重哈希（Double Hashing）开放寻址哈希表实现
*
* @param <K> 键类型
* @param <V> 值类型
*/
public class DoubleHashingHashTable<K, V> {
private static final int DEFAULT_CAPACITY = 16; // 默认容量
private static final double DEFAULT_LOAD_FACTOR = 0.5; // 默认装载因子阈值
private K[] keys; // 键数组
private V[] values; // 值数组
private int capacity; // 当前容量
private int size; // 元素个数
private final double loadFactor; // 装载因子
private int R; // 第二哈希函数使用的质数
@SuppressWarnings("unchecked")
public DoubleHashingHashTable(int initialCapacity, double loadFactor) {
this.capacity = initialCapacity;
this.loadFactor = loadFactor;
this.size = 0;
// 选择小于 capacity 的最大质数 R
this.R = getPreviousPrime(capacity);
this.keys = (K[]) new Object[capacity];
this.values = (V[]) new Object[capacity];
}
public DoubleHashingHashTable() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 插入或更新键值对
*/
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key 不能为空");
// 扩容检查
if ((double) (size + 1) / capacity > loadFactor) {
resize(2 * capacity);
}
int h1 = hash1(key);
int h2 = hash2(key);
int idx = h1;
for (int i = 0; i < capacity; i++) {
idx = (h1 + i * h2) % capacity;
if (keys[idx] == null) {
keys[idx] = key;
values[idx] = value;
size++;
return;
}
if (keys[idx].equals(key)) {
values[idx] = value;
return;
}
}
// 正常情况下不会到达此处
throw new RuntimeException("表已满，无法插入");
}
/**
* 查找值
*/
public V get(K key) {
if (key == null) return null;
int h1 = hash1(key);
int h2 = hash2(key);
int idx;
for (int i = 0; i < capacity; i++) {
idx = (h1 + i * h2) % capacity;
if (keys[idx] == null) return null;
if (keys[idx].equals(key)) {
return values[idx];
}
}
return null;
}
/**
* 删除键值对
*/
public V remove(K key) {
if (key == null) return null;
int h1 = hash1(key);
int h2 = hash2(key);
int idx;
for (int i = 0; i < capacity; i++) {
idx = (h1 + i * h2) % capacity;
if (keys[idx] == null) return null;
if (keys[idx].equals(key)) {
V oldValue = values[idx];
keys[idx] = null;
values[idx] = null;
size--;
// 重新插入后续探测链上的元素
rehashFrom((idx + h2) % capacity, h2);
return oldValue;
}
}
return null;
}
/**
* 从 startIdx 开始，按照步长 h2 重新插入所有后续元素
*/
private void rehashFrom(int startIdx, int h2) {
int idx = startIdx;
while (keys[idx] != null) {
K reKey = keys[idx];
V reVal = values[idx];
keys[idx] = null;
values[idx] = null;
size--;
put(reKey, reVal);
idx = (idx + h2) % capacity;
}
}
/**
* 哈希函数1：获取初始索引
*/
private int hash1(K key) {
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
/**
* 哈希函数2：获取探测步长
*/
private int hash2(K key) {
return R - ((key.hashCode() & 0x7FFFFFFF) % R);
}
/**
* 扩容至 newCapacity 并重新哈希
*/
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
K[] oldKeys = keys;
V[] oldValues = values;
capacity = newCapacity;
R = getPreviousPrime(capacity);
keys = (K[]) new Object[capacity];
values = (V[]) new Object[capacity];
size = 0;
for (int i = 0; i < oldKeys.length; i++) {
if (oldKeys[i] != null) {
put(oldKeys[i], oldValues[i]);
}
}
}
/**
* 返回小于 n 的最大质数
*/
private int getPreviousPrime(int n) {
for (int i = n - 1; i >= 2; i--) {
if (isPrime(i)) return i;
}
return 3;
}
private boolean isPrime(int num) {
if (num < 2) return false;
for (int i = 2; i * i <= num; i++) {
if (num % i == 0) return false;
}
return true;
}
/**
* 返回所有键的迭代器
*/
public Iterable<K> keys() {
return () -> new Iterator<K>() {
private int idx = 0;
@Override
public boolean hasNext() {
while (idx < capacity && keys[idx] == null) idx++;
return idx < capacity;
}
@Override
public K next() {
if (!hasNext()) throw new NoSuchElementException();
return keys[idx++];
}
};
}
/**
* 返回所有值的迭代器
*/
public Iterable<V> values() {
return () -> new Iterator<V>() {
private int idx = 0;
@Override
public boolean hasNext() {
while (idx < capacity && values[idx] == null) idx++;
return idx < capacity;
}
@Override
public V next() {
if (!hasNext()) throw new NoSuchElementException();
return values[idx++];
}
};
}
/**
* 当前元素个数
*/
public int size() {
return size;
}
/**
* 是否为空
*/
public boolean isEmpty() {
return size == 0;
}
}
六、代码详细解读
-
构造函数：初始化容量、装载因子，计算第二哈希质数 R，并分配数组。
-
put 方法：
-
校验键非空并检查装载因子，必要时扩容；
-
计算
h1（主哈希）、h2（探测步长）； -
按公式
(h1 + i*h2)%capacity线性探测：遇空槽则插入，遇相同键则更新。
-
-
get 方法：同样计算
h1、h2，沿探测序列查找并返回值，否则为null。 -
remove 方法：找到目标后置空并
size--，再从删除位置沿步长h2重插后续所有元素，保证表完整性。 -
resize 方法：扩容为两倍，重新计算 R 并对旧表中所有元素逐一
put。 -
hash1/hash2：分别实现主哈希和双哈希探测步长，通过取模、质数保证遍历全表。
-
getPreviousPrime/isPrime：用于计算小于容量的最大质数 R，保证
h2与capacity互质。 -
keys/values 迭代器：跳过
null，懒加载方式返回所有键或值。
七、项目详细总结
本项目通过 Java 从零实现了双重哈希的开放寻址哈希表，重点掌握了两种哈希函数设计、探测序列计算、装载因子与扩容、删除后重插策略等核心技术。与线性探测相比，双重哈希能够显著降低聚集现象，提高高负载场景下的性能稳定性。经多组测试，插入、查找、删除操作均能保持 O(1) 摊销复杂度，扩容后元素分布均匀、查找效率恢复良好。
八、项目常见问题及解答
-
Q：为什么第二哈希函数要与容量互质？
A：保证探测步长与表容量互质，可遍历整个表而无死角。 -
Q：双重哈希相比线性探测的优势是什么？
A：避免了线性探测的初级聚集和二次探测的二级聚集，大幅提升高负载情况下的性能。 -
Q：删除后为何需要重插后续元素？
A：直接置 null 会断裂探测链，造成后续元素无法被查找；重插可修复链路。 -
Q：R 如何选取？
A：R 为小于 capacity 的最大质数，可通过简单素性测试获得。 -
Q：是否有 tombstone 策略？
A：本实现采用直接重插，无 tombstone 标记；更简单但删除成本稍高。
九、扩展方向与性能优化
-
探测策略变种
-
二次探测：结合双重哈希与二次探测，可进一步提高分散性。
-
三重哈希：增加第三哈希函数，适用于超高性能场景。
-
-
并发支持
-
使用分段锁（Segment Lock）或读写锁（ReadWriteLock）实现并发访问。
-
参考
ConcurrentHashMap的分段并发设计。
-
-
空间优化
-
tombstone 标记 + 延迟重建，减少删除时的重插成本。
-
紧凑哈希（Compact Hash）结合位图，降低内存开销。
-
-
持久化与缓存
-
将哈希表持久化到文件系统或嵌入式数据库。
-
与 LRU、LFU 等缓存淘汰策略结合，构建高性能缓存。
-
-
动态调整装载因子
-
根据运行时负载动态调节扩容阈值，实现性能与空间的自动平衡。
-
-
基准测试与调优
-
使用 JMH（Java Microbenchmark Harness）对比不同策略在各种负载下的性能。
-
分析 GC 行为，调整 JVM 参数优化内存管理。
-
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
24
0- 0
已为社区贡献476条内容
所有评论(0)