java.util.Comparatorの比較判定は適当に書くと実行時エラーが出る(ことがある)

また実装をサボって時間を浪費したので書きました。

<問題>

<実行時エラー(RE)が発生した提出>

抜粋

Collections.sort(rowA, new Comparator<Map.Entry<Long,Long>>(){
  @Override
  public int compare(Map.Entry<Long,Long> e1, Map.Entry<Long,Long> e2){
    return (e1.getValue() == e2.getValue() ? 0 : e1.getValue() > e2.getValue() ? -1 : 1);
  }
});

上記のようにKeyに対して全く順序付けを行わずにcompareを実装すると、特定の入力値が入ってきた際に以下のように制約違反として扱われるようです。

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!

これらはなぜ発生するのでしょうか。

Collections.sort()は内部的にTimSort(マージソート系？)を用いているようで、ソート順が安定していないと、ソート途中で同値の要素が入れ替わってしまい(上記の場合getValue()の値が等しいが、getKey()の値が異なる物)、安定ソートでないとみなされ実行時エラーとして処理されるようです。

Collections.sort()の公式ドキュメントでも、

このソートは固定であることが保証されています。つまり、ソートを実行しても、同等の要素の順序は変わりません。

と書かれており、安定ソートであることが明記されています。(逆に言うと、独自の比較関数を使用してソートを行う際は安定ソートとして実装しなければならない)

docs.oracle.com

さて、Comparatorで比較関数を作成する際はcompare()をOverrideしますが、これらは推移的(大小関係を破綻させないようにする)であれば良く、必ずしもCollections.sort()の要件である安定ソートが保証されてなくとも許されます。

実装では、順序関係が推移的であることも保証されなければいけません。

docs.oracle.com

まとめると、実際にソートを実装する機能[Comparator.compare()]よりソートを行う機能[Collections.sort()]の制約の方が厳しいので、ソートを行った際に一部の入力値で実行時エラーが発生する形となります。

Javaで独自のComparatorを作成し、謎のREで落ちる際は上記の事象を疑ってみてください。