虽然我们现在开发中使用的JDK一般都是JDK8了但是最近还是有很多同学在面试的过程中遇到了JDK1.7的一些问题那么接下来我们就带着大家一起来聊一下HashMap在1.7中的各种问题。
出现问题主要是由于扩容的如下代码导致的：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry e = src[j];
if (e != null) {
src[j] = null;
do {
Entry next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
一、put一个数据get返回null
从上面代码中可以看到扩容的时候会把存储数据的table数组赋值给src数组然后遍历src里面的每一个元素看是否为空的如果为空则把src[j]置为空,此时就出问题了。
原本应该获取到open的但是现在可能只能获取到null了,主要出现的原因是线程一扩容的时候会对table中的数据进行修改,此时线程二来获取可能就获取到的是修改后的值(null),当线程一操作完成以后线程二再次获取也不会出现该问题,该问题只会出现在扩容中。
二、扩容的实现出现循环链表
还是上面那一段代码,如果是在单线程的环境下执行扩容是不会有任何问题的,大致的扩容如下：
从扩容的过程中大家可以看到扩容的时候是把原来的链表顺序倒置然后插入到新的下标中,这个过程其实就是经常说的头插法也就是这个问题导致了循环链表的问题，那么接下来就一起来看下多线程环境下是如何形成的循环链表的：
线程一：
do {
Entry next = e.next; //线程一执行到这一行的时候挂起
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
线程二：完整的执行完成所有的扩容操作
从图中可以看到当线程一进行第三次循环的时候就已经形成了循环链表了。
三、丢失数据
上图除了描述扩容的过程中会形成循环链表以外还描述了一个问题就是在扩容的时候有一个数据丢失了,原因是因为next指向的是k2现在k2的next指向的不是k3而是k1所以k3的数据不能拷贝到新的数组中所以出现数据丢失。
四、Cpu占用100%
在多线程环境下我们通过get方式去获取数据的时候,可能出现cpu占用100%的情况,主要的原因是我们hash计算索引的时候计算到了2,然后2这个下标里面又有一个循环链表,只要我们进入该循环链表我们的程序就出不来了,然后cpu就会占用到100,同时也获取不到数据,这个其实也是一个隐形的数据丢失的情况,虽然数据存在但是因为进入了循环链表所以数据怎么都获取不到。
五、如何解决以上的问题
- 使用线程安全的HashTable替换HashMap,当然现在HashTble已经几乎在项目中看不到了
- 通过Collections.synchronizedMap获取到一个线程安全的HashMap
- ConcurrentHashMap替换HashMap【下一篇文章我们就将讲解ConcurrentHashMap】
六、JDK1.8如何解决循环链表的问题
JDK1.8采用的是数据+链表+红黑树的方式来实现的,同时他重构了resize的迁移方法,把HashMap的头插法修改为了所谓的尾插法,他保证了数据迁移的顺序问题。
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; //核心代码
}
}
因为JDK1.8的resize中会牵涉到红黑树的实现,很多的同学如果没有学过数据结果可能听不懂所以再次我就不打算再去展开讲解了，以后有机会给大家分享数据结构的内容,听懂了以后再回过头来查阅这段代码。
