Java中List和Map排序的坑

问题起源

今天同事找我说一个问题，看一个报错，报错原因是：

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大，所以导致了乱序，所以也是同样的错误，第一次遇到这种数值返回造成的隐晦的错误。

Java中List和Map排序的坑