HashMapマルチスレッドデッドサイクルJava

詳細
HashMapマルチスレッドデッドサイクルJava
HashMap,  スレッドが安全ではないことはよく知られています.マルチスレッドの場合get()ではデッドサイクルが発生する可能性が高い.なぜなら
HashMapはチェーンテーブルを用いてHash競合を解決するが,チェーンテーブル構造であるため,閉じたリンクを形成しやすく,ループ時にスレッドがこのHashMapをget操作するとデッドループを生じる.HashMapのデータ構造を操作するスレッドは1つしかなく,閉じたループを生成することは不可能である.それはマルチスレッド同時の場合にしか起こりません.それはput操作の場合、size>initialCapacity*loadFactorの場合、HashMapはrehash操作を行います

public V put(K key, V value)
{
    ......
    // Hash 
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    //   key    ，      value （    ）
    for (Entry 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++;
    // key   ，        
    addEntry(hash, key, value, i);
    return null;
}

 
容量が標準addEntryを超えているかどうかを確認します.

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry e = table[bucketIndex];
    table[bucketIndex] = new Entry(hash, key, value, e);
    //     size            threshold，    ，  resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

 現在sizeがthresholdを超えている場合は、resize操作を行い、より大きなサイズのhashテーブルを新規作成し、古いHashテーブルから新しいHashテーブルにデータを移行します.
 
Hashテーブルのサイズ変更resize

void resize(int newCapacity)
{
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    //      Hash Table
    Entry[] newTable = new Entry[newCapacity];
    // Old Hash Table       New Hash Table 
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

 
table[]配列容量が小さいとハッシュ衝突が発生しやすいため,Hashテーブルのサイズと容量は非常に重要である.一般的に、Hashテーブルというコンテナは、データを挿入するときに、設定したthredholdを超えた容量があるかどうかをチェックし、超えた場合はHashテーブルのサイズを大きくする必要があります.このプロセスをresizeと呼びます.
複数のスレッドが同時にHashMapに新しい要素を追加すると、複数のresizeは、古いデータを新しいハッシュテーブルにマッピングする必要があるため、resizeのたびに一定の確率でデッドサイクルが発生します.このコードの一部はHashMap#transfer()メソッドにあります.

void transfer(Entry[] newTable)
{
    Entry[] src = table;
    int newCapacity = newTable.length;
    //          ：
    //   OldTable        ，    NewTable 
    for (int j = 0; j < src.length; j++) {
        Entry e = src[j];
        if (e != null) {
            src[j] = null;
            do {
                Entry next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}