同期してないHashMapのget()とresize()がぶつかると値が取れない可能性がある

非同期状態のHashMapのサイズが拡張している最中にgetすると値が取れないことの確認。jdkの6u7。
putするとaddEntryが呼ばれて、要素数が閾値(指定しなければテーブルサイズの0.75倍)を超えたとき、テーブルサイズが2倍になる。
java.util.HashMap.addEntry()の抜粋

    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);
        if (size++ >= threshold)
            resize(2 * table.length); // ここ
    }

java.util.HashMap.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); // newTableに要素をコピー
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

そのresize()の中で新しいテーブルに要素をtransferメソッドでコピーしてる。このときコピー元が一時的にnullになる。
java.util.HashMap.transfer()の抜粋

    void transfer(Entry[] newTable) {
        Entry[] src = table; // tableはHashMapのテーブル(インスタンス変数)
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null; // コピー元テーブルに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);
            }
        }
    }

ひとつの同期してないHashMapからひたすらキー0でgetし続けるスレッドと、0が入っている状態でそのHashMapにどんどんputしていくスレッドを用意する。

    public void testPutGet() throws Exception {
        final HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        
        // ひたすらget
        Runnable getter = new Runnable() {
            public void run() {
                try {
                    Integer zero = Integer.valueOf(0);
                    while ( ! Thread.interrupted()) {
                        Integer value = map.get(zero);
                        if ( ! zero.equals(value)) {
                            System.out.println("get : ".concat(String.valueOf(value)));
                        }
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        };
        
        // ひたすらput
        Runnable putter = new Runnable() {
            public void run() {
                try {
                    long start = 0L;
                    long time = 0L;
                    for (int i=1; i<10000; i++) {
                        System.out.print("put start ");
                        start = System.nanoTime();
                        map.put(i, i);
                        time = System.nanoTime() - start;
                        System.out.println("put time : " + time + " value=" + i);
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }
        };
        
        map.put(0, 0); // キー0はあらかじめ入れておく
        
        Thread getterThread = new Thread(getter);
        Thread putterThread = new Thread(putter);
        getterThread.start();
        putterThread.start();
		
        System.in.read(); // 待つ
        getterThread.interrupt();
    }

デフォルトコンストラクタだとテーブルサイズ16、負荷係数0.75なのでテーブルサイズの変更が起きるのは、要素数1万以下だと12, 24, 48, 96, 192, 768, 1536, 3072, 6144(テーブルサイズが倍になったものの0.75倍)を超えたとき。キーが0スタートであることに注意してこの付近の出力結果を見てみると、

…
put start put time : 5029 value=11
put start put time : 7543 value=12
put start put time : 3352 value=13
…
put start put time : 3352 value=23
put start put time : 11454 value=24
get : null
put start put time : 3911 value=25
…
put start put time : 2794 value=47
put start get : null
put time : 14807 value=48
put start put time : 3352 value=49
…
put start put time : 2514 value=95
put start get : null
put time : 11733 value=96
put start put time : 3073 value=97
…
put start put time : 3073 value=191
put start get : null
put time : 33523 value=192
put start put time : 4191 value=193
…
put start put time : 3073 value=767
put start get : null
get : null
get : null
get : null
get : null
get : null
get : null
put time : 100292 value=768
put start put time : 2514 value=769
…

…
put start put time : 2235 value=3071
put start get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
put time : 332723 value=3072
put start put time : 2794 value=3073
…
put start put time : 2234 value=6143
put start get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
get : null
put time : 199187 value=6144
put start put time : 2514 value=6145
…

テーブルサイズが拡張するところでputの時間がドンと大きくなって、'put start'と'put time'の間でgetでキー0の値をとるとnullが返ってくることがある。