问题起源
今天同事找我说一个问题，看一个报错，报错原因是：
Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
at java.util.TimSort.mergeLo(TimSort.java:777)
at java.util.TimSort.mergeAt(TimSort.java:514)
at java.util.TimSort.mergeCollapse(TimSort.java:441)
at java.util.TimSort.sort(TimSort.java:245)
at java.util.Arrays.sort(Arrays.java:1512)
at java.util.ArrayList.sort(ArrayList.java:1454)
at java.util.Collections.sort(Collections.java:175)
at com.asiainfo.miaohq.test.Test1.main(Test1.java:18)
很容易写个小的验证程序：
public class SortTest {
/**
* @Title: main
* @Description:
* @param args
*/
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 65; i++) {
list.add(i);
list.add(null);
}
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int a = 0;
if (o1 == null)
a = 1;
else if (o2 == null)
a = -1;
else
a = o1.compareTo(o2);
return a;
}
});
for (Integer i : list) {
System.out.println(i);
}
}
}
说明：如果是循环次数不是65更少的数字，偶尔报错，偶尔
不报错，实际原因和算法有关系，里面进行分组排序然后合并（只是猜测）。
查找原因
去看了下异常栈，里面是个复杂的排序算法，也没耐心去查下去了，搜了下，大概的意思是排序不符合逻辑规则。
具体例子：
假设a>b b>c 那么a>c一定成立的。
目前上面的例子存在 问题是如果o1为null，则在任何情况下，都是null>o2,
但是其实存在o2==null的情况，这就导致了null> null 的逻辑错误。
解决办法
1 添加属性设置
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");
2 判断null情况：
public class SortTest {
/**
* @Title: main
* @Description:
* @param args
*/
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 65; i++) {
list.add(i);
list.add(null);
}
Collections.sort(list, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
int a = 0;
if(o1 == null && o2== null)
return 0;
if (o1 == null)
a = 1;
else if (o2 == null)
a = -1;
else
a = o1.compareTo(o2);
return a;
}
});
for (Integer i : list) {
System.out.println(i);
}
}
}
国外例子
下面代码，你可以看出为什么也会报这个错误吗？
public int compare(Node o1, Node o2)
{
HashMap<Integer,Integer> childMap = orderMap.get(parentID);
if(childMap != null && childMap.containsKey(o1.getID()) &&
childMap.containsKey(o2.getID()))
{
int order1 = childMap.get(o1.getID());
int order2 = childMap.get(o2.getID());
if(order1<order2)
return -1;
else if(order1>order2)
return 1;
else
return 0;
}
else
return 0;
}
外国人解释：
比较方法是不传递的。举个例子如果 A==B 和B==C，那么
A一定等于C。
现在看这个例子的情况：
假设A、B、C三个对象情况。假设包含情况是这样的：
childMap.containsKey(A.getID()) returns true
childMap.containsKey(B.getID()) returns false
childMap.containsKey(C.getID()) returns true
当A和B比较的时候，外面的if条件不满足，所以返回结果是0，意味着A==B
当B和C比较的时候，外面的if条件仍然不满足，所以结果也是0，意味着B==C。
假设A和C比较的时候很有可能返回1或-1 ，这就造成的结果是A!=C.
这就违反了传递规则。
所以不能在else里面直接返回0，需要根据情况判断。
额外的坑
后面同事又测试发现一个问题，代码片段如下：
public class FFileTimeCompartor implements Comparator<Map.Entry<String, FTPFile>> {
@Override
public int compare(Entry<String, FTPFile> map1, Entry<String, FTPFile> map2) {
if (map1 == null && map2 == null) {
return 0;
}
if (map1 == null)
return 1;
if (map2 == null)
return -1;
FTPFile file1 = map1.getValue();
FTPFile file2 = map2.getValue();
long res = file1.getTimestamp().getTimeInMillis() - file2.getTimestamp().getTimeInMillis();
return (int) (res == 0 ? file1.getName().compareTo(file2.getName()) : res);
}
}
仍然是报上面的错误，后面终于发现是file1.getTimestamp().getTimeInMillis() 比较是long类型，那么相差的差值在转成int的时候，由于可能被int大，所以导致了乱序，所以也是同样的错误，第一次遇到这种数值返回造成的隐晦的错误。
