网页特效代码网站,太原网站设计费用,在线制作app平台,哪个网站做非洲的生意HashMap是线程不安全的#xff0c;在多线程环境下对某个对象中HashMap类型的实例变量进行操作时#xff0c;可能会产生各种不符合预期的问题。本文详细说明一下HashMap存在的几个线程安全问题。注#xff1a;以下基于JDK1.8HashMap原理请走传送门通过简单例子来探索HashMap原… HashMap是线程不安全的在多线程环境下对某个对象中HashMap类型的实例变量进行操作时可能会产生各种不符合预期的问题。本文详细说明一下HashMap存在的几个线程安全问题。注以下基于JDK1.8HashMap原理请走传送门通过简单例子来探索HashMap原理及内部存储结构1 多线程的put可能导致元素的丢失1.1 试验代码如下注仅作为可能会产生这个问题的样例代码直接运行不一定会产生问题public class ConcurrentIssueDemo1 {private static MapString, String map new HashMap();public static void main(String[] args) {// 线程1 t1new Thread(new Runnable() {Overridepublic void run() {for (int i 0; i 99999999; i) {map.put(thread1_key i, thread1_value i);}}}).start();// 线程2 t2new Thread(new Runnable() {Overridepublic void run() {for (int i 0; i 99999999; i) {map.put(thread2_key i, thread2_value i);}}}).start();}
}
1.2 触发此问题的场景先来看一下put方法的源码public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, I;// 初始化hash表if ((tab table) null || (n tab.length) 0)n (tab resize()).length;// 通过hash值计算在hash表中的位置并将这个位置上的元素赋值给p如果是空的则new一个新的node放在这个位置上if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {// hash表的当前index已经存在元素向这个元素后追加链表NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {// 新建节点并追加到链表if ((e p.next) null) { // #1p.next newNode(hash, key, value, null); // #2if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
}
假设当前HashMap中的table状态如下此时t1和t2同时执行put假设t1执行put(“key2”, “value2”)t2执行put(“key3”, “value3”)并且key2和key3的hash值与图中的key1相同。那么正常情况下put完成后table的状态应该是下图二者其一下面来看看异常情况假设线程1、线程2现在都执行到put源代码中#1的位置且当前table状态如下然后两个线程都执行了if ((e p.next) null)这句代码来到了#2这行代码。此时假设t1先执行p.next newNode(hash, key, value, null);那么table会变成如下状态紧接着t2执行p.next newNode(hash, key, value, null);此时table会变成如下状态这样一来key2元素就丢了。2 put和get并发时可能导致get为null场景线程1执行put时因为元素个数超出threshold而导致rehash线程2此时执行get有可能导致这个问题。分析如下先看下resize方法源码大致意思是先计算新的容量和threshold在创建一个新hash表最后将旧hash表中元素rehash到新的hash表中重点代码在于#1和#2两句// hash表
transient NodeK,V[] table;final NodeK,V[] resize() {// 计算新hash表容量大小beginNodeK,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 thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap 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;// 计算新hash表容量大小endNodeK,V[] newTab (NodeK,V[])new Node[newCap]; // #1// #2table newTab; // rehash beginif (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(this, newTab, j, oldCap);else { // preserve orderNodeK,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;elseloTail.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;}}}}}// rehash endreturn newTab;
}
在代码#1位置用新计算的容量new了一个新的hash表#2将新创建的空hash表赋值给实例变量table。注意此时实例变量table是空的。那么如果此时另一个线程执行get时就会get出null。3 JDK7中HashMap并发put会造成循环链表导致get时出现死循环此问题在JDK8中已经解决。3.1 JDK7中循环链表的形成发生在多线程并发resize的情况下。相关源码如下void resize(int newCapacity) {Entry[] oldTable table;int oldCapacity oldTable.length;if (oldCapacity MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return;}Entry[] newTable new Entry[newCapacity];transfer(newTable, initHashSeedAsNeeded(newCapacity));table newTable;threshold (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY 1);
}/*** Transfers all entries from current table to newTable.*/
// 关键在于这个transfer方法这个方法的作用是将旧hash表中的元素rehash到新的hash表中
void transfer(Entry[] newTable, boolean rehash) {int newCapacity newTable.length;for (EntryK,V e : table) { // table变量即为旧hash表while(null ! e) {// #1EntryK,V next e.next;if (rehash) {e.hash null e.key ? 0 : hash(e.key);}// 用元素的hash值计算出这个元素在新hash表中的位置int i indexFor(e.hash, newCapacity);// #2e.next newTable[I];// #3newTable[i] e;// #4e next;}}
}
假设线程1(t1)和线程2(t2)同时resize两个线程resize前两个线程及hashmap的状态如下堆内存中的HashMap对象中的table字段指向旧的hash表其中index为7的位置有两个元素我们以这两个元素的rehash为例看看循环链表是如何形成的。线程1和线程2分别new了一个hash表用newTable字段表示。PS如果将每一步的执行都以图的形式呈现出来篇幅过大这里提供一下每次循环结束时的状态可以根据代码一步一步推算。Step1: t2执行完#1代码后CPU且走执行t1并且t1执行完成这里可以根据上图推算一下此时状态如下用t2.e表示线程2中的局部变量et2.next同理。Step2: t2继续向下执行完本次循环Step3: t2继续执行下一次循环Step4: t2继续下一次循环循环链表出现3.2 死循环的出现HashMap.get方法源码如下:public V get(Object key) {if (key null)return getForNullKey();EntryK,V entry getEntry(key);return null entry ? null : entry.getValue();
}final EntryK,V getEntry(Object key) {if (size 0) {return null;}int hash (key null) ? 0 : hash(key);// 遍历链表for (EntryK,V e table[indexFor(hash, table.length)];e ! null;e e.next) {Object k;// 假设这里条件一直不成立if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;}return null;
}
由上图可知for循环中的e e.next永远不会为空那么如果get一个在这个链表中不存在的key时就会出现死循环了。
