兰州网站建设人才招聘,无锡 学校网站建设,电商网站建设价格低,建立网站的英文怎么说转载自 HashMap在java并发中如何发生死循环 在多线程环境中#xff0c;使用HashMap进行put操作时会引起死循环#xff0c;导致CPU使用接近100%#xff0c;下面通过代码分析一下为什么会发生死循环。 首先先分析一下HashMap的数据结构#xff1a;HashMap底层数据结构是有一…转载自 HashMap在java并发中如何发生死循环 在多线程环境中使用HashMap进行put操作时会引起死循环导致CPU使用接近100%下面通过代码分析一下为什么会发生死循环。 首先先分析一下HashMap的数据结构HashMap底层数据结构是有一个链表数据构成的HashMap中定义了一个静态内部类作为链表代码如下与本文无关的代码省略
静态内部类entry代码 static class EntryK,V implements Map.EntryK,V { final K key; V value; EntryK,V next; final int hash; /** * Creates new entry. */ Entry(int h, K k, V v, EntryK,V n) { value v; next n; key k; hash h; } 、 } Hashmap属性代码
/** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; 之所以会导致HashMap出现死循环是因为多线程会导致HashMap的Entry节点形成环链这样当遍历集合时Entry的next节点用于不为空从而形成死循环 单添加元素时会通过key的hash值确认链表数组下标
public V put(K key, V value) { if (key null) return putForNullKey(value); //确认链表数组位置 int hash hash(key.hashCode()); int i indexFor(hash, table.length); //如果key相同则覆盖value部分 for (EntryK,V e table[i]; e ! null; e e.next) { Object k; if (e.hash hash ((k e.key) key || key.equals(k))) { V oldValue e.value; e.value value; e.recordAccess(this); return oldValue; } } modCount; //添加链表节点 addEntry(hash, key, value, i); return null; } 下面看一下HashMap添加节点的实现
void addEntry(int hash, K key, V value, int bucketIndex) { //bucketIndex 通过key的hash值与链表数组的长度计算得出 EntryK,V e table[bucketIndex]; //创建链表节点 table[bucketIndex] new EntryK,V(hash, key, value, e); //判断是否需要扩容 if (size threshold) resize(2 * table.length); } 以上部分的实现不会导致链路出现环链环链一般会出现HashMap扩容是下面看看扩容的实现:
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);//可能导致环链 table newTable; threshold (int)(newCapacity * loadFactor); } 下面transfer的实现
void transfer(Entry[] newTable) { Entry[] src table; int newCapacity newTable.length; for (int j 0; 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 newTable[i]; newTable[i] e; e next; } while (e ! null); } } } 这个方法的目的是将原链表数据的数组拷到新的链表数组中拷贝过程中如果形成环链的呢下面用一个简单的例子来说明一下
public class InfiniteLoop { static final MapInteger, Integer map new HashMapInteger, Integer(2, 0.75f); public static void main(String[] args) throws InterruptedException { map.put(5, 55); new Thread(Thread1) { public void run() { map.put(7, 77); System.out.println(map); }; }.start(); new Thread(Thread2) { public void run() { map.put(3, 33); System.out.println(map); }; }.start(); } } 下面通过debug跟踪调试来看看如果导致HashMap形成环链断点位置
线程1的put操作线程2的put操作线程2的输出操作HashMap源码transfer方法中的第一行、第六行、第九行测试开始 使线程1进入transfer方法第一行此时map的结构如下2. 使线程2进入transfer方法第一行,此时map的结构如下 3.接着切换回线程1执行到transfer的第六行此时map的结构如下 4.然后切换回线程2使其执行到transfer方法的第六行此时map的结够如上
5.接着切换回线程1使其执行到transfer方法的第九行然后切换回线程2使其执行完此时map的结构如下 6.切换回线程1执行循环因为线程1之前是停在HashMap的transfer方法的第九行处所以此时transfer方法的节点e的key3e.next的key7
void transfer(Entry[] newTable) { Entry[] src table; int newCapacity newTable.length; for (int j 0; 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);//线程1等线程2执行结束后 //从此处开始执行 //此时e的key3,e.next.key7 //但是此时的e.next.next的key3了 //被线程2修改了 e.next newTable[i]; newTable[i] e; e next; } while (e ! null); } } } 下面线程1开始执行第一次循环循环后的map结构如下 接着执行第二次循环e.key7,e.next.key3e.next.nextnull 接着执行第三次循环从而导致环链形成map结构如下 并且此时的map中还丢失了key5的节点
