JavaHashMap实现：数组链表与哈希定位详解

本文深入剖析了Java中HashMap底层原理的手动实现过程，聚焦于数组+链表结构如何通过哈希定位（hash & (length-1)）、冲突处理（头插法链表）、键值比对（先hash后equals的双重校验）以及扩容机制（必须rehash且长度翻倍）等核心环节确保高效存取；同时直击常见致命误区——如未重写equals导致get失效、可变key引发定位失败、用==替代equals、不规范扩容引发死循环等，带你从零写出健壮的HashMap，真正吃透JDK源码背后的设计逻辑与工程权衡。

怎么用数组+链表手动实现 HashMap 的 put 和 get

核心就是两步：哈希值算下标、冲突了就链表头插。Java 里 Object.hashCode() 默认返回内存地址相关整数，直接对数组长度取模就能定位——但得保证数组长度是 2 的幂，否则取模等价于位运算，性能才稳。

实操建议：

• 初始化数组用 new Node[16]，别用 new Node[15]，否则 hash & (length - 1) 会出错
• put() 里先算 index = hash & (table.length - 1)，不是 hash % table.length，负 hash 会导致负下标
• 链表节点用静态内部类 Node，含 key、value、next，别漏 next 字段，否则链不起来
• 查找时必须逐个比对 key.equals()，不能只看 hash 值，因为不同 key 可能 hash 相同

为什么 get() 要先判 hash 再判 equals

这是为了快速失败。hash 不等，key 肯定不等；hash 相等只是可能相等，还得靠 equals() 确认。如果跳过 hash 判断，每次都要调 equals()，而字符串或自定义对象的 equals() 往往更重。

常见错误现象：

• 重写了 hashCode() 没重写 equals() → get() 找不到已存的 key（因为 hash 对上了，但 equals 返回 false）
• key 是可变对象（比如没设 final 的 StringBuffer），存完改了内容 → hash 变了，get() 去老下标找，链表里遍历也匹配不上
• 用 == 替代 equals() 判 key → 基本类型包装类如 Integer 在 [-128, 127] 外会新建对象，== 必然 false

扩容时为什么必须 rehash 并重新计算 index

数组长度变了，hash & (length - 1) 的结果就变了。比如原长度 4，hash=5 → 5 & 3 = 1；扩容到 8 后，5 & 7 = 5，位置完全不同。不 rehash 就找不到数据。

性能影响明显：

• 扩容触发条件一般是 size >= threshold（默认 0.75 * capacity），别设成 1.0，否则链表容易过长
• rehash 时旧链表要整体拆成两个新链表（高位为 0 或 1），不是简单复制，否则并发下会死循环（JDK 7 的经典 bug）
• 新数组长度必须翻倍（newCap = oldCap ），才能继续用 & (length - 1) 替代取模

哪些地方最容易空指针或越界

最常崩在三处：数组未初始化、链表遍历时 next 为 null 还继续 .next、hash 为 Integer.MIN_VALUE 时取反溢出。

防御写法：

• table 声明后必须在构造方法里初始化，别留 null，否则 table[index] 直接 NPE
• 遍历链表必须写成 for (Node e = table[index]; e != null; e = e.next)，别漏 e != null 判断
• 算 hash 别直接用 key.hashCode()，先做扰动：h = key.hashCode() ^ (key.hashCode() >>> 16)，缓解低比特位分布不均
• 下标计算前加 if (table == null) resize();，避免首次 put 就崩

真正难的不是写出来，是想清楚每个 next 指向谁、每次 resize() 后旧节点怎么落到新桶里。手写一遍，再去看 JDK 7 的 transfer 方法，就明白为啥它怕并发了。

今天关于《JavaHashMap实现：数组链表与哈希定位详解》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！