HashMap源码解读（中篇）
文章目录
前言
上一篇博主写了一些关于HashMap的前置知识，简单易懂：
下面将深入HashMap源码，进行解读。
看源码不是盲目看书，要有的放矢，带着疑问去看。
本文章将围绕这几个疑问展开：
- HashMap的哈希函数是如何设计的？
- put方法的逻辑是什么？到底是如何存储元素的？
- 当发生冲突时，是如何解决的？
- 哈希表冲突比较严重时，如何扩容resize？
一、进入JDK中的源码（InteliJ IDEA为例）
有两种快捷方式：
- 双击shift，输入HashMap类名即可。
- 直接在使用的类上，ctrl+鼠标左键点进去即可
二、HashMap的结构
JDK8之后HashMap的结构图如下：（可先看下面再回来看这个结构图）
JDK8之前的HashMap就是数组+链表，JDK8之后采用数组+链表+红黑树
冲突严重的链表会被“树化”，将链表转为红黑树，提高冲突严重的链表的查询效率。
三、源码解读
3.1 属性解读
如图所示：
图中有六条属性，下面逐一解释：
1. static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
默认初始化的数组大小 (默认的哈希桶数量) ： 16
注：哈希桶就是哈希表中一个个的数组元素，不包括链表元素
2.static final int MAXIMUM_CAPACITY = 1 << 30;
最大的数组容量：
3.static final float DEFAULT_LOAD_FACTOR = 0.75f;
默认负载因子，默认时开始保存的元素个数最多为 16 * loadFactor = 12 个
4.static final int TREEIFY_THRESHOLD = 8;
树化阈值。某个哈希桶中的链表长度超过8才会触发“树化”操作
5.static final int UNTREEIFY_THRESHOLD = 6;
“解树化” 当某个哈希桶中的红黑树结点个数过小，< = 6时，就会将红黑树还原为链表。
6.static final int MIN_TREEIFY_CAPACITY = 64;
树化有两个条件：
- 此时哈希表的哈希桶个数 >= 64
- 单个链表的结点个数 >= 8
若某个链表长度 >= 8 ,但此时哈希桶的数量不足64，则只是简单的哈希表扩容而已。
3.2 put方法解读
如图所示：
内部存储调用的是putVal方法，方法里面参数主要是hash值和key，value值。
3.2.1 HashMap中的hash方法
源码如下：
1.首先判断传入的Key值是否为null？ 如果为null，直接放入数组索引为0的哈希桶中。
2.如果传入的Key值不为null，则将key的hashCode 无符号右移16位，保留高16位 然后和 原hashCode作 异或运算，求得数组索引。
注意：Key对象所在类的hashCode方法若没有覆写，则默认调用Object提供的hashCode方法。
- 高低16位都参与哈希函数的运算，尽可能保证不同key映射到比较均衡的状态。
- 原32位的hashCode和只保留高16的数字做异或运算
- 高低位树都参与hash运算得到的值更加平均
- 哈希函数设计理念：经过hash运算得到的值尽可能地平均
此时求出地hash值还不是当前数组的索引，只是经过hash运算得到的一个比较均衡的值,hash值还要经过如下红框的位运算，得到数组索引值：
上一步得到的key的hash值和当前哈希表的长度-1 进行 & 运算就可以得到索引值。（位运算的效率是最高的）
- 相当于hash % 数组长度取模(n)
- 前提是n必须为 2^n （初始化的哈希桶数量必须为2 ^ n）。
- 将任意的正整数转为哈希桶数量之内的小整数 => i 就是当前key求的哈希桶的编号
3.2.2 HashMap中的putVal方法
JDK中源码如下
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}代码解读：
1.首先判断当前哈希表是否为空，若为空，进行默认初始化操作（resize()函数里面包括了扩容、数据搬移和初始化操作）
2.tab[i] = 这个哈希桶的头结点元素，当这个键值对计算出的哈希桶链表为空，直接将当前新元素放入链表的头部。
- 此时哈希表不为空且对应链表头部已经有元素了
4.链表不为空但是链表的头部元素key和新键值对的key相同（equals相同），hash值也相同，认为是同一个元素，替换头结点。
5.此时这个哈希桶对应的链表已经树化，调用RB的逻辑进行红黑树上的结点插入处理。
6. 链表的插入逻辑，新节点尾插入链表尾部，如果此时链表长度大于树化阈值，则执行treeifyBin()树化处理，注意此时哈希桶对应的还是链表，若哈希桶数量小于64，只是扩容，并不树化。
treeifyBin函数：若哈希桶数量小于64，只是扩容，并不树化。
7.新插入的元素的Key已经存在了，只是更新Value值即可。
8.判断添加元素之后整个的哈希表大小是否超过threshold，若超过则执行resize()扩容
未完待续
本文解读了HashMap中的属性 以及 Put方法 ，对hashCode和equals 方法进行了一个扩展，以及对HashMap的Key唯一性进行了解释，后篇文章博主将会更新resize方法的解读以及 HashMap的构造方法懒加载等，感谢各位继续关注博主更新~~😀