顺义区专业网站制作网站建设,免费ppt下载网站有哪些,施工企业样板先行制度,图书销售网站建设HashMap用在并发场景存在的问题 一、✅典型解析1.1 ✅JDK 1.8中1.2 ✅JDK 1.7中1.3 ✅如何避免这些问题 二、 ✅HashMap并发场景详解2.1 ✅扩容过程2.2 ✅ 并发现象 三、✅拓展知识仓3.1 ✅1.7为什么要将rehash的节点作为新链表的根节点3.2 ✅1.8是如何解决这个问题的3.3 ✅除了… HashMap用在并发场景存在的问题 一、✅典型解析1.1 ✅JDK 1.8中1.2 ✅JDK 1.7中1.3 ✅如何避免这些问题 二、 ✅HashMap并发场景详解2.1 ✅扩容过程2.2 ✅ 并发现象 三、✅拓展知识仓3.1 ✅1.7为什么要将rehash的节点作为新链表的根节点3.2 ✅1.8是如何解决这个问题的3.3 ✅除了并发死循环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时出现的问题可以下几种方法 使用线程安全的HashMap实现Java提供了线程安全的HashMap实现如ConcurrentHashMap。ConcurrentHashMap采用了分段锁的机制可以保证在多线程环境下对HashMap的读写操作都是安全的。 手动同步如果必须使用HashMap可以在访问HashMap时进行手动同步。使用synchronized关键字将访问HashMap的代码块包装起来保证同一时间只有一个线程可以访问HashMap从而避免并发问题。 使用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) {ConcurrentHashMapString, 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) {MapString, String map new HashMap();// 手动同步访问HashMapsynchronized (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) {ConcurrentHashMapString, 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 。 看一张图片 之所以选择使用头插法是因为JDK的开发者认为后插入的数据被使用到的概率更高更容易成为热点数据而通过头插法把它们放在队列头部就可以使查询效率更高。 我们再来看一眼源码 void transfer(Entry[] newTable) {Entry[] src table;int newCapacity newTable.length;for (int j 9; j src.length; j) {EntryK,V e src[j];if (e ! null) {src[j] null;do {EntryK,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 执行到 EntryK, next e.next; 的时候被hang住如下图所示: 此时 thread-2 开始执行当 thread-2 扩容完成后结果如下: 此时 thread-1 抢占到执行时间开始执行e.next newTable[i]; newTable[i] e; e next;后会变成如下样式: 接着进行下一次循环继续执行 e.next newTable[i]; newTable[i] e; e next; 如下图所示 因为此时 e ! null且 e.next null开始执行最后一次循环结果如下 可以看到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) {EntryK,V e src[j];if (e ! null) {src[j] null;do {EntryK,V next e.next;int i indexFor(e.hash , newCapacity);//如果新桶中没有数值则直接放进去if (newTable[i] null) {newTable[i] e;continue;}// 如果有则遍历新桶的链表else {EntryK,V newTableEle newTable[i];while(newTableEle ! null) {EntryK,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 NodeK,V[] resize() {NodeK,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 thresholdelse if (oldThr 0) {newCap oldThr;}// zero initial threshold signifies using defaultselse {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})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,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)((TreeNodeK,V)e).split(thisnewTabjoldCap);// preserve orderelse {NodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,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;elsehiTail.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不到数据
