Java:实现使用线性探测作为冲突的开放寻址的哈希表算法（附带源码）
一、项目背景详细介绍
在现代软件系统中，哈希表（Hash Table）是一种常见且高效的键值存储数据结构，其平均查找、插入和删除操作的时间复杂度均可达到 O(1)。Java 标准库中已经实现了 HashMap、HashSet 等基于哈希表的容器，但了解其底层实现原理，对于深入掌握数据结构与算法并进行自定义优化具有重要意义。
开放寻址法（Open Addressing）和链式法（Separate Chaining）是常见的两种开放式哈希解决冲突的方法。其中，开放寻址法将冲突的元素存储在表的其他空闲槽位上，它根据一定的探测序列进行“探测”，线性探测（Linear Probing）是最简单的一种探测策略：当发生冲突时，依次向后移动固定的步长（通常为 1），直到找到空槽。
本项目旨在用 Java 从零开始实现一个基于线性探测的开放寻址哈希表，帮助读者理解哈希冲突处理机制、质量因子（load factor）与扩容策略，并通过手写代码掌握底层实现细节。
二、项目需求详细介绍
-
功能需求
-
插入（put）：向哈希表中插入键值对，如果键已存在则更新对应值。
-
查找（get）：根据键返回对应的值，若不存在返回
null。 -
删除（remove）：根据键删除键值对，并保证后续探测链仍能正确查找。
-
扩容（resize）：当哈希表的装载因子超过阈值时，自动将内部数组容量扩大为原来的两倍并重新哈希。
-
遍历（keys/values）：返回当前所有键或所有值的迭代器。
-
-
性能需求
-
平均查找/插入/删除时间复杂度：O(1)。
-
合适的装载因子阈值：一般取 0.5~0.75。
-
-
设计需求
-
代码结构清晰、可维护。
-
使用对外 API 友好的接口设计：
public class LinearProbingHashTable<K,V>。 -
完整测试用例，验证各种边界场景（如负载因子达到阈值、删除后再查找、扩容后元素顺序正确性等）。
-
三、相关技术详细介绍
-
哈希函数
-
Java 对象默认的
hashCode()返回一个int，可通过key.hashCode() & 0x7fffffff取正。 -
取模映射：
index = hash % capacity。
-
-
线性探测（Linear Probing）
-
冲突时位置
i：尝试(i + 1) % capacity，依次向后查找。 -
聚集问题：连续冲突会形成“聚簇”，可能导致性能下降。
-
-
装载因子（Load Factor）
-
定义为
N / M，其中N为元素个数，M为表容量。 -
当超过阈值（如 0.75）时触发扩容，降低聚集风险。
-
-
扩容策略
-
将容量扩为原来的两倍，并将所有存在的键值对重新哈希到新数组。
-
扩容开销为 O(N)，但平均摊销成本仍为 O(1)。
-
-
删除策略
-
不能直接将槽置为
null，否则探测链断裂。 -
需标记“已删除”或重新整理后续元素。
-
简化方式：在删除后，将后继元素逐一重新插入，保证探测链完整。
-
四、实现思路详细介绍
-
数据结构设计
-
使用两个并行数组：
K[] keys、V[] values。 -
用
int size记录当前元素个数，用int capacity记录数组长度，用double loadFactor保存阈值。
-
-
哈希与索引计算
-
哈希值：
hash = (key.hashCode() & 0x7fffffff)。 -
初始索引：
idx = hash % capacity。
-
-
插入逻辑（put）
-
计算初始索引
idx。 -
从
idx开始线性探测：-
若
keys[idx] == null或已被标记为“已删除”，则直接插入。 -
若
keys[idx].equals(key)，则替换values[idx]并返回。 -
否则
idx = (idx + 1) % capacity，继续探测。
-
-
插入后
size++；若size / capacity > loadFactor，触发扩容。
-
-
查找逻辑（get）
-
计算初始索引，线性探测直至出现
null即停止，或找到匹配键返回值。
-
-
删除逻辑（remove）
-
查找目标键的索引
idx。 -
若存在，将
keys[idx]、values[idx]置null，并将后续探测链中的元素暂存、size--，然后重新 insert 这些后续元素以保证链不被截断。
-
-
扩容逻辑（resize）
-
创建新数组，容量为旧容量的两倍。
-
遍历旧数组中所有非
null的键值对，调用put插入到新数组。
-
-
遍历接口（keys/values）
-
返回一个包含所有非空键/值的
Iterable，便于使用for-each遍历。
-
五、完整实现代码
// 文件: LinearProbingHashTable.java
package com.example.hashtable;
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* 基于线性探测的开放寻址哈希表实现
* @param <K> 键类型
* @param <V> 值类型
*/
public class LinearProbingHashTable<K, V> {
private static final int DEFAULT_CAPACITY = 16; // 默认初始容量
private static final double DEFAULT_LOAD_FACTOR = 0.75; // 默认装载因子
private K[] keys; // 键数组
private V[] values; // 值数组
private int size; // 当前元素个数
private int capacity; // 当前数组容量
private final double loadFactor; // 装载因子阈值
@SuppressWarnings("unchecked")
public LinearProbingHashTable(int initialCapacity, double loadFactor) {
this.capacity = initialCapacity;
this.loadFactor = loadFactor;
this.keys = (K[]) new Object[capacity];
this.values = (V[]) new Object[capacity];
this.size = 0;
}
public LinearProbingHashTable() {
this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**
* 插入或更新键值对
* @param key 键
* @param value 值
*/
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key 不能为空");
// 装载因子检查并扩容
if ((double) (size + 1) / capacity > loadFactor) {
resize(2 * capacity);
}
int idx = hash(key);
// 线性探测寻找插入位置
while (keys[idx] != null) {
// 如果键已存在则更新值
if (keys[idx].equals(key)) {
values[idx] = value;
return;
}
idx = (idx + 1) % capacity;
}
// 找到空槽后插入
keys[idx] = key;
values[idx] = value;
size++;
}
/**
* 根据键获取值
* @param key 键
* @return 值，若不存在返回 null
*/
public V get(K key) {
if (key == null) return null;
int idx = hash(key);
while (keys[idx] != null) {
if (keys[idx].equals(key)) {
return values[idx];
}
idx = (idx + 1) % capacity;
}
return null;
}
/**
* 删除键值对
* @param key 键
* @return 被删除的值，若不存在返回 null
*/
public V remove(K key) {
if (key == null) return null;
int idx = hash(key);
// 查找目标键
while (keys[idx] != null) {
if (keys[idx].equals(key)) {
V oldValue = values[idx];
// 删除位置置空
keys[idx] = null;
values[idx] = null;
size--;
// 重新插入后续探测链上的元素
idx = (idx + 1) % capacity;
while (keys[idx] != null) {
K reKey = keys[idx];
V reValue = values[idx];
keys[idx] = null;
values[idx] = null;
size--;
put(reKey, reValue);
idx = (idx + 1) % capacity;
}
return oldValue;
}
idx = (idx + 1) % capacity;
}
return null;
}
/**
* 计算索引
*/
private int hash(K key) {
return (key.hashCode() & 0x7fffffff) % capacity;
}
/**
* 扩容并重新哈希
*/
@SuppressWarnings("unchecked")
private void resize(int newCapacity) {
LinearProbingHashTable<K, V> newTable = new LinearProbingHashTable<>(newCapacity, loadFactor);
for (int i = 0; i < capacity; i++) {
if (keys[i] != null) {
newTable.put(keys[i], values[i]);
}
}
this.keys = newTable.keys;
this.values = newTable.values;
this.capacity = newTable.capacity;
}
/**
* 返回所有键的迭代器
*/
public Iterable<K> keys() {
return () -> new Iterator<K>() {
private int index = 0;
@Override
public boolean hasNext() {
while (index < capacity && keys[index] == null) index++;
return index < capacity;
}
@Override
public K next() {
if (!hasNext()) throw new NoSuchElementException();
return keys[index++];
}
};
}
/**
* 返回所有值的迭代器
*/
public Iterable<V> values() {
return () -> new Iterator<V>() {
private int index = 0;
@Override
public boolean hasNext() {
while (index < capacity && values[index] == null) index++;
return index < capacity;
}
@Override
public V next() {
if (!hasNext()) throw new NoSuchElementException();
return values[index++];
}
};
}
/**
* 返回当前元素个数
*/
public int size() {
return size;
}
/**
* 判断是否为空
*/
public boolean isEmpty() {
return size == 0;
}
}
六、代码详细解读
-
构造函数：初始化容量、装载因子，并分配键值数组。
-
put 方法：检查并扩容后，计算初始索引并进行线性探测，插入或更新键值对。
-
get 方法：从哈希值对应位置线性探测查找目标键并返回对应值。
-
remove 方法：删除目标位置后，重新插入该槽之后的所有元素以维护探测链连续性。
-
hash 方法：对键的
hashCode()取正并对容量取模。 -
resize 方法：新建更大容量的表，将所有现存元素重新
put到新表，实现扩容。 -
keys/values 方法：返回键或值的懒加载迭代器，跳过空槽。
-
size/isEmpty 方法：返回当前元素个数及是否为空。
七、项目详细总结
通过本项目，从头实现了基于线性探测的开放寻址哈希表，读者能够深入理解哈希冲突处理、装载因子与扩容机制、以及删除后探测链维护等关键细节。该实现已在多种边界场景下测试通过，如扩容触发、删除后再查找、遍历接口正确性等。该哈希表适用于中小规模数据存取，对于大规模高并发场景建议采用 Java 自带的 ConcurrentHashMap 或其他分布式缓存系统。
八、项目常见问题及解答
-
Q：为何删除后要重新插入后续元素？
A：若不重新插入，探测链会被截断，后续通过线性探测到达该空槽位置的元素将无法找到。 -
Q：聚集问题如何缓解？
A：合理选取装载因子（如 ≤0.5），并使用扩容；也可考虑二次探测或双重散列等高级策略。 -
Q：如何保证扩容后性能？
A：扩容操作为 O(N)，但均摊开销仍为 O(1)。可在初始化时指定更大容量或更低装载因子以减少扩容次数。 -
Q：该实现支持并发吗？
A：当前实现非线程安全，若需并发访问可在外部加锁，或使用ConcurrentHashMap。
九、扩展方向与性能优化
-
探测策略优化
-
二次探测（Quadratic Probing）：步长为二次函数形式，减轻聚集。
-
双重散列（Double Hashing）：使用第二哈希函数计算探测增量，提高分散性。
-
-
内存与空间优化
-
使用位图（Bit Set） 标记已删除槽位，避免频繁重插。
-
压缩存储：对
keys、values数组使用更紧凑的格式或外部存储。
-
-
并发安全
-
基于读写锁或分段锁的并发哈希表实现。
-
无锁（lock-free）或分布式哈希表设计。
-
-
持久化与缓存
-
将哈希表持久化到文件或数据库。
-
与 LRU/TTL 等缓存策略结合，适用于高并发缓存场景。
-
-
性能测试
-
基准测试（Benchmark）不同负载因子、不同探测策略下的读写性能。
-
内存占用与 GC 行为分析。
-
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
45
0- 0
已为社区贡献484条内容
所有评论(0)