一篇看懂 Java HashMap 原理：底层结构、存取流程与面试高频考点

 

HashMap 是 Java 集合框架中最常用、面试出镜率最高的实现类，以**键值对（Key-Value）**形式存储数据，具备查询快、插入快、删除快的特点，但线程不安全、不保证有序。本文从底层结构、哈希计算、存取流程、扩容机制、常见问题等方面，彻底讲透 HashMap 原理。

 

 

 

一、HashMap 核心定位

 

- 存储形式： key → value  映射，key 唯一、允许为 null（最多一个 null key，多个 null value）

- 线程安全：非线程安全，多线程下建议用  ConcurrentHashMap 

- 有序性：不保证插入顺序，遍历顺序随扩容可能变化

- 底层结构：- JDK 1.7：数组 + 链表

- JDK 1.8：数组 + 链表 + 红黑树（链表过长自动转树，提升查询效率）

 

 

 

二、底层数据结构详解

 

1. 核心组成

 

1. 哈希表（数组）- 是 HashMap 的主体，称为“桶（bucket）”

- 下标由  key  的哈希值计算得出，是 O(1) 定位的基础

2. 链表- 解决哈希冲突：不同 key 算出相同下标时，用链表串起来

3. 红黑树- JDK 1.8 新增：当链表长度 ≥ 8 且数组长度 ≥ 64 时，自动转为红黑树

- 目的：避免长链表导致查询退化为 O(n)，红黑树查询为 O(logn)

 

2. 关键常量（JDK 1.8）

 

- 默认初始容量： 16 （必须是 2 的 n 次方）

- 默认加载因子： 0.75 （时间与空间平衡的经验值）

- 树化阈值： 8 （链表转红黑树）

- 解树阈值： 6 （红黑树退化为链表）

- 最小树化容量： 64 （数组长度不足 64 优先扩容，不树化）

 

 

 

三、哈希计算与下标定位（核心）

 

1. 哈希值计算

 

HashMap 不直接使用  hashCode() ，而是做一次扰动函数：

 

java

static final int hash(Object key) {

    int h;

    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

 

 

- 高 16 位与低 16 位异或，让哈希分布更均匀，减少冲突

-  key == null  固定存在下标 0 位置

 

2. 数组下标计算

 

java

index = hash & (table.length - 1)

 

 

- 等价于取模，但位运算更快

- 因为数组长度永远是 2 的 n 次方， length-1  低位全 1，保证下标分布均匀

 

 

 

四、put 存值完整流程（JDK 1.8）

 

1. 数组为空时，执行第一次扩容，初始化容量为 16

2. 根据 key 计算哈希值与数组下标

3. 如果当前桶为空，直接新建节点放入

4. 如果桶不为空：- 若 key 已存在，覆盖旧 value

- 若是红黑树，执行树的插入

- 若是链表，尾插法追加（JDK 1.7 是头插）

5. 链表长度 ≥ 8 且数组长度 ≥ 64，链表转红黑树

6. 插入后判断元素数量 > 阈值（容量 × 加载因子），执行扩容

 

 

 

五、get 取值流程

 

1. 根据 key 计算哈希与下标

2. 定位到对应桶

3. 首节点 key 匹配，直接返回 value

4. 若是红黑树，树中查找

5. 若是链表，遍历查找

6. 找不到返回 null

 

 

 

六、扩容机制（最关键考点）

 

1. 什么时候扩容

 

- 元素个数 > 容量 × 加载因子（默认 16 × 0.75 = 12）

- 数组长度不足，树化前优先扩容

 

2. 扩容做什么

 

- 新建数组，容量变为原来 2 倍

- 重新计算所有节点下标，迁移到新数组

- JDK 1.8 优化：节点要么在原下标，要么在 原下标 + 旧容量，无需重新全部 hash

 

3. 为什么长度必须是 2 的 n 次方

 

1. 下标计算  hash & (len-1)  效率极高

2. 扩容时重新分配下标更简单、均匀

3. 减少哈希冲突，提高查询效率

 

 

 

七、哈希冲突与解决办法

 

1. 什么是哈希冲突

 

不同 key 计算出相同数组下标，称为冲突。

 

2. HashMap 解决方案

 

- JDK 1.7：链地址法 + 头插法

- JDK 1.8：链地址法 + 尾插法 + 红黑树

- 配合扰动函数、2 次方位运算，尽量减少冲突

 

 

 

八、JDK 1.7 与 JDK 1.8 区别（必背）

 

1. 结构：1.7 数组+链表；1.8 数组+链表+红黑树

2. 插入：1.7 头插；1.8 尾插（避免多线程扩容链表成环）

3. 扩容重 hash：1.7 重新计算；1.8 简化迁移规则

4. 哈希冲突：1.8 长链表性能大幅提升

5. 并发风险：1.7 扩容可能链表成环、死循环；1.8 仍非线程安全

 

 

 

九、高频面试问题总结

 

1. HashMap 线程不安全表现？- 数据覆盖、丢失

- JDK 1.7 扩容可能出现链表环，导致 CPU 100%

2. 为什么加载因子是 0.75？- 冲突概率、空间利用率、性能三者平衡，泊松分布统计经验值

3. HashMap、HashTable、ConcurrentHashMap 区别？- HashTable：线程安全（全表锁）、效率低、不允许 null key/value

- ConcurrentHashMap：线程安全、分段锁/ CAS + synchronized、高并发

4. 为什么重写 equals 必须重写 hashCode？- 相等对象必须有相同 hashCode，否则 HashMap 无法正常存取

5. HashMap 如何保证 key 唯一？- 先比较 hashCode，再用 equals 判断，相同则覆盖

 

 

 

十、总结

 

HashMap 核心就是一句话：

数组做主存，哈希定位置，链表解冲突，红黑树提性能，扩容保效率。

 

理解它的哈希算法、下标定位、put/get 流程、扩容规则与树化机制，就能彻底掌握 HashMap 原理，无论是日常开发还是面试都能轻松应对。