线性探测法是开放地址法中解决哈希冲突的方式：当目标位置被占，依次检查下一位置（索引+1），直至找到空槽或遍历完数组；它实现简单、缓存友好，但易产生聚集现象。
什么是线性探测法
线性探测法是开放地址法中解决哈希冲突的一种方式：当目标位置已被占用，就依次检查下一个位置（索引 +1），直到找到空槽或遍历完数组。它实现简单、缓存友好，但容易产生“聚集”（clustering），影响性能。
核心设计要点
用数组模拟哈希表时，需明确三点：
JavaStoryDevelop
下载
你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在
-
数组元素类型：建议使用自定义键值对类（如
HashEntry<k></k>），支持存储键、值，并能区分“空槽”“已删除”“已占用”三种状态（仅用null区分空和删除会导致查找中断） -
哈希函数：对键调用
hashCode()后取模数组长度（Math.abs(key.hashCode()) % capacity），注意处理负哈希值 -
探测逻辑：从初始哈希位置开始，每次加 1 并对容量取模（
(index + 1) % capacity），避免越界
插入与查找的实现逻辑
插入时，线性探测找第一个空槽或已删除槽；查找时，必须持续探测直到遇到空槽（未命中）或匹配键（命中）。不能在遇到已删除槽就停止，否则会漏掉后续插入的同哈希键。
- 插入步骤：计算初始索引 → 循环探测（跳过已占用但键不匹配的项）→ 找到空槽或已删除槽 → 写入新条目 → size++
- 查找步骤：计算初始索引 → 循环探测（遇到空槽则返回 null；遇到键匹配则返回值）→ 不因“已删除”中断
-
删除步骤：查到键后，不直接置为
null，而设为特殊标记（如DELETED），保证查找链不断裂
一个轻量级示例（简化版）
以下是一个基于 String 键、Integer 值的简易实现片段（省略泛型和扩容）：
class LinearProbingMap {
private static final Object DELETED = new Object();
private HashEntry[] table;
private int size;
private int capacity;
static class HashEntry {
String key;
Integer value;
HashEntry(String k, Integer v) { key = k; value = v; }
}
public LinearProbingMap(int cap) {
capacity = cap;
table = new HashEntry[cap];
}
private int hash(String key) {
return Math.abs(key.hashCode()) % capacity;
}
public void put(String key, Integer value) {
int i = hash(key);
while (table[i] != null && table[i] != DELETED && !table[i].key.equals(key)) {
i = (i + 1) % capacity;
}
table[i] = (table[i] == DELETED) ? new HashEntry(key, value) : table[i];
if (table[i] == null || table[i] == DELETED) {
table[i] = new HashEntry(key, value);
size++;
}
}
public Integer get(String key) {
int i = hash(key);
while (table[i] != null) {
if (table[i] != DELETED && table[i].key.equals(key)) {
return table[i].value;
}
i = (i + 1) % capacity;
}
return null;
}
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
