jdk1.7中hashMap死鎖詳解

死鎖發生的條件

在hashMap擴容時，且在多線程通路時可能發生死鎖。

分析

1. 生成一個hashMap的初始table。

public static void main(String[] args) {
        // 測試 java 7 中哪些數字的 hash 結果相等
        System.out.println("長度為16時，桶下标為1的key");
        for (int i = 0; i < 64; i++) {
            if (hash(i) % 16 == 1) {
                System.out.println(i);
            }
        }
        System.out.println("長度為32時，桶下标為1的key");
        for (int i = 0; i < 64; i++) {
            if (hash(i) % 32 == 1) {
                System.out.println(i);
            }
        }
        // 1, 35, 16, 50 當大小為16時，它們在一個桶内
        final HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        // 放 12 個元素
        map.put(2, null);
        map.put(3, null);
        map.put(4, null);
        map.put(5, null);
        map.put(6, null);
        map.put(7, null);
        map.put(8, null);
        map.put(9, null);
        map.put(10, null);
        //因為連結清單采用頭插法，是以下面三個節點為table[1]的前三個節點
        map.put(16, null);
        map.put(35, null);
        map.put(1, null);
        System.out.println("擴容前大小[main]:"+map.size());
        new Thread() {
            @Override
            public void run() {
                // 放第 13 個元素, 發生擴容
                map.put(50, null);
                System.out.println("擴容後大小[Thread-0]:"+map.size());
            }
        }.start();
        new Thread() {
            @Override
            public void run() {
                // 放第 13 個元素, 發生擴容
                map.put(50, null);
                System.out.println("擴容後大小[Thread-1]:"+map.size());
            }
        }.start();
    }
    //hashMap中的哈希函數，用來生成hash值
    final static int hash(Object k) {
        int h = 0;
        if (0 != h && k instanceof String) {
            return sun.misc.Hashing.stringHash32((String) k);
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
           

1. 主要分析table[1]位置，如下圖。

   

2. 如果再插入<50,null>鍵值對，則數組擴容，将鍵值對重新配置設定。源碼如下，死鎖主要發生在這裡。

void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }
           

1. 兩個線程同時運作，線程0和線程1同時運作到 if(rehash){ 這一行。e和next 的指向如下圖。

   

2. 線程0停止，線程1運作完，數組擴容後，鍵值對會進行重排，如下圖。

   

3. 線程0和線程1都是通路的相同的節點，是以當線程1運作完後線程0的指向如下。e還是指向1，next還是指向35。但是線程1将連結清單的結構改變了。

   

4. 對比線程0先後兩種狀态，如果線程0繼續運作，則會發生死循環。