【昕宝爸爸小模块】HashMap用在并发场景存在的问题

这篇具有很好参考价值的文章主要介绍了【昕宝爸爸小模块】HashMap用在并发场景存在的问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全


这是一个非常典型的问题,但是只会出现在1.7及以前的版本,1.8之后就被修复了。


一、✅典型解析


1.1 ✅JDK 1.8中


虽然JDK 1.8修复了某些多线程对HashMap进行操作的问题,但在并发场景下,HashMap仍然存在一些问题。

如:虽然JDK 1.8修复了多线程同时对HashMap扩容时可能引起的链表死循环问题但在JDK 1.8版本中多线程操作HashMap时仍然可能引起死循环,只是原因与JDK 1.7不同。此外,还存在数据丢失和容量不准确等问题

在并发场景下,HashMap主要存在以下问题:


1. 死循环问题:在JDK 1.8中,引入了红黑树优化数组链表,同时改成了尾插,按理来说是不会有环了,但是还是会出现死循环的问题,在链表转换成红黑数的时候无法跳出等多个地方都会出现这个问题。


2. 数据丢失问题:在并发环境下,如果一个线程在获取头结点和hash桶时被挂起,而这个hash桶在它重新执行前已经被其他线程更改过,那么该线程会持有一个过期的桶和头结点,并且会覆盖之前其他线程的记录,从而造成数据丢失。

3. 容量不准问题:在多线程环境下,HashMap的容量可能不准确。这是因为在进行resize(调整table大小)的过程中,如果多个线程同时进行操作,可能会导致数组链表中的链表形成循环链表,使得get操作时e = e.next操作无限循环,从而无法准确计算出HashMap的容量。

在并发场景下使用HashMap需要注意其存在的问题,并采取相应的措施进行优化和改进。


1.2 ✅JDK 1.7中


在JDK 1.7中,HashMap在并发场景下存在问题。

首先,如果在并发环境中使用HashMap保存数据,有可能会产生死循环的问题,造成CPU的使用率飙升。这是因为HashMap中的扩容问题。当HashMap中保存的值超过阈值时,将会进行一次扩容操作。在并发环境下,如果一个线程发现HashMap容量不够需要扩容,而在这个过程中,另外一个线程也刚好进行扩容操作,就有可能造成死循环的问题。

其次,HashMap在JDK 1.7中并不是线程安全的,因此在多线程环境下使用HashMap需要额外的同步措施来保证并发安全性。否则,可能会导致数据不一致或者出现其他并发问题。

因此,在JDK 1.7中,HashMap在并发场景下也存在一些问题需要注意和解决。


1.3 ✅如何避免这些问题


为了避免在并发场景下使用HashMap时出现的问题,可以下几种方法:

  1. 使用线程安全的HashMap实现:Java提供了线程安全的HashMap实现,如ConcurrentHashMap。ConcurrentHashMap采用了分段锁的机制,可以保证在多线程环境下对HashMap的读写操作都是安全的。

  2. 手动同步:如果必须使用HashMap,可以在访问HashMap时进行手动同步。使用synchronized关键字将访问HashMap的代码块包装起来,保证同一时间只有一个线程可以访问HashMap,从而避免并发问题。

  3. 使用Java并发包中的数据结构:Java提供了一些并发包(java.util.concurrent),其中包含了一些线程安全的集合类,如ConcurrentHashMap、CopyOnWriteArrayList等。这些数据结构在内部已经进行了优化,可以保证在多线程环境下的安全性和性能。

避免在并发场景下使用HashMap时出现问题的关键是选择合适的线程安全的实现或手动进行同步操作,以确保数据的一致性和正确性


看下面的这些Demo,解释了如何避免在并发场景下使用HashMap时出现的问题:


1. 使用线程安全的HashMap实现(ConcurrentHashMap


import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, String> concurrentHashMap = new ConcurrentHashMap<>();
        // 添加元素到ConcurrentHashMap中
        concurrentHashMap.put("key1", "value1");
        // 获取元素
        String value = concurrentHashMap.get("key1");
        System.out.println("Value for key1: " + value);
    }
}

2. 手动同步(使用synchronized关键字


import java.util.HashMap;
import java.util.Map;

public class SynchronizedHashMapExample {
    public static void main(String[] args) {
        Map<String, String> map = new HashMap<>();
        // 手动同步访问HashMap
        synchronized (map) {
            // 添加元素到HashMap中
            map.put("key1", "value1");
            // 获取元素
            String value = map.get("key1");
            System.out.println("Value for key1: " + value);
        }
    }
}

3. 使用Java并发包中的数据结构(如 ConcurrentHashMap

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

public class AtomicIntegerExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, AtomicInteger> concurrentHashMap = new ConcurrentHashMap<>();
        // 添加元素到ConcurrentHashMap中,使用AtomicInteger作为值,保证线程安全
        concurrentHashMap.put("key1", new AtomicInteger(1));
        // 获取并自增AtomicInteger的值,保持线程安全
        int newValue = concurrentHashMap.get("key1").incrementAndGet();
        System.out.println("New value for key1: " + newValue);
    }
}

二、 ✅HashMap并发场景详解


2.1 ✅扩容过程


HashMap在扩容的时候,会将元素插入链表头部,即头插法。如下图,原来是 A->B->C ,扩容后会变成 C->B->A


看一张图片:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

之所以选择使用头插法,是因为JDK的开发者认为,后插入的数据被使用到的概率更高,更容易成为热点数据,而通过头插法把它们放在队列头部,就可以使查询效率更高


我们再来看一眼源码:


void transfer(Entry[] newTable) {
	
	Entry[] src = table;
	int newCapacity = newTable.length;
	for (int j = 9; 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 = newTableli];
				newTable[i] = e;
				e = next;
			} while (e != null);
		}
	}
}

2.2 ✅ 并发现象


但是,正是由于直接把当前节点作为链表根节点的这种操作,导致了在多线程并发扩容的时候,产生了循环引用的问题。


假如说此时有两个线程进行扩容,thread-1 执行到 Entry<K,> next = e.next; 的时候被hang住,如下图所示:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

此时 thread-2 开始执行,当 thread-2 扩容完成后,结果如下:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

此时 thread-1 抢占到执行时间,开始执行e.next = newTable[i]; newTable[i] = e; e = next;后,会变成如下样式:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

接着,进行下一次循环,继续执行 e.next = newTable[i]; newTable[i] = e; e = next; ,如下图所示:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

因为此时 e != null,且 e.next = null,开始执行最后一次循环,结果如下:


【昕宝爸爸小模块】HashMap用在并发场景存在的问题,# Java集合类,java,开发语言,Hash,HashMap,线程安全

可以看到,a和b已经形成环状,当下次get该桶的数据时候,如果get不到,则会一直在a和b直接循环遍历,导致CPU飙升到100%。


三、✅拓展知识仓


3.1 ✅1.7为什么要将rehash的节点作为新链表的根节点


在重新映射的过程中,如果不将 rehash 的节点作为新链表的根节点,而是使用普通的做法,遍历新链表中的每一个节点,然后将rehash的节点放到新链表的尾部,伪代码如下:


void transfer(Entry[] newTable) {
	for (int j = ; 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);
				//如果新桶中没有数值,则直接放进去
				if (newTable[i] == null) {
					newTable[i] = e;
					continue;
				}
				// 如果有,则遍历新桶的链表
				else 
				{
					Entry<K,V> newTableEle = newTable[i];
					while(newTableEle != null) {
						Entry<K,V> newTableNext = newTableEle .next;
						//如果和新桶中链表中元素相同,则直接替换
						if(newTableEle.equals(e)) {
							newTableEle = e;
							break;
						}
						newTableEle = newTableNext ;
					}
					// 如果链表遍历完还没有相同的节点,则直接插入
					if(newTableEle == null) {
						newTableEle = e;
					}
				}
			} while (e != null);
		}
	}
}

通过上面的代码我们可以看到,这种做法不仅需要遍历老桶中的链表,还需要遍历新桶中的链表,时间复杂度是O(n^2),显然是不太符合预期的,所以需要将rehash的节点作为新桶中链表的根节点,这样就不需要二次遍历,时间复杂度就会降低到O(N)


3.2 ✅1.8是如何解决这个问题的


前面提到,之所以会发生这个死循环问题,是因为在JDK 1.8之前的版本中,HashMap是采用头插法进行扩容的,这个问题其实在JDK 1.8中已经被修复了,改用尾插法!JDK 1.8中的 resize 代码如下:


final Node<K,V>[] resize() {
	Node<K,V>[] oldTab = table;
	int oldCap = (oldTab == nul1) ?  : 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
		}
		// initial capacity was placed in threshold
		else if (oldThr > 0) {
			newCap = oldThr;
		}
		// zero initial threshold signifies using defaults
		else {
			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);
					// preserve order
					else {
						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;
	} 
}

3.3 ✅除了并发死循环,HashMap在并发环境还有啥问题


1. 多线程put的时候,size的个数和真正的个数不一样

2. 多线程put的时候,可能会把上一个put的值覆盖掉

3. 和其他不支持并发的集合一样,HashMap也采用了fail-fast操作,当多个线程同时put和get的时候,会抛出并发异常

4. 当既有get操作,又有扩容操作的时候,有可能数据刚好被扩容换了桶,导致get不到数据文章来源地址https://www.toymoban.com/news/detail-819590.html

到了这里,关于【昕宝爸爸小模块】HashMap用在并发场景存在的问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包