Comparison method violates its general contract!

   今天一个群里哥们儿碰到一个异常,抛到群里求解答,他的代码如下图: Comparison method violates its general contract!

抛出的异常信息为:

  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方法源码,如图: Comparison method violates its general contract!  继续跟踪Arrays类的sort方法: Comparison method violates its general contract!  看到这里我基本就豁然开朗了,因为抛异常的地方是在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不知道,它只要求你的逻辑必须严谨,严格考虑各种情况下两者大小的判定原则。所以正确写法应该是:

  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;

  

 

异常信息

Comparison method violates its general contract!
Comparison method violates its general contract!
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)
...
Comparison method violates its general contract!
Comparison method violates its general contract!

 

原因

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 比较结果相同。

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

Comparison method violates its general contract!
Comparison method violates its general contract!
new Comparator<Student>() {
    @Override
    public int compare(Student o1, Student o2) {
        return o1.getId() > o2.getId() ? 1 : -1;
    }
} 
Comparison method violates its general contract!
Comparison method violates its general contract!

 

背景

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

复现

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

  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的情况,再者说我们不需要自己去比较,修改为如下代码即可:

  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的启动参数中加入如下参数:

  1. -Djava.util.Arrays.useLegacyMergeSort=true  
-Djava.util.Arrays.useLegacyMergeSort=true

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

 

分析

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

  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: Utilities
Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException
Description: 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: behavioral
RFE: 6804124

 

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

Comparison method violates its general contract!

 

 

  • 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. 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,以便有心人共同研究,如下:
  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};
      (完)

 

原文。https://www.cnblogs.com/firstdream/p/7204067.html

 
 
 
关键点 就是存在多个相同的,违反了约束
 
Comparison method violates its general contract!

 

 Comparison method violates its general contract!

 

 

 

Comparison method violates its general contract!

 

 

Comparison method violates its general contract!

 

 

Comparison method violates its general contract!

上一篇:小林求职记(四)不会吧不会吧,面试还真会问这些呀


下一篇:一组精美的网页设计标志