HashMap 的底层实现原理是什么？｜阿里巴巴后端开发面经解析

60 秒回答模板

HashMap 底层本质是哈希表，存的是 key-value。它先对 key 计算 hash，再通过数组长度减一与 hash 做位运算，定位到 table 数组中的某个桶。如果这个桶为空，就直接放入节点；如果不为空，就说明发生了哈希冲突，需要在桶内比较 hash 和 equals，key 相同则覆盖 value，key 不同则追加到链表或红黑树中。JDK 1.7 的 HashMap 结构是数组加链表，冲突节点用链表存储，插入通常是头插法，扩容时需要重新计算位置，多线程并发扩容可能导致链表成环，所以它不是线程安全的。JDK 1.8 做了几个重要优化：底层变为数组加链表加红黑树；链表长度达到树化阈值且数组容量足够时会转成红黑树；链表插入改为尾插法；扩容时节点只会留在原下标或移动到原下标加旧容量的位置，减少重新哈希成本。默认容量是 16，默认负载因子是 0.75，容量通常保持 2 的幂，这样可以用位运算快速取模并让扩容迁移更高效。面试时还要强调，HashMap 允许一个 null key 和多个 null value，但不保证遍历顺序，也不适合并发写场景，并发场景应该使用 ConcurrentHashMap。

考点 整体结构

主线 定位流程

易错点 只说 HashMap 是数组加链表，忽略 JDK 1.…

深入解析

整体结构

HashMap 的底层是一个 table 数组，数组中的每个位置称为桶。每个桶保存一个节点引用，节点里包含 hash、key、value 和 next 等信息。理想情况下，不同 key 被均匀分散到不同桶中，查找、插入、删除接近 O(1)。但不同 key 可能算到同一个桶，这就是哈希冲突，HashMap 通过链地址法处理冲突：同一个桶内的多个节点形成链表，JDK 1.8 在冲突严重时还会把链表转为红黑树。

定位流程

put 一个元素时，HashMap 会先处理 key 的 hash 值，再用数组长度参与下标计算。因为容量保持为 2 的幂，所以可以用 hash 与 length - 1 做位运算来得到下标，相当于更快的取模。定位到桶后，如果桶为空就直接创建节点；如果桶不为空，就逐个比较桶内节点的 hash 和 key，相同则覆盖旧 value，不同则挂到冲突结构中。get 时流程类似，先定位桶，再在桶内继续查找目标 key。

冲突处理

哈希冲突不可避免，因为 key 的取值空间远大于数组桶数量。JDK 1.7 中同一个桶的冲突节点统一用链表保存，桶内查找需要顺着链表比较，冲突越多性能越差。JDK 1.8 保留链表作为低冲突场景的简单结构，但当单个桶里的链表长度达到阈值，并且 table 容量达到最小树化容量时，会把链表转换成红黑树。这样极端冲突下的桶内查找可以从 O(n) 降到 O(log n)，代价是节点结构更重、维护逻辑更复杂。

扩容机制

HashMap 通过容量和负载因子控制扩容，默认容量是 16，默认负载因子是 0.75，阈值通常等于 capacity 乘 loadFactor。当元素数量超过阈值时，会触发扩容，通常把数组容量扩大为原来的两倍。扩容不是简单复制数组，因为数组长度变了，下标计算结果也可能变化，所以旧节点需要迁移到新 table。JDK 1.8 利用容量为 2 的幂这个条件，让节点只在原位置和原位置加旧容量之间二选一，降低迁移成本。

JDK 1.7 特点

JDK 1.7 的 HashMap 主要是数组加链表，节点类型常称为 Entry。发生冲突后，新节点通常采用头插法放到桶链表头部。头插法实现简单，插入成本低，但在扩容迁移时会改变链表顺序。由于 HashMap 本身没有同步控制，如果多个线程同时 put 或 resize，可能出现数据覆盖、元素丢失，严重时还可能因为链表成环导致 get 操作死循环。因此 JDK 1.7 的 HashMap 在并发写场景中风险很高。

JDK 1.8 优化

JDK 1.8 的 HashMap 把底层结构升级为数组加链表加红黑树，节点类型变为 Node，并引入 TreeNode 支持树化。它在桶内链表较短时仍使用链表，因为链表内存开销小、维护简单；只有冲突足够严重时才树化，以平衡空间和时间成本。JDK 1.8 链表插入更偏向尾插法，扩容迁移时也通过高低位拆分保留相对顺序，降低了 JDK 1.7 并发扩容时链表反转带来的成环风险，但这并不意味着 HashMap 变成线程安全。

边界取舍

HashMap 的设计是在速度、内存和复杂度之间折中。数组提供快速定位，但太大会浪费空间，太小会冲突严重；负载因子越高越省空间，但冲突概率增加，查询性能下降；红黑树能改善极端冲突，但节点更复杂，旋转和比较也有成本，所以不会一冲突就树化。HashMap 允许 null key，通常落在下标 0 的桶位；它不保证顺序，也不能依赖遍历结果稳定。如果需要有序，可以考虑 LinkedHashMap 或 TreeMap；如果需要线程安全，应考虑 ConcurrentHashMap。

易错点

只说 HashMap 是数组加链表，忽略 JDK 1.8 已经引入红黑树。
把 hashCode 相同和 key 相同混为一谈，忘记最终还要 equals 判断。
误以为链表长度达到 8 一定树化，忽略最小树化容量这个条件。
说 JDK 1.8 解决了并发问题，因此 HashMap 可以多线程随便写。
只背默认容量和负载因子，不会解释为什么容量要保持 2 的幂。
把 HashMap、Hashtable、ConcurrentHashMap 的线程安全语义混在一起。

面试官追问

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

主要是为了高效计算下标和简化扩容迁移。容量是 2 的幂时，hash 与 length - 1 做位运算即可得到桶下标，效果类似取模但效率更高。同时扩容为两倍后，节点新位置只取决于 hash 的某一位，迁移时只会留在原下标或移动到原下标加旧容量。

JDK 1.8 为什么引入红黑树，而不是一直用链表？

链表在冲突少时很轻量，插入和维护成本低，但冲突严重时查找需要线性遍历，性能会明显下降。红黑树可以把桶内查找从 O(n) 降到 O(log n)，适合极端冲突场景。JDK 1.8 只在链表足够长且容量足够大时树化，就是为了避免过早付出树结构的内存和维护成本。

JDK 1.7 和 JDK 1.8 的 HashMap 最大区别是什么？

核心区别有三点：第一，JDK 1.7 是数组加链表，JDK 1.8 是数组加链表加红黑树；第二，JDK 1.7 链表插入偏头插法，扩容迁移可能反转链表，JDK 1.8 更偏尾插并保留相对顺序；第三，JDK 1.8 扩容时利用高低位拆分，迁移效率和极端冲突性能都更好。

HashMap 为什么不是线程安全的？

因为它的 put、remove、resize 等操作没有整体同步控制，也没有保证并发修改下的结构一致性。多个线程同时修改同一个 HashMap 时，可能同时操作同一个桶、同时触发扩容或覆盖彼此的更新，导致数据丢失、读到旧值、结构异常。需要并发访问时，通常应该使用 ConcurrentHashMap。

HashMap 的 put 过程能完整描述一下吗？

put 时先计算 key 的 hash，然后根据 table 长度定位桶。如果 table 还没初始化，会先初始化。桶为空时直接放入新节点；桶不为空时，先判断桶首节点是否 key 相同，相同则覆盖；否则看桶结构是链表还是红黑树，分别执行链表追加或树节点插入。插入后 size 增加，超过阈值则触发扩容。