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

Java基础系列-HashMap源码解析4-基本概念

news 2025/5/31 21:03:02

文章目录

HashMap 源码解析
- 简介
- - 概念拓展1
  - 概念拓展2
- JDK1.8 之前
- JDK1.8 之后
- 类的属性
- - loadFactor 负载因子
  - threshold

HashMap 源码解析

简介

HashMap 主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。

HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个

JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。 JDK1.8 以后的 HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于等于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap 默认的桶数组初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。并且， HashMap 总是使用 2 的幂作为哈希表的大小。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 即 16

概念拓展1

初始化逻辑：

当使用 new HashMap() 无参构造函数时，数组并不会立即创建。

首次添加元素（调用 put() 方法）时，会触发 延迟初始化，此时数组才会分配为 16 的大小。

扩容规则：

初始扩容阈值为 DEFAULT_INITIAL_CAPACITY * LOAD_FACTOR，即 16 * 0.75 = 12。当元素数量超过阈值时，数组会扩容为 2 * 原容量（即 32，后续依此类推）。

这一设计旨在平衡 时间效率（减少哈希碰撞）和 空间开销。

为什么要选择 2 的幂次方？

通过 (capacity - 1) & hash 计算桶索引，避免取模运算（位运算效率更高）。

2 的幂次方能确保 (capacity - 1) 的二进制全为 1（如 15 -> 1111），使得哈希分布更均匀。

概念拓展2

阈值（Threshold） 是 HashMap 内部机制中决定何时扩容数组的临界值，其计算公式为：
阈值 = 数组当前容量 × 负载因子（Load Factor）
默认情况下，负载因子为 0.75，初始容量为 16，因此初始阈值为 12（即 16 × 0.75）。
阈值控制 HashMap 在空间开销与性能效率之间的平衡，具体表现为：

触发扩容的时机

当 HashMap 中元素总数（包括所有桶中的节点）超过阈值时，数组会触发扩容（容量翻倍到 2×原容量）。例如：

初始容量为 16，阈值为 12。

插入第 13 个元素时触发扩容，数组容量变为 32，新阈值为 24（32 × 0.75）。

优化哈希碰撞概率

扩容时，原数组中的元素会重新分配到新数组的桶中（哈希值的计算基于数组容量，因此位置可能变化）。

容量翻倍后，哈希冲突概率降低，链表树化风险（Java 8 中链表长度 ≥8 时会树化为红黑树）减少，从而维护操作（查找、插入、删除）的高效性。

避免高负载导致性能下降

若阈值设置过高（如负载因子接近 1）→ 哈希碰撞概率显著增加，链表长度变长，查询效率退化成 O(n)。

若阈值设置过低（如负载因子接近 0）→ 频繁扩容浪费空间，且扩容时的数据迁移耗费时间。

实际示例
假设初始容量为 8，负载因子 0.75，阈值为 6。 负载因子（默认 0.75）决定了哈希表的“稀疏程度”：

负载因子越大 → 阈值越接近容量，空间利用率高，但哈希冲突风险增加。适合对内存敏感但对性能要求不高的场景。

负载因子越小 → 提前触发扩容，哈希冲突概率低，查询效率高，但内存占用多。适合对延迟敏感的系统（如高频交易的缓存）。

JDK1.8 之前

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。

HashMap 通过 key 的 hashCode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

所谓扰动函数指的就是 HashMap 的 hash 方法。使用 hash 方法也就是扰动函数是为了防止一些实现比较差的 hashCode() 方法换句话说使用扰动函数之后可以减少碰撞。

JDK 1.8 HashMap 的 hash 方法源码:

JDK 1.8 的 hash 方法相比于 JDK 1.7 hash 方法更加简化，但是原理不变

static final int hash(Object key) {int h;// key.hashCode()：返回散列值也就是hashcode// ^：按位异或// >>>:无符号右移，忽略符号位，空位都以0补齐return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对比一下 JDK1.7 的 HashMap 的 hash 方法源码.

static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}

相比于 JDK1.8 的 hash 方法，JDK 1.7 的 hash 方法的性能会稍差一点点，因为毕竟扰动了 4 次。

所谓 “拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

在这里插入图片描述

JDK1.8 之后

相比于之前的版本，JDK1.8 以后在解决哈希冲突时有了较大的变化。

当链表长度大于阈值（默认为 8）时，会首先调用 treeifyBin()方法。这个方法会根据 HashMap 数组来决定是否转换为红黑树。只有当数组长度大于或者等于 64 的情况下，才会执行转换红黑树操作，以减少搜索时间。否则，就是只是执行 resize() 方法对数组扩容。相关源码这里就不贴了，重点关注 treeifyBin()方法即可！
在这里插入图片描述

类的属性

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {// 序列号private static final long serialVersionUID = 362498820763181265L;// 默认的初始容量是16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;// 最大容量static final int MAXIMUM_CAPACITY = 1 << 30;// 默认的负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;// 当桶(bucket)上的结点数大于等于这个值时会转成红黑树static final int TREEIFY_THRESHOLD = 8;// 当桶(bucket)上的结点数小于等于这个值时树转链表static final int UNTREEIFY_THRESHOLD = 6;// 桶中结构转化为红黑树对应的table的最小容量static final int MIN_TREEIFY_CAPACITY = 64;// 存储元素的数组，长度总是2的幂次倍transient Node<k,v>[] table;// 一个包含了映射中所有键值对的集合视图transient Set<map.entry<k,v>> entrySet;// 存放元素的个数，注意这个不等于数组的长度。transient int size;// 每次扩容和更改map结构的计数器transient int modCount;// 阈值(容量*负载因子) 当实际大小超过阈值时，会进行扩容int threshold;// 负载因子final float loadFactor;
}