JAVA中的hashmap怎么实现的？｜阿里巴巴后端开发面经解析

60 秒回答模板

Java 中的 HashMap 本质上是一个基于哈希表的 key-value 容器。JDK8 以后，它的底层结构可以概括为数组加链表加红黑树：数组是主存储区，每个数组位置叫桶；不同 key 经过 hash 计算后可能落到同一个桶，少量冲突时用链表串起来，冲突过多时会把链表转换成红黑树来降低查询复杂度。put 时先对 key 的 hashCode 做扰动，让高位信息参与低位运算，再用数组长度减一与 hash 做按位与确定桶下标。如果桶为空就直接插入；如果桶中已有元素，就比较 hash 和 equals，key 相同则覆盖 value，不同则追加到链表或插入红黑树。get 时同样计算 hash 和桶下标，然后在桶内按 key 匹配查找。HashMap 默认负载因子是 0.75，当 size 超过 capacity 乘以 loadFactor 的阈值时触发扩容，通常容量翻倍。因为容量保持为 2 的幂，定位可以用位运算，并且扩容时元素只会留在原下标或移动到原下标加旧容量的位置。需要注意，链表树化不只看长度达到 8，还要求数组容量至少 64，否则优先扩容。HashMap 不是线程安全的，并发 put、resize 可能导致数据丢失、覆盖异常或结构不一致，多线程场景应使用 ConcurrentHashMap。

考点 底层结构

主线 hash 扰动与桶定位

易错点 只说 HashMap 是数组加链表，忽略 JDK8 以…

深入解析

底层结构

HashMap 的主结构是一张 Node 数组，每个数组槽位代表一个桶。桶里保存具有相同或相近定位结果的节点。没有冲突时，一个桶只有一个节点；发生冲突后，节点会以链表形式连接；JDK8 以后，当单个桶的链表过长且表容量达到要求时，链表会转换为红黑树。这样既保留了哈希表平均 O(1) 的访问特性，又在极端冲突时避免链表退化成线性扫描。

hash 扰动与桶定位

HashMap 不直接拿 key 的 hashCode 定位数组，而是会做一次扰动计算，典型形式是让 hashCode 的高 16 位与低 16 位异或。原因是数组下标通常通过 hash 与 length-1 做按位与得到，如果数组长度较小，只用低位会浪费高位信息。扰动可以让高位参与定位，降低冲突概率。容量保持为 2 的幂，是为了让取模等价于位运算，提升定位效率并简化扩容后的迁移判断。

put 写入流程

put 时先处理 key 的 hash，若 table 还未初始化会先创建数组，然后根据 hash 定位桶位。桶为空时直接放入新节点；桶不为空时，先检查第一个节点是否与当前 key 相同，判断依据是 hash 相同并且 key 相等或 equals 返回 true。若第一个节点不匹配，就继续在链表或红黑树中查找。找到相同 key 就覆盖旧值，找不到则新增节点。新增后 size 增加，并根据阈值判断是否需要 resize。

get 查询流程

get 的流程与 put 的前半段一致：先根据 key 计算扰动后的 hash，再通过数组长度定位到桶。若桶为空，直接返回 null；若桶首节点匹配 key，则直接返回 value；否则根据桶内结构继续查找。如果是链表，就逐个比较 hash 与 equals；如果是红黑树，就按照树节点逻辑查找。HashMap 查询快的前提是 hash 分布均匀，如果大量 key 落入同一桶，性能会明显下降。

扩容 resize

HashMap 通过容量和负载因子控制空间与冲突的平衡。默认负载因子是 0.75，阈值通常是 capacity 乘以 loadFactor。当元素个数超过阈值时，HashMap 会扩容，常见情况是容量翻倍。JDK8 的扩容迁移比较高效，因为新容量是旧容量的两倍，一个节点在新数组中的位置只取决于 hash 与 oldCap 这一位是否为 0：为 0 留在原下标，为 1 移到原下标加 oldCap。

树化与退化

链表转红黑树并不是只看链表长度。JDK8 中，桶内节点数达到树化阈值 8 时，如果数组容量小于最小树化容量 64，HashMap 通常会优先扩容，而不是马上树化。这样做是因为很多冲突可以通过扩大数组自然分散，没必要过早引入红黑树的维护成本。红黑树在删除或扩容拆分后，如果节点数变少，也可能退化回链表，以减少小规模桶位上的额外开销。

相等性契约

HashMap 判断 key 是否相同，不能只看 hashCode，也不能只看 equals。通常会先比较 hash 是否相同，再用 == 或 equals 判断 key 的逻辑相等性。因此自定义对象作为 key 时，必须遵守 equals 与 hashCode 的契约：equals 相等的对象必须有相同 hashCode。如果只重写 equals 不重写 hashCode，逻辑相等的 key 可能落到不同桶，导致 get 取不到、put 无法覆盖旧值等问题。

线程安全风险

HashMap 不是线程安全容器。多个线程同时 put、remove 或 resize 时，可能出现覆盖丢失、读到中间状态、size 不准确、结构不一致等问题。早期实现中并发扩容还可能引发链表环等严重异常。即使 JDK8 改进了迁移方式，也不能把 HashMap 当成并发容器使用。多线程读写应选择 ConcurrentHashMap，或者在外部加锁，但通常优先使用专门的并发集合。

易错点

只说 HashMap 是数组加链表，忽略 JDK8 以后链表过长会转换为红黑树。
把树化条件简单记成链表长度达到 8，忘记最小树化容量 64 这个限制。
认为 hashCode 相同就代表 key 相同，忽略最终还需要 == 或 equals 判断。
只重写 equals 不重写 hashCode，导致自定义对象作为 key 时查询和覆盖异常。
把扩容理解成简单复制数组，没有说明容量翻倍后元素会重新分布到新桶位。
在多线程场景直接使用 HashMap，忽略并发 put 和 resize 可能造成的数据风险。

面试官追问

为什么 HashMap 的容量通常是 2 的幂？

容量是 2 的幂时，hash 对容量取模可以转换成 hash 与 length-1 的按位与运算，效率更高。同时，扩容翻倍后元素迁移也更容易判断，只需要看 hash 与旧容量对应的那一位，元素要么留在原位置，要么移动到原位置加旧容量。

HashMap 为什么要做 hash 扰动？

桶下标主要依赖 hash 的低位，如果直接使用 hashCode，在数组容量较小时，高位信息可能完全参与不到定位中。扰动操作把高位信息混入低位，可以改善分布，减少不同 key 集中落入同一桶的概率，从而降低冲突。

链表什么时候会变成红黑树？

JDK8 中，当桶内链表节点数达到树化阈值 8 时，HashMap 会考虑树化。但如果当前数组容量还小于 64，通常会优先扩容，因为扩容后冲突可能自然分散。只有链表足够长且容量足够大时，才会转换为红黑树。

HashMap 的 get 一定是 O(1) 吗？

不是严格一定。HashMap 的平均查询复杂度接近 O(1)，前提是 hash 分布较均匀、冲突较少。若大量 key 落入同一个桶，链表情况下查询会退化为 O(n)。JDK8 引入红黑树后，严重冲突时桶内查询可改善到 O(log n)。

HashMap 和 ConcurrentHashMap 的主要区别是什么？

HashMap 面向单线程或外部同步场景，本身不保证并发安全；ConcurrentHashMap 是并发容器，针对多线程读写做了同步控制和可见性设计。多个线程同时修改普通 HashMap 可能导致数据丢失或结构异常。