読者です 読者をやめる 読者になる 読者になる

Webエンジニア susumuis の技術ブログ

このブログの内容は個人の見解であり、所属する組織の公式見解ではありません

TreeSetのComparatorではまったのでメモ(初心者向け)

今更感のある話題ですが、初心者=僕が、ドハマリして、いろいろ面白い現象に遭遇しました。
内容はいたって基本中の基本のため、仕事でプログラミングしている者としては恥ずかしい限りですが、後に同じようにハマる人がいたときのために、メモを残します。

やろうとしたこと:

もともとこんなコードがあって

set = new TreeSet();
for (DBの取得結果) {
  set.add(取得した値);
}

この後、setをつかって、UIを生成していたのだけど、順番が違うよって指摘を受けた。DBには、よくある、「表示順」のカラムがある。SQLならorder byで取れる。TreeSetの場合はCompatatorを渡せば良い。ということで、こんなHashMapをつくって

Map<String, Integer> idToSortOrderMap = new HashMap<String, Integer>();
for (DBの取得結果) {
  idToSortOrderMap.put(id, order);
}

みたいにして。こんなstatic内部クラスを作る

private static class MyComparator implements Comparator, Serializable {
	private HashMap<String, Integer> idToOrderMap;
	public MyComparator(HashMap<String, Integer> idToOrderMap) {
		this.idToOrderMap= idToOrderMap;
	}
	public int compare(String o1, String o2) {
		Integer i1 = idToOrderMap.get(o1);
		Integer i2 = idToOrderMap.get(o2);
		if (i1 == null) { return 1; }
		if (i2 == null) { return -1; }
		return i1 - i2;
	}
}

これで一見すると、表示順は正常で、あたいもちゃんと追加されているので、完了…そう思っていました。

問題発生

ところが、例えば

idToOrderMap.put("hoge", 1);
idToOrderMap.put("hoge2", 2);
idToOrderMap.put("fuga", 1);

のとき、

set.add("hoge");
set.add("hoge2");

System.out.println(set.contains("fuga")); // falseのはず

ところが、結果はtrueになってしまいます。

問題の原因

初歩的なことですが、Java APIリファレンスに、
http://java.sun.com/javase/ja/6/docs/ja/api/java/util/TreeSet.html

あるセットが Set インタフェースを正しく実装するには、明示的なコンパレータが提供されているかどうかにかかわらず、そのセットによって維持される順序付けが「equals との一貫性」のあるものでなければいけないことに注意してください。

http://java.sun.com/javase/ja/6/docs/ja/api/java/util/Comparator.html

たとえば、(a.equals(b) && c.compare(a, b) != 0) である 2 つの要素 a および b をコンパレータ c で空の TreeSet に追加すると仮定します。a と b はツリーセットの点から見て等価ではないため、2 番目の add オペレーションは、Set.add メソッドの仕様とは異なる場合でも、true を返し、ツリーセットのサイズは大きくなります。

と記述されています。

噛み砕いていうと「compareの結果が0と、equalsが同値でないと、TreeSetは異常な動きをするよ」というところです。

Effective Java

を持っている人は、Effective Javaの第2版 「項目12 Comparableの実装を検討する」に関連する記述があります。

はまりどころは、compareとequalsの一貫性は、必須ではないというところです。しかし、TreeSetやTreeMapのようにこの一貫性を要求する実装クラスがあるということです。

完成コード

上記クラスの修正版は以下のとおりです。

private static class MyComparator implements Comparator, Serializable {
	private HashMap<String, Integer> idToOrderMap;
	public MyComparator(HashMap<String, Integer> idToOrderMap) {
		this.idToOrderMap= idToOrderMap;
	}
	public int compare(String o1, String o2) {
		if (o1 == null) {
			return o2 == null ? 0 : -1;
		}
		Integer i1 = idToOrderMap.get(o1);
		Integer i2 = idToOrderMap.get(o2);
		if (i1 == null) {
			if (i2 != null) {
				return -1;
			}
			return o1.compareTo(o2);
		}
		if (i2 == null) {
			return 1;
		}
		if (i1.equals(i2)) {
			return o1.compareTo(o2);
		}
		return i1.compareTo(i2);
	}
}

2011/06/24 修正

ソースを修正しました。修正した箇所は、

if (i1 == i2) {

の箇所で、i1,i2がintではなく、Integerだったので、値の比較ではなく、オブジェクトの比較がされていました。equalsを使うべきでしたが、そうすると、nullの場合にヌルポになるので、上記の対応になります。やりたいことは最終行の

return i1.compareTo(i2);

なんですよね。Javaが冗長とか言われるのも、こういったNull対策があったりとかするところなんでしょうね……。

まあ、SQLでもこう言うのありますけどね。