首页 > 代码库 > Comparison method violates its general contract!

Comparison method violates its general contract!

    今天一个群里哥们儿碰到一个异常,抛到群里求解答,他的代码如下图: 技术分享

抛出的异常信息为:

Java代码 技术分享 技术分享
  1. java.lang.IllegalArgumentException: Comparison method violates its general contract!  
  2. at java.util.TimSort.mergeHi(TimSort.java:868)  
  3. at java.util.TimSort.mergeAt(TimSort.java:485)  
  4. at java.util.TimSort.mergeCollapse(TimSort.java:408)  
  5. at java.util.TimSort.sort(TimSort.java:214)  
  6. at java.util.TimSort.sort(TimSort.java:173)  
  7. at java.util.Arrays.sort(Arrays.java:659)  
  8. at java.util.Collections.sort(Collections.java:217)  
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)

   我说是compare方法实现的问题,他死活跟我掰,说我之前代码还好好的啊。没办法,我只好根据异常信息提示去翻JDK源码,异常里提示at java.util.TimSort.mergeHi(TimSort.java:868)即TimSort类的mergeHi方法抛出的。于是我不断Google,找到了这篇帖子why does my compare method throw exception — Comparison method violates its general contract》,根据他们的提示,我大概了解了compare方法需要返回1,-1,0即你的返回值要符合约定。

    于是我又按照异常提示看了Collections的sort方法源码,如图: 技术分享  继续跟踪Arrays类的sort方法: 技术分享  看到这里我基本就豁然开朗了,因为抛异常的地方是在TimSort类里,说明实际走的是else分支,所以有了第一种解决方法,添加-Djava.util.Arrays.useLegacyMergeSort=true这个JVM参数,其实要真正解决这个问题,要符合规范的实现compare方法,因为他写的代码里没有考虑对象o1和对象o2为Null的情况,即当o1与o2都为null时两者大小如何判定呢,当o1为null但o2不为null时两者大小又如何判定了呢,同理当o2为null但o1不为null时两者大小又如何判定呢又不得而知,或许你又会说,我这两个对象不可能为null,但那是你认为,JVM不知道,它只要求你的逻辑必须严谨,严格考虑各种情况下两者大小的判定原则。所以正确写法应该是:

Java代码 技术分享 技术分享
  1. if(o1 == null && o2 == null) {  
  2.     return 0;  
  3. }  
  4. if(o1 == null) {  
  5.     return -1;  
  6. }  
  7. if(o2 == null) {  
  8.     return 1;  
  9. }  
  10. if(o1.getCreateTime() > o2.getCreateTime()) {  
  11.     return 1;  
  12. }  
  13. if(o2.getCreateTime() > o1.getCreateTime()) {  
  14.     return -1;  
  15. }  
  16. return 0;  
if(o1 == null && o2 == null) {	return 0;}if(o1 == null) {	return -1;}if(o2 == null) {	return 1;}if(o1.getCreateTime() > o2.getCreateTime()) {	return 1;}if(o2.getCreateTime() > o1.getCreateTime()) {	return -1;}return 0;

  

 

异常信息

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)...

 

原因

JDK7中的Collections.Sort方法实现中,如果两个值是相等的,那么compare方法需要返回0,否则 可能 会在排序时抛错,而JDK6是没有这个限制的。

if (len2 == 0) {    throw new IllegalArgumentException("Comparison method violates its general contract!");}

 

 在 JDK7 版本以上,Comparator 要满足自反性,传递性,对称性,不然 Arrays.sort,

Collections.sort 会报 IllegalArgumentException 异常。

说明:

1) 自反性:x,y 的比较结果和 y,x 的比较结果相反。

2) 传递性:x>y,y>z,则 x>z。

3) 对称性:x=y,则 x,z 比较结果和 y,z 比较结果相同。

反例:下例中没有处理相等的情况,实际使用中可能会出现异常:

new Comparator<Student>() {    @Override    public int compare(Student o1, Student o2) {        return o1.getId() > o2.getId() ? 1 : -1;    }} 

 

背景

16号为了统一线上服务器运行环境,将两台服务器的Tomcat6+JDK6升级到Tomcat7+JDK7,本以为很简单的事情,升级后自己验证也没问题,没想到却悲剧了。升级后,过了半小时运营就找过来反馈问题,部分角色无法登陆系统,由于异常日志没有输出,没有找到问题,无奈回滚。今天我们就来说说JDK6升级到JDK7会遇到的坑。本文为了方便搜索,就直接以异常信息作为文章标题了。

复现

回滚后,到beta环境按照线上的权限配置,复现该问题,加上了error日志输出,输出了文章标题的异常,这个异常是在类似如下代码中抛出的:

[java] view plain copy print?
  1. Collections.sort(list, new Comparator<Integer>() {  
  2.     @Override  
  3.     public int compare(Integer o1, Integer o2) {  
  4.         return o1 > o2 ? 1 : -1;// 错误的方式  
  5.     }  
  6. });  
Collections.sort(list, new Comparator<Integer>() {	@Override	public int compare(Integer o1, Integer o2) {		return o1 > o2 ? 1 : -1;// 错误的方式	}});

解决方案

 

先说如何解决,解决方式有两种。

修改代码

上面代码写的本身就有问题,第4行没有考虑o1 == o2的情况,再者说我们不需要自己去比较,修改为如下代码即可:

[java] view plain copy print?
  1. Collections.sort(list, new Comparator<Integer>() {  
  2.     @Override  
  3.     public int compare(Integer o1, Integer o2) {  
  4.         // return o1 > o2 ? 1 : -1;  
  5.         return o1.compareTo(o2);// 正确的方式  
  6.     }  
  7. });  
Collections.sort(list, new Comparator<Integer>() {	@Override	public int compare(Integer o1, Integer o2) {		// return o1 > o2 ? 1 : -1;		return o1.compareTo(o2);// 正确的方式	}});

不修改代码

 

那么问题来了。为什么上面代码在JDK6中运行无问题,而在JDK7中却会抛异常呢?这是因为JDK7底层的排序算法换了,如果要继续使用JDK6的排序算法,可以在JVM的启动参数中加入如下参数:

[plain] view plain copy print?
  1. -Djava.util.Arrays.useLegacyMergeSort=true  
-Djava.util.Arrays.useLegacyMergeSort=true

这样就会照旧使用JDK6的排序算法,在不能修改代码的情况下,解决这个兼容的问题。

 

分析

在我以前的认知中,高版本的JDK是可以兼容之前的代码的,与同事讨论了一番另加搜索了一番,事实证明,JDK6到JDK7确实存在兼容问题(不兼容列表)。在不兼容列表中我们可以找到关于Collections.sort的不兼容说明,如下:

[plain] view plain copy print?
  1. Area: API: Utilities  
  2. Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException  
  3. Description: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced.   
  4. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract.   
  5. The previous implementation silently ignored such a situation.  
  6. If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort,   
  7. to restore previous mergesort behavior.  
  8. Nature of Incompatibility: behavioral  
  9. RFE: 6804124  
Area: API: UtilitiesSynopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentExceptionDescription: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation.If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.Nature of Incompatibility: behavioralRFE: 6804124

 

描述的意思是说,java.util.Arrays.sort(java.util.Collections.sort调用的也是此方法)方法中的排序算法在JDK7中已经被替换了。如果违法了比较的约束新的排序算法也许会抛出llegalArgumentException异常。JDK6中的实现则忽略了这种情况。那么比较的约束是什么呢?看这里,大体如下:

技术分享

 

 

  • 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
再回过头来看我们开篇有问题的实现:
[java] view plain copy print?
  1. return x > y ? 1 : -1;  
return x > y ? 1 : -1;
当x == y时,sgn(compare(x, y))  = -1,-sgn(compare(y, x)) = 1,这违背了sgn(compare(x, y)) == -sgn(compare(y, x))约束,所以在JDK7中抛出了本文标题的异常。

 

结论

 

那么现在是否可以盖棺定论了,按照上面的分析来看,使用这种比较方式(return x > y ? 1 : -1;),只要集合或数组中有相同的元素,就会抛出本文标题的异常。实则不然,什么情况下抛出异常,还取决于JDK7底层排序算法的实现,也就是大名鼎鼎的TimSort。后面文章会分析TimSort。本文给出一个会引发该异常的Case,以便有心人共同研究,如下:
[java] view plain copy print?
  1. Integer[] array =   
  2. {0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,   
  3. 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 30, 0, 3};  
Integer[] array = {0, 0, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 2, 1, 0, 0, 0, 2, 30, 0, 3};
      (完)

Comparison method violates its general contract!