用数组实现哈希表的核心是通过取模哈希函数（index = key % table_size）将键映射到质数容量数组下标，冲突时用线性探测（逐个+1取模）解决，空位记0、删除位记-1以保持探测链连贯，负载因子宜≤0.7。

用数组实现简单哈希表，核心是把「键」快速映射到数组下标，并在线性探测机制下处理冲突。它不依赖复杂类库，适合理解底层逻辑，也常用于嵌入式、算法题或教学场景。

数组作为底层存储结构

哈希表本质是一个固定长度的数组，每个位置（桶）存一个值。比如声明 int table[17]，就创建了容量为 17 的哈希表。初始时所有元素设为 0（表示空）或 -1（表示已删除），避免与有效数据混淆。

• 数组索引即哈希地址，由哈希函数计算得出，最常用的是取模：index = key % table_size
• 数组大小建议选质数（如 17、97、101），能减少同余冲突，提升分布均匀性
• 不能直接用 key 当索引（如 key=1000000 就需百万级数组），所以必须通过哈希函数压缩

线性探测解决哈希冲突

当两个不同 key 经哈希后落到同一索引，就发生冲突。线性探测的做法是：从原位置开始，逐个检查下一个位置（index = (index + 1) % table_size），直到找到空位或确认不存在。

• 插入：算出初始 index → 若位置非空（既不是 0 也不是 -1），继续 +1 探测 → 找到空位后填入
• 查找：同样从初始 index 开始 → 匹配则返回；遇 0（空）则停止（说明该 key 未存）；遇 -1（已删）则继续探查
• 删除：不能直接清零（否则会截断后续查找链），要标记为 -1，保持探测路径连贯

关键操作示例（Java 简化版）

以下逻辑可直接运行验证：

• insert(23)：若 table_size=17，则 23%17=6 → 若 table[6] 已被占，试 table[7]、table[8]…直到空位
• find(40)：40%17=6 → 查 table[6]≠40 → table[7]≠40 → …→ 若某处为 0，返回未找到
• delete(7)：7%17=7 → 找到 table[7]==7 → 设为 -1，不破坏后续对其他 key（如 24→24%17=7）的探测路径

注意事项与优化提示

线性探测易引发“一次聚集”——连续占用块越多，新插入越容易挤进该区域，进一步加剧堆积。实际使用中要注意：

• 负载因子（已存元素数 / 数组长度）建议控制在 0.7 以内，超限及时扩容重哈希
• 初始化时将数组全置为 0 或 -1，避免读取未初始化内存导致不可预测行为
• 若 key 可能为负数（如 Java 中 key % size 可能为负），应先做 (key % size + size) % size 校正
• 仅适用于整型 key 场景；字符串等类型需先转成整数哈希码（如 s.hashCode()）再取模