Java HashMapのデッドサイクル

タオバオのネットの中で同僚が1つのCPUが100%のオンライン上で故障されたと貼り付けたのを見て、しかもこの事は何度も発生して、Java言語が同時の情況の下でHashMapを使ってRace Conditionをもたらして、それによって死の循環を招いたためです.このことは私も4、5年前に経験したことがありますが、もともと書くことがないと思っていましたが、JavaのHashMapは非スレッドで安全なので、併発すると必ず問題が発生します.しかし、ここ数年、多くの人がこのことを経験していることに気づきました(ネットで「HashMap Infinite Loop」を調べると多くの人がこのことを言っているのが見えます)、これは普遍的な問題だと思います.ワクチンの文章を書いてこのことを話し、完璧な「Race Condition」がどのように形成されているかを見せなければなりません.
        問題の症状
        以前、私たちのJavaコードはいくつかの理由でHashMapというものを使っていましたが、当時のプログラムは単一スレッドで、すべて問題ありませんでした.その後、私たちのプログラムの性能に問題があるので、マルチスレッドになる必要があります.そこで、マルチスレッドになってからオンラインになると、プログラムが常に100%のCPUを占めていることを発見します.スタックを見てみると、プログラムがHashMap.get()という方法でHangしていることがわかります.プログラムを再起動すると問題がなくなります.しかし、しばらくするとまた来ます.また、この問題はテスト環境では再現しにくいかもしれません.
        私たち自身のコードを簡単に見ると、HashMapが複数のスレッドで操作されていることがわかります.Javaのドキュメントでは、HashMapは非スレッドで安全であり、ConcurrentHashMapを使用する必要があります.
        しかし、ここで原因を研究することができます.
        Hashテーブルデータ構造
        HashMapという古典的なデータ構造を簡単に説明する必要があります.
        HashMapは通常、1つのポインタ配列(table[]と仮定)ですべてのkeyを分散し、1つのkeyが追加されると、Hashアルゴリズムによってkeyによってこの配列の下付きiを算出し、それをtable[i]に挿入し、2つの異なるkeyが同じiに計算されると、衝突と呼ばれ、衝突と呼ばれ、table[i]に存在するにチェーンテーブルを作成します.
        table[]のサイズが小さく、例えば2個しかない場合、10個のkeysを入れると衝突が非常に頻繁になり、O(1)のルックアップアルゴリズムがチェーンテーブル遍歴となり、性能がO(n)となり、これがHashテーブルの欠陥であることが知られている(『Hash Collision DoS問題』参照).
        したがって、Hashテーブルのサイズと容量は非常に重要です.一般的に、Hashテーブルというコンテナは、データを挿入する際に、設定されたthredholdを超えた容量があるかどうかをチェックし、超えた場合はHashテーブルのサイズを大きくする必要がありますが、これにより、Hashテーブル全体の無素が再計算される必要があります.これはrehashと呼ばれ、このコストはかなり大きいです.
        皆さんはこの基礎知識に詳しいと信じています.
        HashMapのrehashソースコード
        次に、JavaのHashMapのソースコードを見てみましょう.
        Putキー、Value対Hashテーブル:

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

        容量が基準値を超えているかどうかを確認

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

        より大きなサイズのhashテーブルを新規作成し、古いHashテーブルから新しいHashテーブルにデータを移行します.

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);
}

        移行されたソースコード、ハイライトに注意:

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

        はい、このコードは普通です.それに何の問題もありません.
        通常のReHashのプロセス
        図を描いてプレゼンテーションをした.

私たちのhashアルゴリズムは簡単にkey modでテーブルの大きさ(つまり配列の長さ)を調べると仮定しました.

の一番上にあるのはold hash表で、その中のHash表のsize=2なのでkey=3,7,5はmod 2以降はtable[1]に衝突した.

次の3つのステップは、Hashテーブルresizeが4になり、その後、すべての再rehashプロセス

である.
        そしてリリースしたRehash
        1)スレッドが2つあると仮定します.赤と水色で表記しました.
        transferコードの詳細を振り返ってみましょう.

do {
    Entry<K,V> next = e.next; // <--                  int i = indexFor (e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

        スレッド2の実行が完了しましたそこで私たちは次のようなものを持っています.
        なお、Thread 1のeはkey(3)を指し、nextはkey(7)を指し、スレッド2 rehashの後、スレッド2再結合後のチェーンテーブルを指す.チェーンテーブルの順序が反転した後を見ることができます.
        2)スレッドがスケジューリングされると実行される.

は、まずnewTalbe[i]=eを実行する.

、次いでe=nextであり、eはkey(7)を指し、

をもたらす.

で次のサイクルのnext=e.nextは、key(3)

を指すnextをもたらす.
        3)万事順調です.
        スレッドが動作します.キー(7)を外し、newTable[i]の1つ目に置き、eとnextを下に移動します.
        4)リングリンクが表示されます.
        e.next=newTable[i]による  key(3).nextはkey(7)を指す
        注意:このときのkey(7).nextはkey(3)を指しており、リングチェーンテーブルがこのように現れている.
        そこで、私たちのスレッドがHashTable.get(11)に呼び出されると、悲劇が現れました.Infinite Loopです.
        その他
        誰かがこの問題をSunに報告したが,Sunはこれが問題だとは思わない.そもそもハンシュマップは同時対応していないからです.同時実行するにはConcurrentHashmapを使用します
        http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6423457
        私はここでこのことを記録して、ただみんなに同時環境の下の危険を理解して体得させるためです.