Java:实现使用二次探测作为冲突的开放寻址的哈希表算法（附带源码）
项目背景详细介绍
在许多场景中，我们需要以 键–值对 的形式高效地存储和检索数据。除了使用分离链表解决冲突的哈希表外，开放寻址法（Open Addressing） 也是常见的方案之一。与分离链表不同，开放寻址将所有元素存储在同一个数组中，当发生冲突时通过探测序列寻找下一个可用槽位。二次探测（Quadratic Probing） 是一种有效的探测策略，它在冲突时按平方序列 hash + 1², hash + 2², hash + 3², … 依次尝试，能在一定程度上减少“主聚集”现象，从而提升性能。
项目需求详细介绍
-
泛型支持
-
键类型
K、值类型V；
-
-
基本操作
-
void put(K key, V value)：插入或更新； -
V get(K key)：根据键查找值； -
V remove(K key)：删除键并返回其值； -
boolean containsKey(K key)； -
int size()/boolean isEmpty()； -
void clear()；
-
-
冲突解决
-
采用开放寻址 + 二次探测；探测函数：
-
idx = (hash + i + i * i) % capacity;
-
动态扩容
-
当负载因子
size/capacity超过阈值（如 0.5）时，容量翻倍并重新哈希；
-
-
删除处理
-
使用“墓碑”（tombstone）标记已删除槽位，以保证探测链的完整性；
-
-
健壮性
-
null键抛出IllegalArgumentException； -
空表
get/remove不命中返回null或抛NoSuchElementException。
-
相关技术详细介绍
-
哈希函数
-
key.hashCode() & 0x7FFFFFFF取正，然后对容量取模；
-
-
开放寻址
-
所有元素存于一个数组中，冲突时按探测序列找下一个可用槽位；
-
-
二次探测
-
探测偏移随尝试次数呈二次增长，可减轻线性探测的主聚集问题；
-
-
墓碑标记
-
删除时不直接清空槽位，而是打上“已删除”标记，后续探测可经过，但插入可复用；
-
实现思路详细介绍
-
内部节点
private static class Entry<K, V> {
K key;
V value;
boolean deleted; // 墓碑标记
Entry(K k, V v) { key = k; value = v; deleted = false; }
}
核心字段
private Entry<K, V>[] table; // 存储槽位
private int capacity; // 当前容量
private int size; // 有效元素数
private final float loadFactor; // 负载因子阈值
-
构造器
-
默认
capacity = 16，loadFactor = 0.5f； -
分配
table = new Entry[capacity]；
-
-
插入（put）
-
校验
key != null； -
如果
(size + deletedCount) / capacity > loadFactor，调用resize()； -
计算初始
hash = hash(key)； -
依次按
i = 0,1,2…计算idx = (hash + i + i*i) % capacity：-
若槽位
null，或deleted==true，插入新Entry，更新size，返回； -
若
key.equals(slot.key)，更新value并返回；
-
-
-
查询（get）
-
同样按二次探测序列遍历，遇
null停止； -
若
!deleted && key.equals(slot.key)，返回value； -
否则继续；未命中返回
null。
-
-
删除（remove）
-
按探测序列定位，找到且
!deleted时打标deleted=true，size--，返回旧值； -
未命中返回
null。
-
-
动态扩容（resize）
-
容量翻倍，新建
newTable，遍历旧table中所有!= null && !deleted的槽位，重新put到newTable；
-
-
其他方法
-
containsKey调用get!=null； -
size/isEmpty/clear简单实现。
-
// 文件：OpenAddressingHashMap.java
import java.util.NoSuchElementException;
@SuppressWarnings("unchecked")
public class OpenAddressingHashMap<K, V> {
private static class Entry<K, V> {
K key; V value;
boolean deleted;
Entry(K k, V v) { key = k; value = v; deleted = false; }
}
private Entry<K, V>[] table;
private int capacity;
private int size;
private int deletedCount;
private final float loadFactor;
public OpenAddressingHashMap() {
this.capacity = 16;
this.loadFactor = 0.5f;
this.table = (Entry<K, V>[]) new Entry[capacity];
this.size = 0;
this.deletedCount = 0;
}
/** 计算非负哈希并对容量取模 */
private int hash(Object key) {
return (key.hashCode() & 0x7FFFFFFF) % capacity;
}
/** 插入或更新 */
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
// 扩容判断：有效数 + 墓碑数 > loadFactor * capacity
if ((size + deletedCount) >= capacity * loadFactor) {
resize();
}
int h = hash(key);
int firstDeleted = -1;
for (int i = 0; i < capacity; i++) {
int idx = (h + i + i * i) % capacity;
Entry<K, V> e = table[idx];
if (e == null) {
// 优先填充第一次遇到的“墓碑”
int target = firstDeleted >= 0 ? firstDeleted : idx;
table[target] = new Entry<>(key, value);
if (firstDeleted >= 0) deletedCount--;
size++;
return;
}
if (e.deleted) {
if (firstDeleted < 0) firstDeleted = idx;
continue;
}
if (e.key.equals(key)) {
e.value = value;
return;
}
}
// 理论上不会到这里
throw new IllegalStateException("HashMap full");
}
/** 根据键查找，未命中返回 null */
public V get(K key) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
int h = hash(key);
for (int i = 0; i < capacity; i++) {
int idx = (h + i + i * i) % capacity;
Entry<K, V> e = table[idx];
if (e == null) break;
if (!e.deleted && e.key.equals(key)) {
return e.value;
}
}
return null;
}
/** 删除键并返回旧值，未命中返回 null */
public V remove(K key) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
int h = hash(key);
for (int i = 0; i < capacity; i++) {
int idx = (h + i + i * i) % capacity;
Entry<K, V> e = table[idx];
if (e == null) break;
if (!e.deleted && e.key.equals(key)) {
e.deleted = true;
size--;
deletedCount++;
return e.value;
}
}
return null;
}
/** 是否包含键 */
public boolean containsKey(K key) {
return get(key) != null;
}
/** 当前元素数量（不含墓碑） */
public int size() {
return size;
}
/** 是否为空 */
public boolean isEmpty() {
return size == 0;
}
/** 清空所有数据 */
public void clear() {
this.table = (Entry<K, V>[]) new Entry[capacity];
this.size = 0;
this.deletedCount = 0;
}
/** 扩容并重哈希 */
private void resize() {
Entry<K, V>[] old = table;
capacity <<= 1;
table = (Entry<K, V>[]) new Entry[capacity];
size = 0;
deletedCount = 0;
for (Entry<K, V> e : old) {
if (e != null && !e.deleted) {
put(e.key, e.value);
}
}
}
}
// 文件：Main.java
public class Main {
public static void main(String[] args) {
OpenAddressingHashMap<String, Integer> map = new OpenAddressingHashMap<>();
map.put("apple", 3);
map.put("banana", 2);
map.put("orange", 5);
System.out.println("banana -> " + map.get("banana")); // 2
map.put("banana", 7);
System.out.println("banana -> " + map.get("banana")); // 7
System.out.println("contains grape? " + map.containsKey("grape")); // false
System.out.println("remove apple: " + map.remove("apple")); // 3
System.out.println("size: " + map.size()); // 2
}
}
代码详细解读
-
槽位与墓碑
-
Entry.deleted标记“已删除”槽位； -
插入时优先复用首个遇到的墓碑槽位；
-
-
二次探测
-
idx = (h + i + i*i) % capacity，其中i从 0 递增； -
确保探测序列可覆盖整个表；
-
-
动态扩容
-
当
(size + deletedCount) ≥ loadFactor * capacity时触发； -
容量翻倍后，对所有“真实”数据重新插入（跳过墓碑）；
-
-
删除操作
-
仅标记
deleted=true，不清空槽位，以保证后续探测链不被截断； -
墓碑数
deletedCount增加，防止表过度填满；
-
项目详细总结
本实现通过开放寻址 + 二次探测，在一个连续数组中管理所有键值对，避免了链表节点的额外开销。利用墓碑标记实现删除操作，同时在负载因子超限时自动扩容并重哈希，保证了均摊 O(1) 的插入、查找与删除性能。
项目常见问题及解答
-
问：为什么要用墓碑？
答：直接清空槽位会截断探测链，导致后续可能存在的元素无法被找到。墓碑既能标记已删除，又允许探测继续。 -
问：二次探测与线性探测有什么区别？
答：线性探测按hash + i寻找，容易产生“主聚集”；二次探测按平方序列，有助于减少聚集。 -
问：扩容阈值为何用
(size+deletedCount)？
答：包括墓碑在内的已使用槽位会影响探测效率，需一并考虑。 -
问：如何改为无需墓碑的删除？
答：可在删除后将后续探测链上的元素逐一重新插入，但实现复杂且效率较低。 -
问：如何选择
loadFactor？
答：一般 0.5~0.7 可在空间利用率与探测长度之间取得平衡。
扩展方向与性能优化
-
双哈希探测：使用第二个哈希函数生成跳跃长度，进一步减轻聚集；
-
并发优化：结合分段锁或
java.util.concurrent包，实现线程安全版本； -
定制哈希函数：针对特定键类型优化
hashCode以减少冲突； -
缓存友好：按块加载或内存对齐，提升缓存命中率；
-
统计分析：监控探测次数分布，动态调整扩容策略与负载因子。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
32
0- 0
已为社区贡献484条内容
所有评论(0)