HashMapと無限ループとsynchronized - 谷本心 in せろ部屋

「HashMapのputとgetを同時に行うと、無限ループが発生する」という事は
Javaエンジニアな皆さんならご存知だと思います。

1. 無限ループの再現

まずは論より証拠、無限ループになることを確認してみましょう。
こんなテストコードを書けば、すぐに再現できます。

public void testHashMap_無限ループ() throws InterruptedException {
	final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	Runnable runnable = new Runnable() {
		public void run() {
			for (int i = 0; i < 1000000; i++) {
				int key = i % 10000;

				if (map.containsKey(key)) {
					map.remove(key);
				} else {
					map.put(key, i);
				}
			}
		}
	};

	Thread th1 = new Thread(runnable);
	Thread th2 = new Thread(runnable);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

私のCore2Duoのマシンでは、このコードで3回に1回ぐらいの確率で無限ループになります。
マシンスペックにより、ループ回数（1000000のところ）の桁を増減させてください。

なぜ無限ループが発生するのかを説明すると長くなりますし、
ググればいくらでも情報が出てくるので、ここでは割愛します。

2. 無限ループ問題の対策とパフォーマンス

無限ループに陥らないようにするためには、いくつかの対策があります。

Hashtableを使う。
Collections.synchronizedMapを使う。
Java1.5以降ならConcurrentHashMapを使う。

具体的には、こんな宣言になります。

final Map<Integer, Integer> map = new Hashtable<Integer, Integer>();
final Map<Integer, Integer> map = Collections.synchronizedMap(new HashMap<Integer, Integer>());
final Map<Integer, Integer> map = new ConcurrentHashMap<Integer, Integer>();

もちろん、自前でsynchronizedブロックを書いても構いません。

public void testHashMap_自前で同期化() throws InterruptedException {
	final Map<Integer, Integer> map = new HashMap<Integer, Integer>();

	Runnable run = new Runnable() {
		public void run() {
			for (int i = 0; i < 1000000; i++) {
				int key = i % 10000;
				synchronized (map) {
					if (map.containsKey(key)) {
						map.remove(key);
					} else {
						map.put(key, i);
					}
				}
			}
		}
	};

	Thread th1 = new Thread(run);
	Thread th2 = new Thread(run);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

では、それぞれの対策のパフォーマンスはどうでしょうか。
実際に計測してみました。
（Core2Duo P8400、Java1.5.0_17にて計測）

同期化処理なし : 688ms
ConcurrentHashMap : 1,282ms
Hashtable : 11,406ms
自前で同期化 : 13,047ms
synchronizedMap : 13,734ms

ConcurrentHashMapの性能の良さが際立っており、他より10倍ぐらい早くなりました。
他の対策はどれも同じ程度で、同期化処理なしの場合に比べ、20倍程度の時間が掛かります。

Java1.5以降であれば、間違いなくConcurrentHashMapを使うべきでしょう。
また、Java1.4以前でも、ConcurrentHashMapを含むjava.util.concurrentパッケージの
クラス群をバックポートしたものが公開されているため、これを使うべきでしょう。
http://backport-jsr166.sourceforge.net/index.php

どうしてもjava.util.concurrentを使えない場合、
安全さを重視するなら、Collections.synchronizedMapを使うのが良いでしょう。
自前のsynchronizedする方法では、抜けが発生する可能性があるためです。

また、HashtableよりもCollections.synchronizedMapを使った方が
「同期化に気をつけるために使っている」ことが明確に伝わるはず、というのが私の考えです。

3. Iterator問題

HashMapに関するもう一つ有名な問題として、
HashtableやsynchronizedMapはIteratorには対応しておらず、
要素数が変わった際に例外をスローする、というものがあります。
ちなみに、ConcurrentHashMapではIteratorを使っても問題は起きません。

これも具体的なコードで見ていきましょう。

public void testHashMap_Iterator問題() throws InterruptedException {
	final int loopCount = 1000000;
	final Map<Integer, Integer> map = Collections
	        .synchronizedMap(new HashMap<Integer, Integer>());

	Runnable run1 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				int key = i % 10000;
				if (map.containsKey(key)) {
					map.remove(key);
				} else {
					map.put(key, i);
				}
			}
		}
	};

	Runnable run2 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				for (Iterator<Entry<Integer, Integer>> it = map.entrySet()
				        .iterator(); it.hasNext();) {
					it.next();
				}
			}
		}
	};

	Thread th1 = new Thread(run1);
	Thread th2 = new Thread(run2);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

これを実行すれば、it.next()を実行している箇所で
java.util.ConcurrentModificationExceptionが発生します。

くどいようですが、ConcurrentHashMapを使っていれば
ConcurrentModificationExceptionは発生しません。

4. Iterator問題の対策とパフォーマンス。

では、ConcurrentHashMapを使えない状況では、どうすれば良いのでしょうか。
パッと思いつくのは、この2つでしょう。

Iteratorの外側で、synchronizedする。
Iterator#next部分を、synchronizedする。

実はこのうち、Iterator#nextの部分をsynchronizedするという対策は効果がありません。

public void testHashMap_Iteratorのnextを同期化() throws InterruptedException {
	final int loopCount = 1000000;
	final Map<Integer, Integer> map = new Hashtable<Integer, Integer>();

	Runnable run1 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				int key = i % 10000;
				synchronized (map) {
					if (map.containsKey(key)) {
						map.remove(key);
					} else {
						map.put(key, i);
					}
				}
			}
		}
	};

	Runnable run2 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				for (Iterator<Entry<Integer, Integer>> it = map.entrySet()
				        .iterator(); it.hasNext();) {
					synchronized (map) {
						it.next();
					}
				}
			}
		}
	};

	Thread th1 = new Thread(run1);
	Thread th2 = new Thread(run2);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

Hashtableを使ったうえでsynchronizedするなど、少し過剰に同期化していますが、
やはりこのようなコードを書いても、ConcurrentModificationExceptionが発生します。
iteratorを取得する部分を含めて、synchronizedする必要があるのです。

こんな風に記述します。

public void testHashMap_Iteratorを同期化() throws InterruptedException {
	final Map<Integer, Integer> map = new Hashtable<Integer, Integer>();
	final int loopCount = 1000000;

	Runnable run1 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				int key = i % 10000;
				if (map.containsKey(key)) {
					map.remove(key);
				} else {
					map.put(key, i);
				}
			}
		}
	};

	Runnable run2 = new Runnable() {
		public void run() {
			Object dummy = null;
			for (int i = 0; i < loopCount / 10; i++) {
				synchronized (map) {
					for (Iterator<Entry<Integer, Integer>> it = map
					        .entrySet().iterator(); it.hasNext();) {
						dummy = it.next();
					}
				}
			}
		}
	};

	Thread th1 = new Thread(run1);
	Thread th2 = new Thread(run2);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

ループ回数を多少いじっていますが、これは処理時間が過剰にならないようにするためです。
これなら、ConcurrentModificationExceptionは発生しません。

とは言え、iteratorの外側でsynchronizedしてしまうと、特にMapのサイズが大きく、
iteratorの中で行う処理（上の例で言うit.next()の部分）のコストが高い場合は
他の処理（上の例で言うrun1の処理）が、長い時間待たされてしまいます。

他に何か対策がないか、、、と考えて思いついたのが、

keySetやentrySetをtoArrayする箇所をsynronizedする。

という方法です。

具体的には、このようなコードになります。

public void testHashMap_entrySetを同期化() throws InterruptedException {
	final Map<Integer, Integer> map = new Hashtable<Integer, Integer>();
	final int loopCount = 1000000;

	Runnable run1 = new Runnable() {
		public void run() {
			for (int i = 0; i < loopCount; i++) {
				int key = i % 10000;
				if (map.containsKey(key)) {
					map.remove(key);
				} else {
					map.put(key, i);
				}
			}
		}
	};

	Runnable run2 = new Runnable() {
		public void run() {
			Object dummy = null;
			for (int i = 0; i < loopCount / 10; i++) {
				Object[] entries = null;
				synchronized (map) {
					entries = map.entrySet().toArray();
				}

				for (Object entry : entries) {
					// 必要に応じて、synchronized(map)を入れる。
					dummy = entry;
				}
			}
		}
	};

	Thread th1 = new Thread(run1);
	Thread th2 = new Thread(run2);

	th1.start();
	th2.start();

	th1.join();
	th2.join();
}

これなら、ConcurrentModificationExceptionが発生することもありませんし、
run2の処理の途中でも、run1は割り込んで処理をすることできます。

ただ、この方法は余計に配列を確保するため、メモリ消費量が大きいだけでなく
toArrayするためのコストも余計に掛かることに、注意してください。
特にentryを使った処理が十分に重い場合（たとえばDBアクセスなど）には有効だと言えるでしょう。

また、それぞれの対策のパフォーマンスも計測してみました。
（Core2Duo P8400、Java1.5.0_17にて計測）

ConcurrentHashMapを利用 : 640ms
entrySetの配列化を同期化 : 21,062ms
Iteratorの外側で同期化 : 28,812ms

これまたConcurrentHashMapが他より30倍以上も高速なことが分かります。
また、上のサンプルでは、entrySetを配列化した方が結果的に高速でした。

5. まとめ

ここまでをまとめておきましょう。

HashMapに複数スレッドからアクセスする場合には、同期化を行わないと、無限ループする可能性があるよ。
使えるなら、ぜひConcurrentHashMapを使おう！
- 無限ループも防げるよ。
- Iteratorを使っても問題が起きないよ。
- 自前でsynchronizedするより断然パフォーマンスが良いよ。
ConcurrentHashMapが使えないなら、Collections#synchronizedMapを使おう。
synchronizedMapを使っていも、Iteratorを取得する／使う箇所をsynchronizedで囲もう。
Iterator内で重い処理を行う場合は、keySetやentrySetを配列化することも検討しよう。

6. おまけ

余談ですが、
Mapのsynchronizedは、2つの観点で行うことがあります。

ひとつは、これまで述べてきた無限ループや、ConcurrentModificationExceptionを防ぐため、
もうひとつは、トランザクションのためです。

今回の話ではトランザクションについては、問題にしていないのですが、
たとえばこの処理を見てください。

if (map.containsKey(key)) {
	map.remove(key);
} else {
	map.put(key, i);
}

map.containsKey(key)の結果が出た直後に
別スレッドからmapのputやremoveが行われた場合に、
このスレッドでputやremoveすると（業務的に）問題が発生する可能性があります。

だから、たとえConcurrentHashMapを使っていたとしても、
この部分はまとめてsynchronized(map)で囲んでおくべきなのです。

DBで言うところの、行ロックやテーブルロックに相当するsynchronizedが必要だ、ということですね。
意外と、こちらの観点が抜けてバグに繋がることがあるので、要注意です。