并发源码|Hashmap死循环问题与ConcurrentHashmap
jdk7hashmap死循环问题
在多线程并发环境下。不应该用此容器,而应使用线程安全的容器如ConcurrentHashmap
其死循环主要是扩容的时候resize方法内调用的transfer方法导致。
e.next = newTable[i];
newTable[i] = e;
如果两个线程正在处理同一个节点e,那么第一个线程正常执行,但是第二个线程设置e.next=e,因为第一个线程已经将newTable[i]设置为e。节点e现在指向它自己,当调用get(Object)时,它将进入一个无限循环。无限循环则会导致cpu100%,另外因为节点形成了环形,后面的元素无法访问到导致数据丢失
而java8中,resize的时候保持了节点的顺序。但同样会有数据丢失的问题
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
jdk7与jdk8关于Hashmap的主要区别
1、jdk7中数据结构为:数组+链表 jdk8中数据结构为:数组+链表/红黑树 当链表数量大于8时,链表转化为红黑树
2、hash值的计算:jdk8采用高低16位异或来进行hashcode计算,可以尽量减少hash碰撞
3、链表的插入:jdk7采用头插法,扩容后元素位置相反。jdk8中采用尾插法,扩容后元素位置一致
ConcurrentHashmap
put源码中,Unsafe,CAS的操作,都是线程安全的,保证了只有一个线程可以在这里成功的将一个key-value对方在数组的一个地方里。如果多个线程并发来执行put的操作,都走到这里,可能就会有其他的线程,CAS往数组里赋值操作就会失败,如果CAS成功了,此时就直接break掉,put操作就成功了
/**
* Maps the specified key to the specified value in this table.
* Neither the key nor the value can be null.
*
* <p>The value can be retrieved by calling the {@code get} method
* with a key that is equal to the original key.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}
* @throws NullPointerException if the specified key or value is null
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//此处有hash冲突,只对有hash冲突的节点进行加锁
//体现了分段加锁的思想,jdk7中使用segment锁冲突会更多,jdk8锁粒度更细
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
get类似,使用Unsafe保证线程安全。Node的val是volatile的,保持了多线程可见性
扩容,扩容时使用
对于get、size、遍历 这些操作,都是弱一致性的
- 原文作者:
- 原文链接:https://leyou240.github.io/post/juc07_hashmap%E6%AD%BB%E5%BE%AA%E7%8E%AF%E4%BB%A5%E5%8F%8Aconcurrenthashmap/
- 版权声明:本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可,非商业转载请注明出处(作者,原文链接),商业转载请联系作者获得授权。