Java中用一维数组实现哈希表采用线性探测法处理冲突，通过取模哈希函数映射键值，用-1表示空位、-2表示已删除（墓碑），插入找空位、查找遇-1终止、删除设墓碑，负载因子超0.7需扩容重哈希。
Java 中用一维数组实现简单哈希表，核心在于把键（key）映射到数组下标，并妥善处理多个 key 落到同一位置的情况——也就是哈希冲突。最直接、易理解的方式是线性探测法，它不依赖额外数据结构（如链表），仅靠数组自身“找空位”，适合教学和轻量场景。
用一维数组模拟哈希表的基本结构
定义一个整型数组 table，初始值全为 -1（表示空位）。容量设为质数（如 17）有助于减少规律性冲突。哈希函数取模即可：
int hash(int key) { return key % table.length; }
插入、查找、删除都从该哈希值对应下标出发，按需向后探测。
线性探测解决冲突的三步操作
当 table[hash(key)] 已被占用时，不是报错或扩容，而是顺序检查下一个位置，直到找到空位或确认目标不存在：
- 插入（insert）：从 hash(key) 开始，逐个检查 table[(index + i) % table.length]，遇到 -1 就写入；
- 查找（find）：同样从 hash(key) 开始比对，遇到 -1 表示该 key 一定不存在（因为插入时不会跳过空位）；
- 删除（delete）：不能直接置为 -1，否则会截断后续 key 的探测路径（比如 24 和 7 都映射到索引 7，删掉 7 后，24 就查不到了）；应改用特殊标记（如 -2）表示“已删除但可覆盖”。
为什么不能随便清空已删位置
假设数组长度为 17，key=7 和 key=24 都满足 7%17==24%17==7。若先插入 7，再插入 24，它会落在 table[8]。此时若删除 7 并设 table[7] = -1，后续查找 24 时，从 index=7 开始查，发现 -1 就立刻返回“未找到”，实际 24 还在 table[8]。所以必须保留“墓碑”标记（-2），让查找继续往后走。
负载因子与性能提醒
数组填得太满，线性探测平均要试很多次，查找退化为 O(n)。实践中建议负载因子（元素数 / 数组长度）不超过 0.7。一旦超限，应复制到更大数组并全部 rehash——这步虽重，但能维持均摊 O(1) 性能。简单实现中可手动触发，生产环境则需自动扩容逻辑。
立即学习“Java免费学习笔记（深入）”；
