前一阵遇到了一个使用Collections.sort()时报异常的问题,跟小伙伴@zhuidawugui 一起排查了一下,发现问题的原因是JDK7的排序实现改为了TimSort,之后我们又进一步研究了一下这个神奇的算法。
先说一下为什么要研究这个异常,前几天线上服务器发现日志里有偶发的异常:
123456789 | java.lang.IllegalArgumentException: Comparison method violates its general contract! at java.util.TimSort.mergeHi(TimSort.java:868) at java.util.TimSort.mergeAt(TimSort.java:485) at java.util.TimSort.mergeCollapse(TimSort.java:408)at java.util.TimSort.sort(TimSort.java:214) at java.util.TimSort.sort(TimSort.java:173) at java.util.Arrays.sort(Arrays.java:659) at java.util.Collections.sort(Collections.java:217)... |
---|
出错部分的代码如下:
1234567 | List<Integer> list = getUserIds();Collections.sort(list, new Comparator<Integer>() { @Override public int compare(Integer o1, Integer o2) { return o1>o2?1:-1; }}); |
---|
google了一下:JDK7中的Collections.Sort方法实现中,如果两个值是相等的,那么compare方法需要返回0,否则可能会在排序时抛错,而JDK6是没有这个限制的。
这个问题在测试时并没有出现,线上也只是小概率复现,如何稳定的复现这个问题?看了一下源代码,抛出异常的那段源代码让人根本摸不着头脑:
123 | if (len2 == 0) { throw new IllegalArgumentException("Comparison method violates its general contract!");} |
---|
为了解开这个困惑,我们对java实现的Timsort代码做了一些分析。
TimSort排序是一种优化的归并排序,它将归并排序(merge sort) 与插入排序(insertion sort) 结合,并进行了一些优化。对于已经部分排序的数组,时间复杂度远低于 O(n log(n)),最好可达 O(n),对于随机排序的数组,时间复杂度为 O(nlog(n)),平均时间复杂度 O(nlog(n))。
它的整体思路是这样的:
这篇文章就不再过多的阐述Timsort整体思路了,有兴趣可以参考[译]理解timsort, 第一部分:适应性归并排序(Adaptive Mergesort)
重点说一下Timsort中的归并。归并过程相对普通的归并排序做了一定的优化,假如有如下的一段数组:
假设这里实现的compare(obj o1,obj o2)如下:
123 | public int compare(Integer o1, Integer o2) { return o1>o2?1:-1;} |
---|
注意!
在第6步查找的时候,有A[base1+1]<tmp[0]
(tmp[0]的值等于没有合并之前的B[base2])。
而第2步时,有B[base2]<A[base1]
而最初生成RunTask的时候,有A[base1]<=A[base1+1]
连起来就是B[base2]<A[base1]<=A[base1+1]<B[base2]
,这显然是有问题的。
所以,当len2==0时,会抛出“Comparison method violates its general contract”异常。问题复现的条件是触发“胜利N次”的优化,并且存在类似(A[base1]==A[base1+x])&&(A[base1+x]==B[base2])的数据排列。这里应该还有几种另外的触发条件,精力有限,就不再深究了。
TimSort in Java 7 OpenJDK 源代码阅读之 TimSort