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