Java线性探测开放寻址哈希表代码排查：第三个键值对未插入问题

算力阿峰

2026-5-19

线性探测哈希表插入第三个键值对失败的常见原因

嘿，我来帮你梳理下这个问题——当年我刚啃线性探测哈希表的时候，也栽过好几个类似的坑！虽然你没贴出具体代码，但根据常见的实现错误，大概率是这几个原因之一：

初始容量设置不合理 + 未触发扩容：如果你的哈希表初始容量刚好是3，前两个插入的键哈希后直接占了前两个位置，第三个键的哈希位置冲突后，线性探测时可能因为负载因子判断错误（比如没设置扩容阈值，或者阈值设得太高），导致误以为表已满。比如很多规范实现会把负载因子阈值设为0.75，当元素数量超过容量的75%时就扩容，要是你初始容量是3，插入2个元素后负载因子已经到了≈66%，再插第三个就超过阈值了，没扩容的话很容易出问题。

线性探测的循环逻辑写错了：这是最常见的坑！比如你只从哈希索引往后探测到数组末尾就停止，没回到表头继续循环。举个例子：

// 错误的探测逻辑：只往后找，不循环到表头
int index = hash(key) % table.length;
for (int i = index; i < table.length; i++) {
    if (table[i] == null) {
        table[i] = new Entry(key, value);
        return;
    }
}
throw new IllegalStateException("表已满");

要是第三个键的哈希索引是0，而0、1位置都被占了，这段代码探测到2位置没问题，但如果哈希索引是2，0、1位置空着，它就会直接抛出“表已满”的错误——正确的做法应该是循环整个表，用取模实现环形探测：

// 正确的环形探测逻辑
int index = hash(key) % table.length;
for (int i = 0; i < table.length; i++) {
    int currentIdx = (index + i) % table.length;
    if (table[currentIdx] == null || table[currentIdx].isDeleted()) {
        table[currentIdx] = new Entry(key, value);
        return;
    }
}
throw new IllegalStateException("表已满");

空位置的标记逻辑错误：线性探测哈希表需要区分「从未使用」和「已删除」的位置（如果支持删除操作的话）。要是你删除元素后直接把位置设为null，或者判断空位置时没考虑已删除的标记，就会导致探测过程中跳过了可以复用的位置，明明有空位却插不进去。比如你之前删除过某个元素，但没做特殊标记，探测到那里时误以为是已占用，就继续往后找，最后绕一圈没找到空位。
哈希函数导致的极端冲突：如果三个键的哈希值完全相同，而你的探测逻辑没处理这种极端情况，比如循环次数不够，或者没正确判断所有位置都被占用，就会导致插入失败。不过这种情况概率较低，但也值得排查——可以打印下三个键的哈希值，看看是不是都撞在一起了。
插入时的键存在性判断错误：比如你在插入前会检查键是否已经存在，但判断逻辑写错了，比如把不同的键误判为相同，导致第三个键被当成已存在的键，从而跳过了插入操作。

如果能把你的具体代码贴出来，我还能帮你精准定位问题，但先从上面这几点排查，应该能找到原因！

内容的提问来源于stack exchange，提问作者user5005768-hd