本文内容均转载自网络,版权所有归原作者。
参考文章:
- 从基础到实践,一文带你看懂HashMap: 未转载进本文,但可跳转阅读参考
- HashMap源码分析
- HashMap加载因子及转红黑树探究
HashMap源码分析/HashMap数据结构及2的整数次幂探究/HashMap探究(一)
HashMap 的数据结构
- JDK1.7:数组+链表
- JDK1.8:hash表=数组+链表+红黑树
什么是哈希表?
哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
HashMap添加元素分析
在HashMap中,当添加元素时,会通过哈希值和数组的长度来计算得出一个计算下标
,用它来准确的定位该元素应该put的位置。通常,我们为了使元素分布均匀会使用取模运算,用一个值去模上总长度,例如:
index = hashCode % arr.length //实际并非这样,后面讲解
计算出index后,就会将该元素添加进去,理想状态下是将每个值都均匀的添加到数组中,但问题是不可能达到这样的理想状态,这时候就会产生哈希冲突。例如:大狂神
通过计算添加到了数组3号位置;
但是,此时佩雨
这个元素通过计算产生了一个与大狂神相同的索引位置,这是就产生了哈希冲突;于是此时,就产生了第二种数据结构——链表,冲突的元素会在该索引处以链表的形式保存;
了解:解决Hash冲突四个方法
1、开放定址法(以冲突的下标为基础再次记算hash,直到不冲突)
这种方法也称再散列法,其基本思想是:当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,再以p为基础,产生另一个哈希地址p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。
2、重Hash法(多个hash函数,一个hash函数计算出来的索引冲突了就换一个函数记算,直到不冲突)
这种方法是同时构造多个不同的哈希函数,当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。
3、链地址法
这种方法的基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第 i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
4、建立公共溢出区
将哈希表分为公共表和溢出表,当溢出发生时,将所有溢出数据统一放到溢出区。
红黑树
之前的情况,当链表的长度过长时,其固有弊端就显现出来了,即查询效率较低,链表查询的时间复杂度是O(n),数组的查询时间复杂度是O(1),链表查询效率非常低,所以就引出了第三种数据结构——红黑树,链表长度>=8时链表转为红黑树,红黑树是一棵接近于平衡的二叉树,其查询时间复杂度为O(logn),远远比链表的查询效率高。
思考:那为什么要在链表长度大于等于8的时候变成红黑树呢?
如果链表的长度没有达到这个长度的话,因为红黑树它自身的这种维护,插入的这种维护的开销也是非常大的,因为每次一去插入一个元素的时候很有可能会破坏掉他的平衡。也就是说hashmap的 put 操作非常多的时候,极有可能会影响插入的性能,因为插入一个元素的话,极有可能会打破它原有的平衡,那么每时每刻它都需要再恢复平衡(也就是红黑树的再平衡,需要左旋右旋,以及重新着色),就非常影响性能;
为什么数组的长度必须是2的指数次幂
hashmap中数组的初始长度(如果不传参,默认为16)
/** * The default initial capacity - MUST be a power of two. * 秦疆翻译:默认初始容量-必须是2的幂 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
**最大容量:**如果具有参数的任一构造函数隐式指定,则使用最大容量。必须是2的幂且 <= 1 << 30
。
/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */
static final int MAXIMUM_CAPACITY = 1 << 30;
如果我们传入的初始容量不是2的指数次幂,他就会将这个数改成大于该数且最接近这个数的2的指数次幂
比如以下这段代码:
HashMap<Object, Object> map = new HashMap<>(13);
map.put("秦疆","Java");
传入的初始容量是13,他就会将13转换为大于13且最接近13的2的指数次幂的一个数:
13----->16
再比如:
7 ----->8
5 ----->8
3 ----->4
源码分析
当我们使用构造方法传进来一个初始容量的值initialCapacity
,默认会传入一个加载因子0.75;
/** * Constructs an empty <tt>HashMap</tt> with the specified initial * capacity and the default load factor (0.75). */
public HashMap(int initialCapacity) {
//默认的加载因子仍是0.75,其通过this关键字调用了本类的另外一个重载方法
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
继续追踪分析代码:
public HashMap(int initialCapacity, float loadFactor) {
//1.这里会先判断传来的初始容量是不是小于零的数字。如果是直接抛出异常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//2.再判断是不是超过了hash定义的最大容量2的30次幂,如果超过了则让其等于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//3.再接着判断传来的加载因子,如果小于零或者不是一个数字直接抛出异常。
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
//4.然后调用了一个tableSizeFor()方法去处理传进来的初始容量
this.threshold = tableSizeFor(initialCapacity);
}
继续追踪分析代码:进入到tableSizeFor()
方法 : 这个处理初始容量的方法;
/** * Returns a power of two size for the given target capacity. * 它的作用是返回一个大于输入参数,且最接近的2的整数次幂的数 */
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/* 解释下这个算法 : 需要先了解: 右移 和 位或这里使用的是位运算:假设n的二进01xxx…xxx;先对n右移1位则结果为:001xx…xxx,再进行位或结果为:011xx…xxx;再对n右移2位则结果为:00011…xxx,再进行位或结果为:01111…xxx;此时前面已经有四个1了,再右移4位,然后进行位或可得8个1;同理,有8个1,再右移8位,然后进行位或肯定会让后八位也为1;综上可得,该算法让最高位的1后面的位全变为1。最后再让结果n+1,即得到了2的整数次幂的值了。而最开始:cap-1再赋值给n的目的是:让找到的目标值 >= 原值*/
解释:HashMap为了实现存取高效,要尽量减少碰撞,就是要尽量做到:把数据分配均匀,保证每个链表长度大致相同,我们就需要一个算法来实现:将存入的数据保存到那个链表中的算法;而这个算法实际就是取模:hash%length
但是,大家都知道这种运算不如位移运算快。因此,源码中做了优化 hash&(length-1)
。
也就是说 hash%length==hash&(length-1)
那为什么是2的n次方呢?
因为2的n次方实际就是1后面n个0,而2的n次方-1,实际就是n个1。
例如长度为8时候,3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞。而长度为5的时候,3&(5-1)=0 2&(5-1)=0,都在0上,出现碰撞了。所以,保证容积是2的n次方,是为了保证在做(length-1)的时候,每一位都能 &1 ,也就是和1111……1111111进行与运算。即:两位同时为“1”,结果才为“1”,否则为0
那么为什么要把初始容量转成2的指数次幂呢?不转成2的指数次幂也是可以存储的啊,为什么要转?
首先看HashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其中的hash方法用于计算key的哈希值;
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
关于这个Hash的思考
为什么为什么要先高16位异或低16位再取模运算?
hashmap这么做,只是为了降低hash冲突的几率。
打个比方,当我们的length为16的时候,哈希码(字符串“abcabcabcabcabc”的key对应的哈希码) 和 (16-1)进行与操作,对于多个key生成的hashCode,只要哈希码的后4位为0,不论不论高位怎么变化,最终的结果均为0。因为与运算中两位同时为“1”,结果才为“1”,否则为0
; 如下:
而加上高16位异或低16位的“扰动函数”后,结果如下
可以看到: 扰动函数优化前:1954974080 % 16 = 1954974080 & (16 - 1) = 0 扰动函数优化后:1955003654 % 16 = 1955003654 & (16 - 1) = 6 很显然,减少了碰撞的几率。
我们一开始提到过,添加元素时索引的下标可以通过取模运算获得,但是我们知道计算机的运行效率:加法(减法)>乘法>除法>取模,取模的效率是最低的。所以我们要在HashMap中避免频繁的取模运算,又因为在我们HashMap中他要通过取模去定位我们的索引,并且HashMap是在不停的扩容,数组一旦达到容量的阈值的时候就需要对数组进行扩容。那么扩容就意味着要进行数组的移动,数组一旦移动,每移动一次就要重回记算索引,这个过程中牵扯大量元素的迁移,就会大大影响效率。那么如果说我们直接使用与运算,这个效率是远远高于取模运算的!
putVal方法,它是实现具体的put操作的方法
再来看putVal方法,它是实现具体的put操作的方法,来看一下源码;
//实现put操作
//返回值: @return 之前的value
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. 如果当前table为空,新建默认大小的table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//2. 获取当前key对应的节点
if ((p = tab[i = (n - 1) & hash]) == null)
//3. 如果不存在,新建节点
tab[i] = newNode(hash, key, value, null);
else {
//4. 存在节点
Node<K,V> e; K k;
//5. key的hash相同,key的引用相同或者key equals,则覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//6. 如果当前节点是一个红黑树树节点,则添加树节点
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//7. 不是红黑树节点,也不是相同节点,则表示为链表结构
else {
for (int binCount = 0; ; ++binCount) {
//8. 找到最后那个节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//9. 如果链表长度超过8转成红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//10.如果链表中有相同的节点,则覆盖
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;
//是否替换掉value值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
//是否超过容量,超过需要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
由以上源码第2步,tab[i = (n - 1) & hash]
中tab就是HashMap的实体数组,其下边通过i = (n - 1) & hash
来获取(n表示数组长度,hash表示hashCode值),但是这必须保证数组长度为2的整数次幂,我们继续往下看
现在我们可以使用与运算(n-1) & hash
取代取模运算hash%length
,因为这两种方式记算出来的结果是一致的(n就是length),也就是(length-1)&hash = hash%length
,例如:假设数组长度为4,哈希值为10
(n-1) & hash = (4-1) & 10 = 00000011 & 00001010 = 00000010 = 2
hash % length = 10 % 4 = 2
但是当数组的长=长度不为2的指数次幂时,两种方式计算的结果不一样,即(length-1)&hash ≠ hash&length
例如:再假设数组长度为5,哈希值10
(n-1) & hash = (5-1) & 10 = 00000100 & 00001010 = 00000000 = 0
hash % length = 10 % 5 = 2
显然,当数组长度不为2的整数次幂时二者是不相等的!
但最重要的一点,是要保证定位出来的值是在数组的长度之内的,不能超出数组长度,并且减少哈希碰撞,让每个位都可能被取到,我们来看下面例子:
例如:(16-1) & hash
二进制的15: 0000 0000 0000 1111
hash(随机) 1101 0111 1011 0000
hash(随机) 1101 0111 1011 1111
结果 0000 0000 0000 0001 ~ 0000 0000 0000 1111
即得出的索引下标只能在0~15之间,保证了所有索引都在数组长度的范围内而不会越界
并且由于2的指数次幂-1都是...1111的形式的,即最后一位是1
这样,由于hash是随机的,进行与运算后每一位都是能取到的
========================================================================
反例:(7-1) & hash
二进制6: 0000 0000 0000 0110
hash 1011 1001 0101 0000
hash 1001 0001 0000 1111
结果 0000 0000 0000 0000 ~ 0000 0000 0000 0110
即得出的索引范围在0~6,虽然不会越界,但最后一位是0
即现在无论hash为何值,0001,0011,0101这几个值是不可能取到的
这就加剧了hash碰撞,并且浪费了大量数组空间,显然是我们不想看到的
总结:首先使用位运算来加快计算的效率,而要使用位运算,就需要数组-1然后与hash值保证其在数组范围内,只有当数组长度为2的指数次幂时,其计算得出的值才能和取模算法的值相等,并且保证能取到数组的每一位,减少哈希碰撞,不浪费大量的数组资源!
HashMap加载因子及转红黑树探究/HashMap探究(二)
今天我们来探究下:负载因子为什么是0.75?为什么红黑树扩容是当链表长度>=8时扩容?Java7的hashmap扩容死锁演示与环链形成分析?
负载因子为什么是0.75?
我们先来看看源码:在构造函数中未指定时使用的加载因子
/** * The load factor used when none specified in constructor. */
static final float DEFAULT_LOAD_FACTOR = 0.75f;
我们知道,最理想的情况就是,当我们put进来的元素刚好平铺在数组上,而不产生链表,尽量不产生 Hash 碰撞。但是我们明白这种情况只是理想化的,是难以实现的。
那么我们反证一下:当我们将负载因子不定为0.75的时候(两种情况):
1、 假如负载因子定为1(最大值),那么只有当元素填慢数组长度的时候才会选择去扩容,虽然负载因子定为1可以最大程度的提高空间的利用率,但是我们的查询效率会变得低下(因为链表查询比较慢)
结论:所以当加载因子比较大的时候:节省空间资源,耗费时间资源
2、加入负载因子定为0.5(一个比较小的值),也就是说,知道到达数组空间的一半的时候就会去扩容。虽然说负载因子比较小可以最大可能的降低hash冲突,链表的长度也会越少,但是空间浪费会比较大
结论:所以当加载因子比较小的时候:节省时间资源,耗费空间资源
但是我们设计程序的时候肯定是会在空间以及时间上做平衡,那么我们能就需要在时间复杂度和空间复杂度上做折中,选择最合适的负载因子以保证最优化。所以就选择了0.75这个值,Jdk那帮工程师一定是做了大量的测试,得出的这个值吧~
为什么红黑树扩容是当链表长度>=8时扩容
看源码:当链表数量大于8时转化为树
/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. * 树阈值 = 8; */
static final int TREEIFY_THRESHOLD = 8;
泊松分布
当我们在put一个元素,产生hash冲突的时候,会遵循泊松分布(通过概率学统计出来)的规则;
泊松分布公式:(exp(-0.5) * pow(0.5, k)
泊松分布图:
意思就是说,当负载因子为0.75的时候,还有当链表的长度的增加。如果再添加新的节点进链表的时候,这个添加进当前链表概率是随着节点的增加而越来越少(泊松分布)。JDK源码中有这样的解释:
也就是说,当put进来一个元素,通过hash算法,然后最后定位到同一个桶(链表)的概率会随着链表的长度的增加而减少,当这个链表长度为8的时候,这个概率几乎接近于0,所以我们才会将链表转红黑树的临界值定为8
当然,虽然在hashmap底层有这种红黑树的结构,但是我们要知道能产生这种结构的概率也不大,所以我们知道在 JDK1.7 到 JDK1.8 这其中HashMap的性能只提高了 7%-8% 左右,提高的并不多。
Java7的hashmap扩容死锁演示与环链形成分析
Java7的hashmap扩容死锁演示与环链形成分析
我们首先来看一下JDK1.7中put方法的源码
我们打开addEntry方法如下,它会判断数组当前容量是否已经超过的阈值,例如假设当前的数组容量是16,加载因子为0.75,即超过了12,并且刚好要插入的索引处有元素,这时候就需要进行扩容操作,可以看到resize扩容大小是原数组的两倍,仍然符合数组的长度是2的指数次幂
我们再进入resize方法如下,它首先会对之前的数组容量进行判断,看是否已经达到了数组最大容量,如果没有,后面会进行数组的转移操作,即transfer方法
JDK1.7中,当数组容量达到16*0.75=12
的时候,数组就需要扩容,在扩容的时候,我们都知道会涉及元素的迁移,那么下面代码就是元素迁移的主要代码:JDK1.7中HashMap存在死锁问题的原因也主要集中在这
//将老的表中的数据拷贝到新的结构中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;//容量
for (Entry<K,V> e : table) { //遍历所有桶:即数组
while(null != e) { //遍历桶中所有元素(是一个链表)
Entry<K,V> next = e.next;
if (rehash) {//如果是重新Hash,则需要重新计算hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);//定位Hash桶
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入,总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
}
我们将重新记算hash值的逻辑先去掉(回顾:为什么使用位运算而不使用取模运算:因为位运算效率高,取模运算效率低,在数组迁移的时候会进行重hash,如果效率不高会极大的影响put的效率)。只留下主要的迁移数组的代码:
for (Entry<K,V> e : table) { //遍历所有桶
while(null != e) { //遍历桶中所有元素(是一个链表)
Entry<K,V> next = e.next;
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入,总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
}
}
举例:
假设有两个线程,两个线程都对这个hashmap进行扩容,扩容就要执行数组迁移代码。
假设线程T2先来对数组进行迁移,当线程而二执行到Entry<K,V> next = e.next的时候,然后线程T2突然阻塞了;
外层for循环来遍历数组的,当数组的值不是空的时候就进入内层的while循环去遍历链表,假设线程T2两个指针(一个叫做e2,一个叫做next2),当遍历到这个结点的时候:e2表示的就是大狂神这个节点,next2表示e2的下一个节点,也就是佩雨的这个节点;
然后刚好线程T1也跑进啦这个逻辑里面了,那么线程T1也有两个指针(e,next),e也指向的是大狂神,next也指向的是佩雨
T1线程继续跑这个逻辑(下面是T1线程自己的扩容与迁移图),会继续转移这个链表,转移完成之后发现一个问题:转移过去后两个节点的上下位置反了(大狂神和佩雨已经反了)
然后T2这个时候又唤醒了,因为线程T2一直都是指向这两个元素的(e2–>大狂神,next–>佩雨),也就是成下图这样
然后T2也要去循环执行这个逻辑
e.next = newTable[i];//元素连接到桶中,这里相当于单链表的插入,总是插入在最前面
newTable[i] = e;//newTable[i]的值总是最新插入的值
e = next;//继续下一个元素
最后会产生这样的情况,就是最终会形成一个环
Java8中的HashMap扩容优化(不会出现死环)
JDK1.8中HashMap扩容的代码
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
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) {
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 { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
然后用当前节点的hash值和旧数组的长度(16)做’与’运算
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
分析:
hash值: 0010 1111 1010 1110
数组的长度(16) 0000 0000 0000 1000
‘与’运算的结果,只可能有两种值:
0000 0000 0000 0000---------------0
0000 0000 0000 1000---------------16
也就是说当前节点用当前节点的hash值和旧数组的长度(16)做'与'运算的结果只可能是0或16
用当前节点的hash值和旧数组的长度(16)做’与’运算,结果出来如果时0就是低位指针,如果是16就是高位指针,那么我们再看:
// 如果是0,则使用低位的指针
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else { // 如果是16,则使用高位的指针
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
如果说 ‘与’ 出来的值是0,那么就会用低位的指针去迁移该数组。如果判断出来的是16,就会用高位的指针去迁移。
那么我们的最终的指针就会成下面的样子:
然后就开始迁移
低位迁移:首先:先将高位和低位断开(将低位的尾部的next置为空)
if (loTail != null) {
//把低位的尾部节点的next值为空(先将高位和低位断开)
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
就成下面这样了:
紧接着将低位的头部loHead付给新数组的某个值,也就是将低位的所有节点移动过去,并且放在与就索引相同的位置;
if (loTail != null) {
//把低位的尾部节点的next值为空(先将高位和低位断开)
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值,也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
高位迁移:先将高位的尾部断开
if (loTail != null) {
//把低位的尾部节点的next值为空(先将高位和低位断开)
loTail.next = null;
newTab[j] = loHead; //将高位的头部赋给新数组的某个值,也就是将高位的所有节点移动过去
}
if (hiTail != null) {
hiTail.next = null; //把高位的尾部节点的next值为空
newTab[j + oldCap] = hiHead;
}
再将高位的头部放到新数组的j + oldCap索引处(当前索引+旧数组的长度),比如说现在的索引是3,再加上数组长度16,最后就是将高位放到新数组的索引为19的地方去;
然后我们发现这个设计非常的巧妙,避免了顺序的颠倒,再也不会出现狂神和佩雨颠倒的问题了
总结
在JDK1.8之后,HashMap底层的数组扩容后迁移的方法进行了优化。把一个链表分成了两组,分成高为和低位分别去迁移,避免了死环问题。而且在迁移的过程中并没有进行任何的rehash(重新记算hash),提高了性能。它是直接将链表给断掉,进行几乎是一个均等的拆分,然后通过头指针的指向将整体给迁移过去,这样就减小了链表的长度
Q.E.D.