当前位置：首页 > news >正文

【Java】HashMap的详细介绍

news 2025/8/16 9:09:07

一.HashMap

1.基本概念

2.底层数据结构：

3.HashCode和equals方法

为什么重写HashCode方法？

为什么重新equals方法？

4.put操作

1.初始化和数组检查

2.计算索引并检查桶是否为空

3.桶不为null，处理哈希冲突

4.判断链表是否转化红黑树

5.以及数组大小是否超过阈值进行扩容

5.get操作

java1.7 -- java1.8 HashMap 做了哪些优化：

哈希值计算：

链表插入方式：

二.ConcurrentHashMap

1.Java 1.7 ConcurrentHashMap架构：

2.Java 1.8 ConcurrentHashMap架构：

CAS+synchronized的使用场景：

扩容区别：

size()区别：

一.HashMap

1.基本概念

HashMap是基于哈希表实现的Map接口，用于存储键值对（K-V）格式，其核心作用就是通过哈希函数为了更快查询到某个元素，时间复杂度O(1);

2.底层数据结构：

在java（1.7）之前底层是采用“数组 + 链表” 的形式存储

但在java（1.8）之后，变成了“数组 + 链表 + 红黑树 ”形式存储

我们主要了解java1.8之后的内容；

从源码上查看

数组的初始容量为16，负载因子为0.75，所以当超过这个阈值 16 * 0.75 = 12
设计初始容量为16核心原因是2 的幂次方更适合哈希计算，能减少哈希冲突，但8又太频繁扩容，新增性能开销，而32空间又会太大，则浪费空间~
负载因子也是同理，太小，会频繁扩容，虽然查询快了，但是数组太稀疏，浪费空间，而太大，就会扩容少，空间利用率高，但查询会变慢~

当插入第13个元素的时候，已经超过阈值，为了避免哈希冲突，会进行扩容~

然后这边当数组大小超过64时候，链表大小超过8的时候，会从链表进化成红黑树，但当元素个数少于6个时，会退回链表~

链表长度≥8
基于泊松分布，当负载因子为 0.75 时，链表长度自然增长到 8 的概率极低（约千万分之一），此时说明哈希冲突异常频繁，需要转为红黑树优化。
数组容量≥64
若数组容量小于 64（如 32），即使链表长度≥8，也会先触发扩容（而非转红黑树）。原因是：数组容量小时，扩容成本低，通过扩容可分散元素，减少冲突；而红黑树的维护成本（插入 / 删除时的旋转操作）高于扩容，此时扩容更高效。

3.HashCode和equals方法

HashMap中的键一定会实现这俩个方法，hashCode用于计算存储的位置，而equals用于判断来个键是否相同，在put方法的时候，如果俩个哈希值相同，会判断是否是同一个值，如果不是就会放在同一个桶中的不同位置，如果相同就是一个东西~

为什么重写HashCode方法？

如果不重写，这个时候，就会导致俩个相同的key，会被计算出俩个不同的哈希值，导致他们存在在不同的桶中，到时候查询的时候到底是查哪个？

为什么重新equals方法？

equals方法是为了当出现哈希冲突的时候，俩个key的哈希值相同，放在同一桶中，但没有比较它们的对象，可能会误判会导致俩个key存储在不同位置，所以没有覆盖之前的值，就会错误~

class Person {String name;int age;@Overridepublic int hashCode() { // 重写hashCode，保证逻辑相等的对象哈希值相同return Objects.hash(name, age);}// 未重写equals()
}public static void main(String[] args) {HashMap<Person, String> map = new HashMap<>();Person p1 = new Person("张三", 20);Person p2 = new Person("张三", 20);map.put(p1, "学生");map.put(p2, "工人"); // 哈希值相同，进入同一个桶，但equals判断为不同keySystem.out.println(map.size()); // 仍输出2，而非预期的1
}

hashCode()和equals()必须配套重写，且满足以下规则：

一致性：如果两个对象通过equals()判断为相等，则它们的hashCode()必须返回相同的值；
对称性：如果a.equals(b)为true，则b.equals(a)也必须为true；
非空性：a.equals(null)必须返回false。

4.put操作

1.初始化和数组检查

首先判断 HashMap 是否未初始化（table 数组为 null 或长度为 0），若是则触发初始化（resize）：

2.计算索引并检查桶是否为空

如果该位置为空，直接创建新节点插入

3.桶不为null，处理哈希冲突

检查首节点：若首节点的 key 与传入 key equals 相等（且哈希值相同），则视为 “重复 key”，记录该节点（后续替换其 value）。
遍历后续节点：
- 若桶是单链表（Node）：遍历链表，若找到 key 相等的节点，记录该节点；若遍历到链表尾部仍未找到，则在链尾插入新节点（Node）。
- 若桶是红黑树（TreeNode）：调用红黑树的插入方法（putTreeVal），若找到重复 key 则记录节点，否则插入新树节点。
处理重复 key：若步骤 1 或 2 中找到重复 key 的节点，用新 value 替换其旧 value，流程结束。

4.判断链表是否转化红黑树

5.以及数组大小是否超过阈值进行扩容

5.get操作

同理get 方法的核心逻辑是：
哈希计算→定位桶→根据桶结构（链表 / 红黑树）查找匹配节点

java1.7 -- java1.8 HashMap 做了哪些优化：

哈希值计算：

1.7版本：对 key 的原始哈希值（hashCode() 结果）进行 4 次扰动（多次移位和异或运算）

1.8版本：简化为 1 次扰动，仅通过一次 “高 16 位与低 16 位异或” 实现混合

减少计算开销：一次异或运算即可达到近似的混合效果，相比 1.7 的 4 次运算，计算效率更高。
实际效果：在大多数场景下，1 次扰动已能保证哈希值的均匀分布，同时降低了 CPU 运算成本。

链表插入方式：

由头插变成尾插，核心是为了解决多线程扩容时的链表环化问题，同时让链表操作逻辑更合理。

多线程扩容时可能导致链表环化（死循环）。
扩容过程中，节点会从旧数组迁移到新数组，头插法在迁移时会反转链表顺序（例如旧链表 A→B，迁移后新链表变为 B→A）。若此时有多个线程同时操作，可能出现节点引用相互指向的情况（如 A.next = B 且 B.next = A），形成环形链表。后续查询时，线程会陷入无限循环，导致 CPU 占用飙升。

二.ConcurrentHashMap

ConcurrentHashMap 是 Java 中用于并发场景的哈希表实现，专为高并发环境设计；

1.Java 1.7 ConcurrentHashMap架构：

在java1.8之前 ConcurrentHashMap 采用的是 分段数组（Segment）+ 哈希表，默认为16个segment，同时支持16个并发~

整体结构：ConcurrentHashMap -> Segment[] -> HashEntry[] -> 链表。

写操作（put/remove 等）：
1. 计算 key 的哈希值，定位到对应的 Segment；
2. 获取该 Segment 的锁（若被占用则阻塞）；
3. 在 Segment 内部的哈希表中执行插入 / 删除（类似 HashMap 的逻辑，链表头插法）；
4. 释放锁。

优点：通过分段锁实现了多线程并发写，效率比全表锁（如 Hashtable）高得多。
缺点：
- 锁粒度仍较大（以 Segment 为单位），若多个线程操作同一 Segment，仍会阻塞；
- 结构复杂，维护成本高；
- 扩容仅针对单个 Segment，但整体性能受限于 Segment 数量。

2.Java 1.8 ConcurrentHashMap架构：

摒弃了 Segment 分段结构，底层直接使用数组 + 链表 + 红黑树（与 JDK 1.8 HashMap 结构类似）

锁的粒度更小，锁的是桶的头节点，并且采取了CAS + synchronized 机制，仅当多个线程操作同一链表 / 红黑树时才会竞争锁，锁冲突概率远低于 1.7 的 Segment 级锁。

CAS+synchronized的使用场景：

无冲突场景（空桶插入、初始化、低并发计数）：用 CAS 实现高效无锁操作。
有冲突场景（非空桶操作、复杂结构修改）：用 synchronized 加锁保证原子性。

版本	底层架构	哈希表数量	锁粒度
JDK 1.7 及之前	两层结构：Segment [] 数组 + 每个 Segment 包含一个 HashEntry [] 数组	多个（默认 16 个，与 Segment 数量一致）	Segment 级（锁整个子哈希表）
JDK 1.8 及之后	单层结构：Node [] 数组（链表 / 红黑树解决冲突）	1 个（整个 ConcurrentHashMap 共用一个底层数组）	节点级（锁链表头节点或红黑树根节点）

扩容区别：

特性	JDK 1.7 扩容	JDK 1.8 扩容
扩容范围	单个 Segment 独立扩容	整个数组全表扩容
并发能力	单线程扩容（当前操作 Segment 的线程）	多线程协同扩容（所有线程可协助迁移）
锁影响范围	仅锁定当前 Segment，其他 Segment 可用	无全局锁，仅锁定迁移中的桶节点
迁移效率	单个 Segment 迁移，效率较低	多线程分片迁移，效率更高
节点迁移方式	头插法（可能反转链表）	尾插法（保持链表顺序，无环化风险）
与读写的兼容性	扩容时该 Segment 读写阻塞	扩容与读写可并行（读无锁，写锁单个桶）

size()区别：

在JDK 1.7 中，ConcurrentHashMap 由多个 Segment 组成，每个 Segment 独立维护自己的元素数量（count），因此计算总 size 时需要累加所有 Segment 的 count。

为减少误差，JDK 1.7 采用 “重试机制”：如果两次连续累加的结果一致，则认为是准确值；若不一致（说明期间有并发修改），最多重试 3 次，若仍不一致则直接返回当前累加值（接受一定误差）。

而在JDK 1.8中，计算 size 依赖于 baseCount 原子变量和 counterCells 辅助数组，通过无锁累加实现，返回两者的总和作为最终的 size。

当插入元素成功后，需要将总数 +1，流程如下：

优先尝试更新 baseCount：
线程通过 CAS 操作直接更新 baseCount（baseCount + 1）。
- 若 CAS 成功：计数完成，无需其他操作。
- 若 CAS 失败：说明存在并发竞争（多个线程同时更新 baseCount），进入下一步。
竞争激烈时，使用 counterCells 分散计数：
- 若 counterCells 未初始化，先通过 CAS 初始化（创建一个 CounterCell 数组）。
- 线程通过哈希算法（基于线程 ID 或随机数）随机选择 counterCells 中的一个 CounterCell。
- 尝试用 CAS 更新该 CounterCell 的 value（value + 1）：
  - 若成功：计数完成。
  - 若失败：重试或选择其他 CounterCell（避免死锁）。

特性	JDK 1.7 计数方式	JDK 1.8 计数方式
底层依赖	各 Segment 的 `count` 累加	`baseCount` + `counterCells` 累加
并发处理	重试机制减少误差，返回近似值	CAS 原子操作，返回接近精确值
性能	低并发时高效，依赖 Segment 数量	高低并发均高效，通过分散竞争优化
实现复杂度	简单（遍历 + 重试）	复杂（原子变量 + 辅助数组 + 竞争分散）
适用场景	分段锁架构下的近似计数	全局数组架构下的高效精确计数