那些年，我们又爱又恨的HashMap（二）-源码篇
站长
· 阅读数 29
一、HashMap重要方法源码分析
1.put()方法，即添加元素方法
put()方法较为复杂的，也是面试中最常问的方法，实现步骤大致如下：
-
计算出需要添加的元素的key的哈希值；
-
使用该哈希值结合数组长度采用位运算
hash&length-1计算出索引值； -
如果该位置无数据，则直接插入；
-
如果有数据，比较哈希值是否相等：
不相等：在此索引位置划出一个节点存储数据，此为拉链法；
相等：发生哈希冲突，使用链表或红黑树解决，调用equals()比较内容是否相同；
相同：新值覆盖旧值；
不相同：划出一个节点直接存储；
-
如果
size大于threshold，进行扩容。
2.put()方法源码：
public V put(K key, V value) {
//调用putVal()方法，putVal()调用hash(key)
return putVal(hash(key), key, value, false, true);
}
3.hash()方法源码：
static final int hash(Object key) {
int h;
/**
* 如果key为null，返回0；
* 如果key不为null，计算出key的哈希值并赋给h，然后与h无符号右移16位后进行按位异或得到最终哈希值
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
-----------------------------------------------------------------------------------------
(h = key.hashCode()) ^ (h >>> 16)的计算过程如下所示：
假设h = key.hashCode()计算出的h为 11111111 11111111 11110000 11101010；
无符号右移，无论是正数还是负数，高位都补0；
^（按位异或运算）：相同二进制数位上相同为0，不同为1。
11111111 11111111 11110000 11101010 //h
^ 00000000 00000000 11111111 11111111 //h >>> 16：
--------------------------------------------------------
11111111 11111111 00001111 00010101 //返回的哈希值
在putVal()方法中使用到了上述hash函数计算的哈希值。
4.putVal()方法源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//此处省略一千行，如果需要，请自行查看jdk源码
if ((p = tab[i = (n - 1) & hash]) == null) //这里使用到了上面计算得到的哈希值
//此处省略一千行，如果需要，请自行查看jdk源码
}
-----------------------------------------------------------------------------------------
利用hash()方法返回的哈希值计算索引，(n - 1) & hash])；
n为数组长度，默认为16；
&（按位与运算）：相同的二进制数位都是1，结果为1，否则为0。
00000000 00000000 00000000 00001111 //n - 1 = 15
& 11111111 11111111 00001111 00010101 //hash
--------------------------------------------------------
00000000 00000000 00000000 00000101 //索引为5
5.为什么要这样运算呢？又是无符号右移16位，又是异或，最后还要按位与，这样不是很麻烦吗？
这样做是为了避免发生哈希冲突。
如果数组长度n很小，假设是16的话，那么n-1=15即1111 ，这样的值和哈希值直接按位与运算，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。
举例说明这个问题：
key.hashCode()计算出的哈希值与n - 1直接按位与运算：
11111111 11111111 11110000 11101010 //h
& 00000000 00000000 00000000 00001111 //n - 1 = 15
--------------------------------------------------------
00000000 00000000 00000000 00001010 //索引为10
再存储一个key.hashCode()计算出的哈希值，并且高16位变化很大
11000111 10110011 11110000 11101010 //新存储的哈希值h，并且高16位变化很大
& 00000000 00000000 00000000 00001111 //n - 1 = 15
--------------------------------------------------------
00000000 00000000 00000000 00001010 //索引仍为10
结论：直接按位与，并且哈希值的高位变化大，低位变化小甚至不变时，容易出现索引值一样的情况，进而造成哈希冲突
二、HashMap中的两个重要方法源码分析
1.最难的putVal()源码分析：
transient Node<K,V>[] table; //表示HashMap中的数组主体
/**
* Implements Map.put and related methods
*
* @param hash hash for key（key的哈希值）
* @param key the key（key）
* @param value the value to put（添加元素的值）
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
/*
1.transient Node<K,V>[] table;表示HashMap中的数组主体；
2.(tab = table) == null：将空的table赋值给tab，第一次是null，结果为true；
3.(n = tab.length) == 0：表示将数组的长度0赋值给n,然后判断n是否等于0，结果为true；
4.由于if使用双或判断，一边为true就为true，所以执行代码 n = (tab = resize()).length;
5.n = (tab = resize()).length：调用resize方法对数组进行扩容，并将扩容后的数组长度赋值给n；
6.执行完 n = (tab = resize()).length 后，数组tab的每个桶（每个索引位置）都是null。
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/*
1.i = (n - 1) & hash：计算出索引并赋值给i，即确定元素存放在哪个桶中；
2.p = tab[i = (n - 1) & hash]：将该索引位置上的数据赋值给节点p；
3.(p = tab[i = (n - 1) & hash]) == null：判断索引位置上的内容是否为null；
4.如果为null，则执行代码 tab[i] = newNode(hash, key, value, null);
*/
if ((p = tab[i = (n - 1) & hash]) == null)
//根据键值对创建新的节点，并将该节点存入桶中。
tab[i] = newNode(hash, key, value, null);
else {
//执行else，说明tab[i]不等于null，表示这个位置已经有值了。
Node<K,V> e; K k;
/*
1.p.hash == hash：p.hash表示已存在key的哈希值，hash表示新添加数据key的哈希值；
2.(k = p.key) == key：将已存在数据的key的地址赋值给k，然后与新添加数据的key的地址进行比较
3.(key != null && key.equals(k))))：执行到这里说明两个key的地址值不相等，那么先判断后 添加的key是否等于null，如果不等于null再调用equals方法判断两个key的内容是否相等
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//如果两个key的哈希值相等，并且value值也相等，则将旧的元素整体对象赋值给e，用e来记录
e = p;
//哈希值不相等或者key的地址不相等，则判断p是否为红黑树结点
else if (p instanceof TreeNode)
//是红黑树几点，则放入树中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//否则说明是链表节点
else {
//是链表的话需要遍历到结尾然后插入（尾插法）；采用循环遍历的方式，判断链表中是否有重复的key
for (int binCount = 0; ; ++binCount) {
/*
1.e = p.next：获取p的下一个元素赋值给e
2.(e = p.next) == null：判断p.next是否等于null，等于null，说明p没有下一个元素;那么此时到达了链表的尾部，还没有找到重复的key,则说明HashMap没有包含该键,则将该键值 对插入链表中。
*/
if ((e = p.next) == null) {
/*
1.p.next = newNode(hash, key, value, null)：创建一个新节点并插入到尾部；
2.这种添加方式也满足链表数据结构的特点，每次向末尾添加新的元素。
*/
p.next = newNode(hash, key, value, null);
/*
1.节点添加完成之后判断此时节点个数是否大于TREEIFY_THRESHOLD临界值8，如果大于则将链表转换为红黑树；
2.binCount表示for循环的初始值，从0开始计数，记录着遍历节点的个数；值是0表示第1个节点，1表示第2个节点，以此类推，7就表示第8个节点，8个节点则存储着9个元素；
3.TREEIFY_THRESHOLD-1 =8-1=7；此时如果binCount的值也是7，则转换红黑树。
*/
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树
treeifyBin(tab, hash);
//转化为红黑树就跳出循环
break;
}
/*
执行到这里说明e = p.next不是null，不是最后一个元素，继续判断链表中结点的key值与插入的数据的key值是否相等
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//相等，跳出for循环，不用再继续比较，直接执行下面的if (e != null)语句
break;
p = e;
}
}
/*
为true表示在桶中找到key的哈希值和key的地址值与插入数据相等的结点；也就是说找到了重复的键，所以这里就是把该键的值变为新的值，并返回旧值，使用的是put方法的修改功能。
*/
if (e != null) { // existing mapping for key（存在重复的键）
//记录e的value
V oldValue = e.value;
//如果onlyIfAbsent为false或者旧值为null
if (!onlyIfAbsent || oldValue == null)
//用新值替换旧值
e.value = value;
//访问后回调
afterNodeAccess(e);
//返回旧值
return oldValue;
}
}
//记录修改次数
++modCount;
//判断实际大小是否大于threshold阈值，如果大于则扩容
if (++size > threshold)
//扩容
resize();
// 插入后回调
afterNodeInsertion(evict);
return null;
}
2.将链表转换为红黑树的treeifyBin()方法源码分析：
链表什么时候转化为红黑树？在putVal()方法中给出了答案：
//当链表长度大于阈值8时转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//转换为红黑树，tab表示数组名，hash表示哈希值
treeifyBin(tab, hash);
treeifyBin()方法源码分析：
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
/*
1.如果当前数组为空或者数组的长度小于64(MIN_TREEIFY_CAPACITY = 64)，则进行去扩容，而不是将链表变为红黑树；
2.原因：如果数组很小就转换红黑树，遍历效率要低一些（红黑树结构复杂）；这时进行扩容，重新计算哈希值，将数据重新分配到数组主体中，链表长度有可能就变短了，这样做相对来说效率高一些。
*/
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//扩容方法
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
/*
1.执行到这里说明哈希表中的数组长度大于64，开始由链表转化为红黑树；
2.e = tab[index = (n - 1) & hash]表示将数组中的元素取出赋值给e，e是哈希表中指定位置桶里的链表节点，从第一个开始；
3.这里hd表示红黑树的头结点，tl表示红黑树的尾结点，默认都为null。
*/
TreeNode<K,V> hd = null, tl = null;
do {
//新创建一个树节点，内容和当前链表节点e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
//将新创键的树节点p赋值给红黑树的头结点
hd = p;
else {
/*
1.p.prev = tl：将上一个节点p赋值给现在的p的前一个节点；
2.tl.next = p：将现在节点p作为树的尾结点的下一个节点。
*/
p.prev = tl;
tl.next = p;
}
tl = p;
/*
e = e.next：将当前节点的下一个节点赋值给e,如果下一个节点不等于null，则回到上面继续取出链表中节点转换为红黑树
*/
} while ((e = e.next) != null);
/*
让桶中的第一个元素即数组中的元素指向新建的红黑树的节点，以后这个桶里的元素就是红黑树而不是链表了，至此，链表转化红黑树完成
*/
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
上述操作一共做了如下三件事：
1.根据哈希表中元素个数确定是扩容还是树形化；
2.如果是树形化遍历桶中的元素，创建相同个数的树形节点，复制内容，建立起联系；
3.然后让桶中的第一个元素指向新创建的树根节点，替换桶的链表内容为树形化内容。
三、HashMap的resize()扩容方法
1.首先，什么时候开始扩容？
当HashMap中的元素个数超过n（数组长度）*loadFactor（负载因子）时，就会进行数组扩容。n的默认值为16，loadFactor的默认值是0.75，那么当HashMap中的元素个数超过16×0.75=12（边界值threshold）时，就把数组的大小扩大为原来的2倍，即32，然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经知道HashMap中元素的个数，那么使用HashMap的有参构造指定初始化大小是一个不错的选择。
说明：
当HashMap中的一个链表长度大于8时，但数组长度没有达到64，那么HashMap会先扩容解决，如果已经达到了64，那么这个链表会变为红黑树，节点类型由Node变成TreeNode类型。当然，如果移除元素使红黑树的节点个数小于6时，也会再把红黑树转换为链表。
2.扩容的实质是什么？
说白了，扩容就是一个rehash的过程，即重新计算HashMap中元素的位置并分配到扩容后的HashMap中。
在JDK1.8之后，HashMap对resize()方法进行了优化，使用到了非常巧妙的rehash方式进行索引位置的计算。
下面分析一下这个rehash方式怎么巧妙？
我们知道，HashMap在扩容的时候，总是扩大为原来的两倍，这样的话，与原始HashMap相比，扩容后计算的索引只是比原来的索引多了一个bit位（二进制位）；
所以：扩容后的索引要么为原来的索引，要么变为原索引+旧容量。
如果没有看明白这句话，请看下面的例子：
例如我们将HashMap由原来的16扩展为32，变化前后索引的计算过程如下所示：
索引计算公式：index=（n-1） & hash；按位与运算：相同二进制位都为1，结果为1，否则为0
hash1（key1）： 11111111 11111111 00001111 00000101；
hash2（key2）： 11111111 11111111 00001111 00010101；
原HashMap容量n=16， 二进制表示为： 00000000 00000000 00000000 00010000；
扩容后HashMap容量n=32，二进制表示为： 00000000 00000000 00000000 00100000；
-----------------------------------------------------------------------------------------
原HashMap的key1索引：
00000000 00000000 00000000 00001111 //n-1=16-1=15
& 11111111 11111111 00001111 00000101 //hash1（key1）
------------------------------------------------------
00000000 00000000 00000000 00000101 //索引为5
原HashMap的key2索引：
00000000 00000000 00000000 00001111 //n-1=16-1=15
& 11111111 11111111 00001111 00010101 //hash2（key2）
------------------------------------------------------
00000000 00000000 00000000 00000101 //索引为5
结果：key1和可以key2的索引都为5；
-----------------------------------------------------------------------------------------
扩容后的HashMap的key1索引：
00000000 00000000 00000000 00011111 //n-1=32-1=31
& 11111111 11111111 00001111 00000101 //hash1（key1）
------------------------------------------------------
00000000 00000000 00000000 00000101 //索引为5
原HashMap的key2索引：
00000000 00000000 00000000 00011111 //n-1=32-1=31
& 11111111 11111111 00001111 00010101 //hash2（key2）
------------------------------------------------------
00000000 00000000 00000000 00010101 //索引为5+16
结果：key1的索引为5；key2的索引为 16+5，即为原索引+旧容量
由上面的推理过程可以得出这样的结论：
元素在重新计算哈希值后，因为n变为2倍，那么n-1的标记范围在高位多1bit（红色），因此新的index就会发生这样的变化：
即红色所示的高位为0，还是原来的索引位置；为1，索引变为原索引+旧容量。
因此，在扩容HashMap时，不需要重新计算哈希值，只需要看原来的哈希值新增的那个bit是1还是0就可以了，是0的话索引不变，是1的话索引变成“原索引+oldCap(原位置+旧容量)”，具体可以看下面16扩容32的示意图：
正是因为这样巧妙的rehash方式，省去了重新计算哈希值的时间，而且由于新增的1bit是0还是1可以认为是随机的，在resize的过程中保证了rehash之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了rehash之后不会出现更严重的哈希冲突，均匀地把之前冲突的节点分散到新的桶中了。
3.扩容方法resize()源码分析：
看完了上面的扩容原理，再来看源码会容易些。
不要看这个方法长，觉得难就看不下去了，静下心，好好分析完，对自己的技术肯定有提升，我们开始吧！
final Node<K,V>[] resize() {
//得到当前数组
Node<K,V>[] oldTab = table;
//如果当前数组为null返回0，否则返回当前数组长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//当前边界值，默认是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
//如果旧数组长度大于0，则开始计算扩容后的大小
if (oldCap > 0) {
//如果旧数组长度大于最大值，就不再扩容，就只好随你碰撞去吧！
if (oldCap >= MAXIMUM_CAPACITY) {
//修改边界值为Integer数据类型的最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
/*
没超过最大值，就扩充为原来的2倍;
1.(newCap = oldCap << 1) < MAXIMUM_CAPACITY：扩大到2倍之后容量是否小于最大容量
2.oldCap >= DEFAULT_INITIAL_CAPACITY：旧数组长度是否大于等于数组初始化长度16
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//旧边界值左移一位，相当于扩大一倍
newThr = oldThr << 1; // double threshold
}
//旧边界值大于0则直接赋值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//计算新的resize最大上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//新的边界值原来默认是12，扩大一倍变为24
threshold = newThr;
//创建新的哈希表
@SuppressWarnings({"rawtypes","unchecked"})
//newCap是扩容后的数组长度32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//判断旧数组是否等于空
if (oldTab != null) {
//遍历旧的哈希表中的桶，重新计算桶里元素的新位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//将旧数组中的数据都置为null，便于GC回收
oldTab[j] = null;
//判断数组是否有下一个引用
if (e.next == null)
//没有下一个引用，说明不是链表，当前桶上只有一个键值对，直接插入
newTab[e.hash & (newCap - 1)] = e;
//判断是否是红黑树
else if (e instanceof TreeNode)
//说明是红黑树，则调用相关方法把树分开
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
//不是红黑树，则采用链表处理冲突
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//通过上述讲解的原理来计算节点的新位置
do {
//原索引
next = e.next;
//如果为true，则e这个节点在扩容后还是原索引位置，说明高位为0
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//原索引+旧容量，说明高位为1
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//将扩容后的原索引放到桶里
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将扩容后的 原索引+旧容量 放到桶里
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
四、总结
HashMap的底层源码算是JDK源码中设计最复杂同样也最优秀的源码了，如果能研究、理解了HashMap的源码，相信JDK的其他源码对你来说也不是什么问题了。
都看到这里了，给个赞再走吧！哈哈哈！！！
转载自:https://juejin.cn/post/6844904111075229709