## 一、底层数据结构:数组 + 链表 + 红黑树

JDK 1.8 的 HashMap 用的是 **数组 + 链表 + 红黑树** 的组合结构。

* **数组** 是主体,数组的每个位置叫一个"桶"(bucket),源码里是 `Node[] table` 。
* 当不同的 key 计算出相同的数组下标(哈希冲突)时,这些元素会以 **链表** 的形式挂在同一个桶下。
* 当链表长度增长到一定阈值,链表会转换成 **红黑树** ,把查询的时间复杂度从 O(n) 优化到 O(log n)。

每个节点 Node 存了四样东西: `hash` (key 的哈希值)、 `key` 、 `value` 、 `next` (指向下一个节点)。

```java
static class Node implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Node next;
}
```

## 二、几个关键的默认值

看源码前先记住几个常量,后面的逻辑都围绕它们展开:

* 默认初始容量: **16** ( `DEFAULT_INITIAL_CAPACITY` )
* 默认负载因子: **0.75** ( `DEFAULT_LOAD_FACTOR` )
* 扩容阈值 threshold = 容量 × 负载因子,初始就是 16 × 0.75 = **12**
* 链表转红黑树的阈值:链表长度 ≥ **8** ( `TREEIFY_THRESHOLD` )
* 红黑树退化为链表的阈值:节点数 ≤ **6** ( `UNTREEIFY_THRESHOLD` )
* 树化的另一个前提:数组长度 ≥ **64** ( `MIN_TREEIFY_CAPACITY` )

**注意** :容量必须是 2 的幂次(16、32、64……),这是后面高效寻址的前提。

## 三、put 一个元素时发生了什么

以 `map.put(key, value)` 为例,大致分四步。

### 1. 计算哈希值(扰动函数)

HashMap 没有直接用 `key.hashCode()` ,而是做了一次"扰动":

```java
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```

这里把 hashCode 的高 16 位和低 16 位做异或。目的是让高位也参与运算,减少哈希冲突。因为下一步寻址只用到了哈希值的低位,如果不搅动,高位的信息就白白浪费了。

### 2. 计算数组下标

```java
index = (n - 1) & hash;   // n 是数组长度
```

这就是为什么容量必须是 2 的幂次:当 n 是 2 的幂时, `n - 1` 的二进制低位全是 1, `(n-1) & hash` 等价于 `hash % n` ,但 **位运算比取模快得多** 。

### 3. 处理哈希冲突

定位到桶之后:

* 如果桶是空的,直接放进去;
* 如果桶里已有元素,说明发生了冲突,就沿着链表往下比对。key 相同( `hashCode` 相等且 `equals` 为 true)就覆盖旧值,否则挂到链表尾部(JDK 1.8 是 **尾插法** ,1.7 是头插法)。

### 4. 判断是否需要树化或扩容

* 如果链表长度达到 8,并且数组长度已经 ≥ 64,链表转成红黑树;若数组长度 (1024)` 之类,避免中途反复扩容带来的性能损耗。注意由于负载因子 0.75 的存在,实际初始容量最好设为 `预估数量 / 0.75` 向上取到 2 的幂。

**4. 不要在遍历时直接增删** 
用 `for` 循环遍历时调用 `map.remove()` 可能抛 `ConcurrentModificationException` ,要删元素请用迭代器的 `iterator.remove()` 。

## 小结

一句话回顾 HashMap 的设计思路: **用数组保证快速寻址,用链表解决哈希冲突,用红黑树兜底极端情况,用 2 倍扩容配合位运算保证效率。**

理解了这套结构,不仅面试时能答得清楚,平时写代码遇到性能问题、并发问题时,也能更快定位到根因。集合框架里像这样"用空间换时间、层层兜底"的设计思想,值得反复琢磨。

HashMap 是 Java 面试里被问得最多的类之一,也是日常开发中用得最频繁的集合。很多人会用 `put` 和 `get`,却说不清它内部到底是怎么存数据的。这篇文章基于 JDK 1.8,把 HashMap 的底层结构、存取过程、扩容机制和常见的坑一次讲透。

一文搞懂 Java HashMap 底层原理:从数组链表到红黑树

后端

前端

JDK1.8 HashMap采用数组+链表+红黑树结构，默认容量16，负载因子0.75。通过扰动函数优化哈希值，位运算快速定位桶位置。链表长度超8且数组长度≥64时转为红黑树，查询效率从O(n)提升至O(logn)。扩容阈值为容量×负载因子，采用2倍扩容机制保证性能。

数据结构

2026上云采购 | AI焕新·智启新局

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

一文搞懂 Java HashMap 底层原理:从数组链表到红黑树-腾讯云开发者社区-腾讯云

一文搞懂 Java HashMap 底层原理:从数组链表到红黑树

一文搞懂 Java HashMap 底层原理:从数组链表到红黑树

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐