やろうとしたこと：

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

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でもこう言うのありますけどね。