开放寻址法与链地址法的本质区别在于：前者将所有元素存于固定数组中，冲突时在数组内探测空位，删除需标记；后者用指针数组挂链表，冲突时追加节点，删除直接移除，负载因子容忍度更高、更易扩展。
本质区别在于：数据怎么存、冲突怎么安排、空间怎么用。
存储位置与结构设计不同
开放寻址法把所有元素都塞进同一个固定大小的数组里，每个数组位置直接存一个值；链地址法则用数组存“指针”，每个指针指向一条链表，真正存数据的是链表节点。
- 开放寻址法：底层是纯数组，没有额外指针，内存连续，缓存友好
- 链地址法：底层是“指针数组 + 动态链表”，每个桶可挂多个节点，结构更松散
冲突处理逻辑完全不同
开放寻址法遇到冲突就“原地找空位”，在数组内按规则探测下一个位置；链地址法遇到冲突就“另起一行”，把新元素加到对应桶的链表里。
- 开放寻址法探测方式常见有线性（+1）、二次（+i²）、双重哈希（用第二个函数算步长）
- 链地址法插入只管追加到链表尾或头，不干扰其他桶，也不影响探测路径
- 开放寻址法删除必须标记为“已删除”，否则会断掉后续元素的查找路径；链地址法删节点即可，不影响结构
性能与适用场景倾向不同
开放寻址法省空间但怕拥挤，链地址法多占内存但抗冲突能力强。
- 开放寻址法负载因子建议控制在 0.7 以下，否则探测链变长，查找退化明显
- 链地址法负载因子可以更高（比如 1.5 甚至 2.0），只要链表不太长，平均查找仍接近 O(1)
- 开放寻址法适合内存受限、数据量较稳定、读多写少的场景
- 链地址法更适合键值对数量波动大、插入频繁、或无法预估总规模的情况
实现复杂度与扩展性差异
链地址法逻辑直白，增删查都围绕链表操作，容易理解也容易扩展（比如换成红黑树防长链）；开放寻址法看似简单，但探测策略、删除标记、扩容重哈希等细节更容易出错。
- Java 的 HashMap 实际用的是链地址法（JDK 8 起链表过长自动转红黑树）
- Java 的 ThreadLocalMap 内部用的是开放寻址法（线性探测），没有链表开销
- 链地址法天然支持动态扩容后只重哈希键值对，开放寻址法扩容必须整体迁移并重新探测
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
