在项目开发中，HashMap是及其常用的数据结构。今天，我们一起来看看它的源码实现（本文源码来自JDK 1.8）。

HashMap有如下类注释：从中可知：

• 基于哈希表的Map接口实现
• 允许空值和空键
• HashMap类大致相当于Hashtable，不同之处在于它是不同步的，是线程不安全的
• HashMap不保证映射的顺序
• 为基本操作(get和put)提供O(1)的性能
• 集合视图进行迭代所需的时间，与HashMap实例的容量加size成正比
• HashMap实例有两个影响其性能的参数:初始容量和负载因子
• 当哈希表中的条目数超过负载因子和当前容量的乘积时，将对哈希表进行重建，使哈希表的桶数大约增加一倍。

1 数据结构

HashMap是Map接口基于哈希表的一种实现。哈希表基于数组实现，元素是Entry对象。HashMap中将Entry形成链表（或者红黑树），来解决哈希冲突。HashMap主要属性如下：java

 代码解读
复制代码
// 默认初始容量16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量，2^31
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表树化时的阈值，当向entry数量为8的桶put元素时，将引起链表树化
static final int TREEIFY_THRESHOLD = 8;
// 桶取消树化时的阈值
static final int UNTREEIFY_THRESHOLD = 6;

// 哈希表
transient Node<K,V>[] table;
// 哈希表尺寸
transient int size;
// 触发下次扩容时map中的entry数，取值为capacity * load factor，
int threshold;
// 负载因子
final float loadFactor;

// 对HashMap实例的修改次数
transient int modCount;
// Entry视图
transient Set<Map.Entry<K,V>> entrySet;

1.1 负载因子

当哈希冲突严重时，键值对在哈希表中的分布将很不均匀，有些桶中没有元素，而有些桶中有很多元素；此时，查询性能将受到影响。

因此，不能等到HashMap中键值对数量，达到或超过哈希表长度时，才进行扩容。

使用loadFactor（小于1）衡量哈希表的饱和程度。要求size > capacity * load factor时，就进行扩容。通过rehash来减少哈希冲突，以保证HashMap的性能。

1.2 分离链表法

嵌套类Node<K,V>，即键值对，是单链表结构。树化时使用嵌套类TreeNode<K,V>。

树化只为提高哈希冲突严重时，在桶中查找某个key的效率。红黑树本质是自平衡的二叉查找树。

使用分离链表法的哈希表：

2 主要方法实现

2.1 初始化

创建HashMap时，可指定初始容量和loadFactor。如果不指定，则使用默认值。

也可用一个Map实例来创建新Map。

2.1.1 哈希表的尺寸

当指定initialCapacity时，会通过计算得到tableSize。HashMap中哈希表长度，要求始终是2的次方数。便于使用&与运算计算余数。

tableSize-1的二进制表示，除最高位外其余全是1；与key的hashCode做与运算，即可得到对哈希表长度的余数。如，tableSizeFor(12)=16，tableSizeFor(32)=32。

2.1.2 延迟创建哈希表

在HashMap的构造方法中，并没有立即初始化哈希表，而是在发生第一次put时，才创建哈希表。

2.2 put实现

先看hashCode计算，HashMap中做了优化。核心逻辑在putVal()中，逻辑如下：

1. 如果table为null或length为0，则初始化哈希表；
2. 根据哈希值，使用与运算计算桶下标i；
3. 如果桶为空，则指直接放入；
4. 如果桶不为空，则在红黑树或链表中put；
5. 如果桶中已存在key，则覆盖旧值，返回；
6. 最后，真的新增了一个entry后，判断是否需要扩容。

注意：

• 在判断key是否已存在时，要求hash值相同，且要求equals()返回true；
• 当桶中entry是链表时，使用尾插法；
• HashMap中先执行put，后处理扩容；由于使用size > threshold判断，不会导致无效扩容。如容量为16，负载因子为0.75，threshold=12；当插入第13个key时，才会触发扩容；
• afterNodeInsertion()定义了插入entry后的额外动作，是一个扩展点。
• 参数onlyIfAbsent为true时，put操作将只插入新key，不覆盖已存在的key（除非旧value为null）。

2.3 resize实现

主要逻辑如下：

• 当对HashMap第一次put时，将通过resize()来触发哈希表的初始化。
• 先将threshold设置为触发下次扩容时的键值对总数。如当前哈希表长度为16，threshold=12；扩容后哈希表长度为32，threshold=24；
• 遍历每一个桶，将其中的键值对重新rehash。

需要注意，resize时对链表也采用尾插法。

为什么resize能减少哈希冲突程度呢？

比如，在长度为16的哈希表中，在index=2的桶中，有key=2、18、34、82、98共5个key；

在resize后哈希表长度变为32，2、34、98将仍在index=2的桶中，而18、82会被移动到index=2+16的桶中。

从而降低了哈希桶中哈希冲突

2.4 get实现

get方法调用了getNode()，在key不存在时返回null。

而getOrDefault()在key不存在时，可以返回给定值。

2.5 size相关方法

实现很简单。

2.6 contains相关方法

containsKey时间复杂度是o(1)。而containsValue是O(n)，与size成正比。

2.7 树化和反树化

2.7.1 树化

只有向HashMap真的插入一个键值对时，才可能触发桶的树化。

当某个哈希桶中键值对数量大于等于7时，将尝试对链表树化：binCount即桶中entry的计数但是，当哈希表长度小于64时，不会树化，而是扩容。

2.7.2 反树化

反树化实现是java.util.HashMap.TreeNode#untreeify。当哈希桶中键值对数量减少时，都可能触发反树化。如remove、resize等操作。

桶由树退化为链表的条件，是桶中entry数小于等于6时。

3 总结

3.1 与JDK7比较

JDK7中，HashMap的桶不会树化，始终是链表结构。在JDK8中，HashMap引入了红黑树

扩容差异：

• 在JDK7中，当HashMap的容量达到阈值时，才会触发扩容。
• 在JDK8中，除了容量达到阈值外，当哈希表长度小于64时，某个桶中的链表长度大于等于7时，也会触发扩容。（树化只是提高了桶中查询效率，而扩容直接削弱了哈希冲突程度，效果更好）

链表的插入方式：

• 在JDK7中，put、resize操作时，对链表使用头插法，在并发扩容时，可能形成环形数据结构，导致死循环；
• 在JDK8中采用头插法，来避免出现死循环。

3.2 注意事项

• 在设置HashMap的初始容量时，应考虑map中的键值对预期数及其负载因子，以尽量减少rehash操作的数量。
• 作为一般规则，默认负载因子(0.75)在时间和空间成本之间提供了一个很好的权衡，最好不要自己指定。

转载来源：https://juejin.cn/post/7420088865464696859