上周线上的一段排序的java代码出现了一个Comparison method violates its general contract
,在解决这个问题的途中学到了一些知识这里总结分享一下。
异常原因
这个排序导致的异常将会在java7以上的版本出现,所以如果你的JDK从6升级到了7或者8,那一定要小心此异常。
在java7的兼容列表中,就有对此排序不兼容的说明:
1 | Area: API: Utilities |
我从资料中查阅到java7开始引入了Timsort的排序算法。我之前一直以为大部分标准库的内置排序算法都是快速排序。现在才得知很多语言内部都使用Timsort排序。随后我在wiki百科上找到了这样一句话:
1 | It was implemented by Tim Peters in 2002 for use in the Python programming language. |
所以这个排序自然是以他命名的。
随后我又在网上找到了这样一张图排序比较的图:
可以发现,Timsort在表现上比QuickSort还要好。
这篇博客不去详细讨论Timsort的实现(看上去这个算法还挺复杂的),我可能会写另一篇博客单独讨论Timsort,简单来说Timsort结合了归并排序和插入排序。这个算法在实现过程中明确需要:严格的单调递增或者递减来保证算法的稳定性。
- sgn(compare(x, y)) == -sgn(compare(y, x))
- ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0
- compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z
看上去很像离散数学课中学习的集合的对称性,传递性的关系。
所以异常的原因是因为排序算法不够严谨导致的,实际上业务上的代码经常不如纯技术上的严谨。比如对于这样一个排序条件。按照:
1 | 价格进行排序,如果价格相等则起飞时间靠前的先排。 |
所以这个判断函数的问题是:
1 | public compareFlightPrice(flightPrice o1, flightPrice o2){ |
这个函数有明显的不稳定性,比如对于compareFlightPrice(a, b)
,如果ab都是非共享非经停,那么这个时候a<b
,但如果调用compareFlightPrice(b, a)
,这个时候b<a
,所以必须判断a是非共享非经停且b不是非共享非经停,才能让a排在前面。
当然除了改比较函数,还有一个解决方式是:给jvm添加启动参数。
-Djava.util.Arrays.useLegacyMergeSort=true
还需要注意的是,并不一定你的比较函数不符合上面的严谨定义,就一定会稳定浮现此异常,实际上我们在生产环境出现此异常的概率很小,毕竟java并不会蠢到先去把整个数组都校验一遍再去排序,实际上它是在排序的过程中才发现你不符合此条件的。所以有可能某种集合顺序让你刚好绕过了此判断。