Java-从源码理解HashMap
前言
【Java-从源码理解HashMap】关于HashMap，是Java程序员和Android程序员日常使用频率相当高的一种集合类型了，熟悉的掌握它的使用方式还是很有必要的，要是能做到知其所以然那就更好了。本文参照JDK1.8的源码进行讲解。
1.介绍
关于HashMap，它是一种通过键值对映射来存储对象的集合，继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口，它的内部实现原理所包含的知识点还是非常的多的。要想更好的理解HashMap，首先还要对其内部的几个变量的含义有一定的了解。
1.size: 集合的大小。
2.loadFactor: 负载因子，默认为0.75(对空间和时间效率的一种平衡值，最好不要自己修改)。
3.threshold: 临界值，当HashMap的大小达到临界值时，就需要重新分配大小。
4.table: 存储键值对数据的哈希桶数组(即HashMap中的数据实际是存储在此数组中的)。
5.Node: table中每一个元素的实体类，由hash值，key值，value值，以及next(Node类型)元素组成；
Node实现了Map中的Entry接口，其本身是一个单向链表。
6.TreeNode: 红黑树节点实现类，继承自LinkedHashMap.Entry类
另外，在JDK1.8以后，HashMap对底层的实现以及扩容机制等进行了优化，采用数组+链表/红黑树的方式存储数据。因为即使负载因子的值和Hash算法设计的再合理也是不会百分之百的避免哈希碰撞的发生，而这样就有可能造成某个位桶下的链表长度过长，当链表的长度超过8的时候，这个链表就将转换成红黑树，因为如果链表的长度过长，就会严重降低HashMap的数据访问速度，而转化成红黑树就是利用了红黑树快速增删改查的特点来提高HashMap的性能。具体结构如下：
文章图片
hashbody.png 有了一些基本的了解之后，我们正式学习下它的源码。
2.构造方法 1.无参构造，通常我们都用这个构造方法创建一个HashMap，该构造方法初始化默认的负载因子值为0.75。
public HashMap() {
this.loadFactor = 0.75F;
}
2.指定“容量大小”和“负载因子”的构造函数：
public HashMap(int var1, float var2) {
// 如果指定的容量值小于0，则抛出异常
if (var1 < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " + var1);
} else {
// 如果指定的容量大小超过了1073741824，那么就让容量值为1073741824
if (var1 > 1073741824) {
var1 = 1073741824;
}
/**
* 如果指定的负载因子值大于0并且是一个合法数字时，将指定的值赋值给loadFactor变量，
* 同时根据指定的容量大小来计算临界值的大小，否则抛出异常。
*/
if (var2 > 0.0F && !Float.isNaN(var2)) {
this.loadFactor = var2;
this.threshold = tableSizeFor(var1);
// 此方法为计算临界值的方法，详解见下
} else {
throw new IllegalArgumentException("Illegal load factor: " + var2);
}
}
}/**
* 此方法为计算当前HashMap中临界值的方法，方法中涉及到了按位或操作以及逻辑运算符操作，这里面运算符的使用方式还请自行科普，
* 总之该方法返回的值一定是大于或者等于var0的2的整数次方，并且是最接近传入的var0的值的2的整数次方。
* 例如：传入了12，返回的为16；传入的16，返回的16；传入的17，返回的32。
*/
static final int tableSizeFor(int var0) {
int var1 = var0 - 1;
var1 |= var1 >>> 1;
var1 |= var1 >>> 2;
var1 |= var1 >>> 4;
var1 |= var1 >>> 8;
var1 |= var1 >>> 16;
return var1 < 0 ? 1 : (var1 >= 1073741824 ? 1073741824 : var1 + 1);
}
3.指定“容量大小”的构造函数，不多说，都懂，只是内部再调用上面的构造方法
public HashMap(int var1) {
this(var1, 0.75F);
}
4.传入一个Map类型参数的构造函数：
public HashMap(Map var1) {
this.loadFactor = 0.75F;
，// 赋值负载因子的值为默认值0.75
this.putMapEntries(var1, false);
// 将传入的集合中的数据逐个添加到HashMap中
}
3.常用方法： 1.put(K var1, V var2)：向集合中添加key为var1，value为var2的键值对数据。
/**
* 方法内部调用putVal方法，其中第一个参数又调用了hash()方法
*/
public V put(K var1, V var2) {
return this.putVal(hash(var1), var1, var2, false, true);
}/**
* 此方法返回根据var0(put方法中传入的key值)得到一个哈希值，首先判断var0是否为空，
* 如果为空，则直接返回0，如果不为空，返回var0的hashCode()方法返回的值的高16位异或低16位后所得到的值。
*/
static final int hash(Object var0) {
int var1;
return var0 == null ? 0 : (var1 = var0.hashCode()) ^ var1 >>> 16;
}/**
* 此方法才是真正的添加操作，方法内部可以分为几个步骤
*/
final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) {
/**
* 1.创建临时变量var6并指向当前集合中的table，创建临时变量var8并让其等于var6的长度；
*如果table为空或者table的长度为0，那么就调用resize()方法进行初始化相关操作。
*/
HashMap.Node[] var6;
int var8;
if ((var6 = this.table) == null || (var8 = var6.length) == 0) {
var8 = (var6 = this.resize()).length;
}
/**
* 2.创建临时变量var7，并让其指向var6[(var8 - 1) & var1]，同时var9为计算出的数组索引值；
*如果var7为空，说明在此索引上没有发生哈希碰撞直接调用newNode方法创建一个Node元素并指向table的第var9个索引上。
*/
Object var7;
int var9;
if ((var7 = var6[var9 = var8 - 1 & var1]) == null) {
var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null);
} else {
/**
* 3.如果var7不为空，说明此时发生了碰撞。首先，创建两个临时变量var10和var11;
*如果var7的hash值等于var1并且var7的key与var2相等(说明已经存在这个key)，此时直接将var10指向var7(其实就是覆盖之前的值)
*/
Object var10;
Object var11;
if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) {
var10 = var7;
} else if (var7 instanceof HashMap.TreeNode) {
/**
* 如果不存在这个key，此时判断var7是不是TreeNode(红黑树)类型；
* 如果是红黑树类型，那么调用putTreeVal方法给树(var7)插入树节点
*/
var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3);
} else {
/**
* 进入到这里，说明此时var7还是链表，此时创建int类型临时变量var12并赋值为0(用于记录遍历的次数)；
*/
int var12 = 0;
while(true) {
/**
* 进入循环，遍历链表中的元素，当发现某个元素的next为null时，
* 说明该元素为链表中最后一个元素，此时将链表的next指向新的Node节点
*/
if ((var10 = ((HashMap.Node)var7).next) == null) {
((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null);
// 如果链表的长度大于或者等于8(var12是从0开始的)，将链表转化成红黑树(具体实现在treeifyBin方法中)
if (var12 >= 7) {
this.treeifyBin(var6, var1);
}
break;
}
// 遍历过程中若发现当前元素的hash值和var1相同并且key也和var2相同，会跳出当前循环，并将value更新
if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) {
break;
}
var7 = var10;
++var12;
}
}
// 对已经存在的key对应的value进行更新
if (var10 != null) {
Object var13 = ((HashMap.Node)var10).value;
if (!var4 || var13 == null) {
((HashMap.Node)var10).value = https://www.it610.com/article/var3;
}
this.afterNodeAccess((HashMap.Node)var10);
return var13;
}
}
++this.modCount;
// 如果当前集合的大小大于临界值threshold，那么就调用resize()方法重新扩容
if (++this.size> this.threshold) {
this.resize();
}
this.afterNodeInsertion(var5);
return null;
}
以上，就是HashMap在put数据的时候的实现原理，用一张图概括如下：
文章图片
hashput.png 2.get(Object var1)：根据key值从集合中获取value
/**
* 方法内部创建一个Node类型临时变量，然后调用getNode方法获取对应的Node对象；
* 如果Node对象为空直接返回null，反之返回Node的value
*/
public V get(Object var1) {
HashMap.Node var2;
return (var2 = this.getNode(hash(var1), var1)) == null ? null : var2.value;
}/**
* 根据var1(get方法中传入的key的hash值)和var2(get方法中传入的key)来返回一个Node对象
*/
final HashMap.Node getNode(int var1, Object var2) {
// 首先，创建三个临时变量var3(指向table)，var4(指向var3[var6 - 1 & var1])，var6(table的length)；
HashMap.Node[] var3;
HashMap.Node var4;
int var6;
// 当table不为空并且table的长度大于0时，判断var3[var6 - 1 & var1]是否为空(这里和put的时候插入的索引运算规则保持一致)
if ((var3 = this.table) != null && (var6 = var3.length) > 0 && (var4 = var3[var6 - 1 & var1]) != null) {
// 当var4的hash值和key与入参的hash值和key都相等时，直接返回var4
Object var7;
if (var4.hash == var1 && ((var7 = var4.key) == var2 || var2 != null && var2.equals(var7))) {
return var4;
}
// 遍历链表
HashMap.Node var5;
if ((var5 = var4.next) != null) {
// 如果为红黑树类型，就通过getTreeNode方法获取对应的TreeNode
if (var4 instanceof HashMap.TreeNode) {
return ((HashMap.TreeNode)var4).getTreeNode(var1, var2);
}
// 不是红黑树，就为链表，遍历链表，当元素的hash值和key值与传入的相等时返回对应的Node
do {
if (var5.hash == var1 && ((var7 = var5.key) == var2 || var2 != null && var2.equals(var7))) {
return var5;
}
} while((var5 = var5.next) != null);
}
}
return null;
}
其实，在把put方法读懂之后，get方法理解起来特别容易了，一个存，一个取，取的时候按照存时的规则去取就可以了。
3.clear()：清空集合数据的方法
/**
* 方法内其实就做了两件事，一个是将集合的size置为0，另一个就是遍历table，将里面的元素全部置为null
*/
public void clear() {
++this.modCount;
HashMap.Node[] var1;
if ((var1 = this.table) != null && this.size > 0) {
this.size = 0;
for(int var2 = 0;
var2 < var1.length;
++var2) {
var1[var2] = null;
}
}
}
4.containsKey(Object var1):判断集合中是否存在var1这个key
/**
* 方法内部也是调用了getNode方法，只要getNode方法返回不为空，就说明已经存在这个key值了
*/
public boolean containsKey(Object var1) {
return this.getNode(hash(var1), var1) != null;
}
还有几个常用的方法，比如remove(Object var1)，containsValue(Object var1)等，其内部的实现其实都是调用上面讲解过的几个方法，只要把上面的put方法能真正的读懂，其他的方法相信你肯定也能明白。
5.重量级方法resize()：
此函数有两种调用时机：1.初始化操作(put操作如果table为null时) 2.当前数组容量过小时，需扩容操作。
final HashMap.Node[] resize() {
HashMap.Node[] var1 = this.table;
// 创建var1并指向当前数组table
int var2 = var1 == null ? 0 : var1.length;
// 创建var2使其等于table的长度
int var3 = this.threshold;
// 创建var3使其等于扩容前的临界值
int var5 = 0;
int var4;
if (var2 > 0) { // 当前table长度大于0
if (var2 >= 1073741824) {
// 如果table的长度大于最大容量，那么将threshold置为2147483647，返回当前table，并未做扩容操作
this.threshold = 2147483647;
return var1;
}
// 如果table长度的2倍小于最大容量并且table的长度大于初始的容量16时，进行扩容操作，扩大为原来的2倍(移位运算自行科普)。
if ((var4 = var2 << 1) < 1073741824 && var2 >= 16) {
var5 = var3 << 1;
// 新的临界值变为之前的2倍
}
} else if (var3 > 0) { // 此时老的临界值已被设置，table还为null
var4 = var3;
// 让新的table数组的容量直接等于老的的临界值
} else { // 此时临界值未被设置，table也为null
var4 = 16;
// 新的table数组的容量设置成默认值16
var5 = 12;
// 新的临界值设置为12(16 * 0.75)
}
// 如果临界值为0，重新计算临界值的大小
if (var5 == 0) {
float var6 = (float)var4 * this.loadFactor;
var5 = var4 < 1073741824 && var6 < 1.07374182E9F ? (int)var6 : 2147483647;
}
this.threshold = var5;
// 将最终得到的临界值大小赋值给threshold
// 创建新的Node类型数组并让table指向刚创建的数组var14(新的table数组)
HashMap.Node[] var14 = (HashMap.Node[])(new HashMap.Node[var4]);
this.table = var14;
if (var1 != null) {
// 把之前的table中的元素一个个的移动到新的table中去(for循环中的移动逻辑这里就不阐述了)
for(int var7 = 0;
var7 < var2;
++var7) {
HashMap.Node var8;
if ((var8 = var1[var7]) != null) {
var1[var7] = null;
if (var8.next == null) {
var14[var8.hash & var4 - 1] = var8;
} else if (var8 instanceof HashMap.TreeNode) {
((HashMap.TreeNode)var8).split(this, var14, var7, var2);
} else {
HashMap.Node var9 = null;
HashMap.Node var10 = null;
HashMap.Node var11 = null;
HashMap.Node var12 = null;
HashMap.Node var13;
do {
var13 = var8.next;
if ((var8.hash & var2) == 0) {
if (var10 == null) {
var9 = var8;
} else {
var10.next = var8;
}
var10 = var8;
} else {
if (var12 == null) {
var11 = var8;
} else {
var12.next = var8;
}
var12 = var8;
}
var8 = var13;
} while(var13 != null);
if (var10 != null) {
var10.next = null;
var14[var7] = var9;
}
if (var12 != null) {
var12.next = null;
var14[var7 + var2] = var11;
}
}
}
}
}
return var14;
}
关于扩容的逻辑确实有些复杂，方法本身也很长，但其实静下心来一步一步的看，也是可以看懂的。
总结 以上，通过阅读源码对HashMap有了更深入一层的了解，其实关于HashMap还有很多需要掌握的知识点的，譬如HashMap是否是线程安全的，它的key是否可以为其他类型，它的key是否可以为null以及它的value是否可以为null等等。单纯就上面讲到的方法来说，我们还需要掌握java的异或，移位，逻辑运算符操作，以及链表和红黑树的知识点。所以，个人认为，一个小小的HashMap还是很考验一个人的水平的，因此真的有必要好好掌握以下。
写在最后 PS：没有啥太深的技术功底，只能凭自己的理解再参考一些前辈的文章，有写的不正确的地方还望指出。
推荐阅读
- Docker应用:容器间通信与Mariadb数据库主从复制
- 一个人的碎碎念
- 我从来不做坏事
- 从蓦然回首到花开在眼前，都是为了更好的明天。
- 西湖游
- 改变自己，先从自我反思开始
- leetcode|leetcode 92. 反转链表 II
- 从我的第一张健身卡谈传统健身房
- 自媒体形势分析
- 操作系统|[译]从内部了解现代浏览器(1)