文档章节

JDK1.6和JDK1.7中,Collections.sort的区别,

tsmyk0715
 tsmyk0715
发布于 06/23 16:04
字数 1316
阅读 27
收藏 0
JDK

背景

最近,项目正在集成测试阶段,项目在服务器上运行了一段时间,点击表格的列进行排序的时候,有的列排序正常,有的列在排序的时候,在后台会抛出如下异常,查询到不到数据,而且在另外一台服务器上是可以排序的, 就是说该问题是偶现的;

java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeLo(TimSort.java:747)
	at java.util.TimSort.mergeAt(TimSort.java:483)
	at java.util.TimSort.mergeCollapse(TimSort.java:410)
	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)

google之后,发现有很多的人也遇到了这个问题,原因就是 JDK 升级的问题,也才想起来最近项目也升级了JDK, 从 JDK1.6 改为JDK1.7了,

原因

在 JDK1.6 和 JDK1.7 的 Collections.sort(List, Comparator) 方法中,底层的实现变了,在使用Comparator比较器进行比较的时候,可能会返回-1,1和0三种结果,但在平时的时候,往往会忽略0,也就是两个元素相等的情况或者NULL的情况,如果在调用Comparator比较的时候,只会返回-1或1,则在 JDK1.6的时候,可以正常运行,在升级到 JDK1.7之后,有可能会运行失败,会抛出异常:java.lang.IllegalArgumentException: Comparison method violates its general contract!,

在项目的对应代码中也发现了如下代码:

    Collections.sort(aObjectList, new Comparator(){
        public int compare(Object o1, Object o2)
        {
			......
            int reverse = 1;
            if ("desc".equalsIgnoreCase(sortType)) {
              reverse = -reverse;
            }
            ......
            double result = filedValue1.doubleValue() - filedValue2.doubleValue();
            int returnValue = 0;
            if (result > 0.0D) {
                returnValue = 1;
            } else if (result < 0.0D) {
                returnValue = -1;
            }
            return returnValue * reverse;
            ......
		}
	}

该代码也只会返回 -1 或 1,没有返回 0  的情况,如果两个相等的时候,在 JDK1.7 环境中运行就会出现上述异常了。

JDK1.6 Collections.sort(List, Comparator)方法的实现:

    public static <T> void sort(List<T> list, Comparator<? super T> c) {
	    Object[] a = list.toArray();
	    Arrays.sort(a, (Comparator)c);
	    ListIterator i = list.listIterator();
	    for (int j=0; j<a.length; j++) {
	        i.next();
	        i.set(a[j]);
	    }
    }
    
    public static <T> void sort(T[] a, Comparator<? super T> c) {
	    T[] aux = (T[])a.clone();
        if (c==null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

可以看到使用的是归并排序mertgeSort进行排序,

JDK1.7 Collections.sort(List, Comparator)方法的实现:

    public static <T> void sort(List<T> list, Comparator<? super T> c) {
	    Object[] a = list.toArray();
	    Arrays.sort(a, (Comparator)c);
	    ListIterator i = list.listIterator();
	    for (int j=0; j<a.length; j++) {
	        i.next();
	        i.set(a[j]);
	    }
    }
 
    // Arrays.sort(a, c);
    public static <T> void sort(T[] a, Comparator<? super T> c) {
        if(LegacyMergeSort.userRequested){
	        legacyMergeSort(a,c)
        }else{
	        TimSort.sort(a,c)
        }
    |
    
    public static <T> void legacyMergeSort(T[] a, Comparator<? super T> c) {
	    T[] aux = (T[])a.clone();
        if (c==null)
            mergeSort(aux, a, 0, a.length, 0);
        else
            mergeSort(aux, a, 0, a.length, 0, c);
    }

可以看到它会用 TimSort.sort()方法进行排序,且在 JDK1.7后默认的排序方法。

解决方法

既然在 sort()方法中使用 LegacyMergeSort.userRequested 参数来控制使用 mergeSort排序算法还是使用 TimSort 排序算法,那么只要 LegacyMergeSort.userRequested 为true就会使用mergeSort算法,就会兼容 JDK1.6 的Collections.sort() 方法了,好在 JVM 提供了一个参数来控制:

-Djava.util.Arrays.useLegacyMergeSort=true

所在就在出问题的那台服务器上的虚拟机中添加了该参数,再进行排序的时候,就可以正常排序了,不会再抛出该异常了。

接下来在看一下 LegacyMergeSort.userRequested 是怎么获取的:

    static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

可以看到也是根据 java.util.Arrays.useLegacyMergeSort 的值来控制的,所以按理说也可以通过设置该环境变量也实现同样的效果,但是我通过该方法并没有成功,最终在用添加虚拟机参数的方式进行解决。

System.setProperty("java.util.Arrays.useLegacyMergeSort", true)

 

以上两种方法只能是用来规避异常,让代码正常运行,是一种规避手段,而正确的做法应该是在写代码的过程中,在使用Collections.sort(List, Comparator)来排序的时候,尽量考虑周全,不要漏掉 0 的情况:

		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				if (flag) 
				{
					return -1;
				}
				else if(flag) 
				{
					return 1;
				}
				else
				{
					return 0;
				}
			}
		});

或者直接使用 compareTo 方法进行比较:

		Collections.sort(list, new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o1.compareTo(o2);
			}
		});

题外话:TimSort.sort

在 JDK 的源码中 Collections.sort(List, Comparator)方法底层就使用的是归并算法来进行排序的,而在 JDK1.7后,就会使用 TimSort 来进行排序了,而TimSort是归并排序的一种变种,在大部分情况下,TimSort算法的效率较高,且它是稳定,因为在大部分情况下,要排序的集合都是部分有序的,完全无序的集合很少出现,TimSort 就抓住这个规律而对归并排序进行优化的。

TimSort.sort的基本思想:

在要排序的集合中,把部分有序的那些元素找出来,这些部分有序的元素姑且称为一个区域,最终这个集合会被划分为若干个区域,之后把这些区域压入栈中,在栈中对这些区域按照一定的规则进行合并。

具体参考:维基百科

 

© 著作权归作者所有

共有 人打赏支持
tsmyk0715
粉丝 21
博文 43
码字总数 98538
作品 0
成都
程序员
JDK7-Collections.sort()报Comparison method violates its general contract异常

记录在 JDK7 下使用 Collections.sort() 排序偶发的一个异常,以前在 JDK1.6 下面没有这个问题: Comparison method violates its general contract 发生问题的代码段: 一个很简单的排序,在...

山哥
2016/09/12
119
0
java 关于string类的intern方法

0.引言 什么都先不说,先看下面这个引入的例子: [java] view plain copy String str1 = new String("SEU")+ new String("Calvin"); System.out.println(str1.intern() == str1); System.ou......

hgqxjj
2017/12/21
0
0
jdk1.6 1.7 list扩容的区别

jdk1.6 public void ensureCapacity(int minCapacity) { modCount++; int oldCapacity = elementData.length; if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCa......

小艺术家被占用了
2016/08/16
19
0
java项目发布到sae上遇到的问题汇总

写在最前面:sae新浪云相比交bae还是有诸多限制的。比如jdk版本,对java许多框架支持不够,但并不影响其使用。现就本人上传到sae的项目遇到的问题进行汇总分析。 问题1: 查看日志后主要报错...

传奇再现
2014/05/07
0
0
JDK7和JDK6中substring()的不同

String substring(int beginIndex, int endIndex) 返回原字符串的子字符串这方法,只要是稍微了解点java的人都知道,就像知道1+1==2一样简单。不过其中的猫腻很少有人关注,就像基本没人问1...

浪子_仗剑走天涯
2013/11/21
0
9

没有更多内容

加载失败,请刷新页面

加载更多

实战讲解高并发和秒杀抢购系统设计

互联网特别是电商平台,阿里双11秒杀、还有12306春运抢票、以及平时各种节假日抢购活动等,都是典型的高并发场景。 这类场景最大的特征就是活动周期短,瞬间流量大(高并发),大量的人短期涌...

xtof
22分钟前
0
0
代码质量管理平台-sonarqube

在工作中,往往开发的时候会不怎么注重代码质量的人很多,存在着很多的漏洞和隐患等问题,sonarqube可以进行代码质量的审核,而且十分的残酷。。。。。接下来我们说下怎么安装 进入官网下载:...

落叶清风
25分钟前
4
0
在Ubuntu安装和配置Sphinx

Ubuntu系统默认是配置有sphinx的,先检查一下,别多此一举。。。。。 在开始本指南之前,您需要: 一个Ubuntu 16.04服务器。 sudo的一个非root用户,您可以通过以下设置本教程 。 安装在服务...

阿锋zxf
34分钟前
0
0
Qt编写输入法V2018超级终结版

对于qt嵌入式linux开发人员来说,输入法一直是个鸡肋问题,要么不支持实体键盘同步,要么不能汉字输入,要么不支持网页输入等,这几年通过陆续接触大量的各种输入法应用场景客户,得到真实需...

飞扬青云
45分钟前
1
0
TypeScript基础入门之高级类型的多态的 this类型

转发 TypeScript基础入门之高级类型的多态的 this类型 高级类型 多态的this类型 多态的this类型表示的是某个包含类或接口的子类型。 这被称做F-bounded多态性。 它能很容易的表现连贯接口间的...

durban
51分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部