采用线性探测哈希技术的数组已满时，能否继续添加元素？

这问题问得很到位——线性探测哈希表本来就靠空槽来解决冲突，数组全满了乍一看确实走投无路。咱们从实际场景出发，拆解成两种核心情况来聊：

一、允许扩容的情况（推荐方案） #

这是最常规也最合理的解决路径，其实根本不该等数组完全满了才处理——业内最佳实践是当负载因子（已存元素数/数组容量）达到0.7~0.8的阈值时，就触发扩容操作。

• 具体操作逻辑：新建一个容量为原数组2倍（或更大的质数）的新数组，将原数组中所有元素重新哈希（因为哈希函数依赖数组容量）到新数组中，完成后替换原数组。
• 为什么选2倍质数容量？一方面能把负载因子直接降到安全范围，另一方面质数能最大程度减少哈希冲突的概率，避免探测链过长。
• 伪代码示例：

def resize_linear_probe_hash(self):
    old_table = self.table
    new_capacity = len(old_table) * 2
    # 可选：将new_capacity调整为最近的质数
    self.table = [None] * new_capacity
    
    for entry in old_table:
        if entry is not None:
            key, val = entry
            idx = hash(key) % new_capacity
            # 线性探测找空槽
            while self.table[idx] is not None:
                idx = (idx + 1) % new_capacity
            self.table[idx] = (key, val)

• 哪怕真的等到数组全满了才想起扩容，操作逻辑也是一样的，只是遍历原数组时每个位置都有元素，不需要判断空值，完成扩容后就能正常插入新元素了。

二、不允许扩容的极端场景（不推荐，但有临时折中方案） #

如果因为内存限制、硬件约束等特殊原因完全不能扩容，那理论上无法添加新的唯一元素——毕竟没有空槽可供线性探测落脚。但有两种特殊情况可以变通：

• 允许覆盖已有元素：如果业务场景能接受数据丢失（比如缓存场景中淘汰旧数据），可以在探测完所有槽位后，选择覆盖某个符合规则的元素（比如最早插入的、访问频率最低的）。但这是无奈之举，会破坏数据完整性。
• 更新已有键的元素：如果插入的元素键已经存在于哈希表中，那不管数组满不满，都可以通过线性探测找到对应键的位置，直接更新其值——这属于更新操作，不算“添加新元素”。

三、为什么强烈不建议等到数组满了再处理？ #

当线性探测哈希表的负载因子接近1时，探测链的长度会急剧增加，插入、查找操作的时间复杂度会从理想的O(1)退化到O(n)，性能会断崖式下跌。所以提前监控负载因子、阈值触发扩容才是正确的打开方式，而不是等数组全满了再救火。

内容的提问来源于stack exchange，提问作者Atulya Jha