java中排序报：Comparison method violates its general contract异常的解决

前言

上周线上的一段排序的java代码出现了一个Comparison method violates its general contract，在解决这个问题的途中学到了一些知识这里总结分享一下。

异常原因

这个排序导致的异常将会在java7以上的版本出现，所以如果你的JDK从6升级到了7或者8，那一定要小心此异常。

在java7的兼容列表中，就有对此排序不兼容的说明：

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

我从资料中查阅到java7开始引入了Timsort的排序算法。我之前一直以为大部分标准库的内置排序算法都是快速排序。现在才得知很多语言内部都使用Timsort排序。随后我在wiki百科上找到了这样一句话：

t 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

看上去很像离散数学课中学习的集合的对称性，传递性的关系。

所以异常的原因是因为排序算法不够严谨导致的，实际上业务上的代码经常不如纯技术上的严谨。比如对于这样一个算法：

选出航班中的最低价

那如果两个相等低价同时存在，按照寻找最低价的逻辑如果这么写：

if (thisPrice < lowPrice){
 lowPrice = thisPrice;
}

那低价这个位置就是“先到先得”了。

但如果这么实现:

if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}

那后面的低价就会覆盖前面的，变成了“后来者居上”。编程中经常遇到先到先得和后来者居上这两个问题。

所以对于上面那个需要提供严谨的判断大小比较函数实现。所以如果是这样的：

return x > y ? 1 : -1;

那么就不符合此条件。

不过我们逻辑要比这个复杂，其实是这样一个排序条件。按照：

  • 价格进行排序，如果价格相等则起飞时间靠前的先排。
  • 如果起飞时间也相等，就会按照：
  • 非共享非经停>非经停>非共享>经停的属性进行优先级选择，如果这些属性都全部相等，才只能算是相等了。

所以这个判断函数的问题是：

public compareFlightPrice(flightPrice o1, flightPrice o2){
 // 非经停非共享
 if (o1.getStopNumber() == 0 && !o1.isShare()) {
 return -1;
 } else if (o2.getStopNumber() == 0 && !o2.isShare()) {
 return 1;
 } else {
 if (o1.getStopNumber() == 0) {
  return -1;
 } else if (o2.getStopNumber() == 0) {
  return 1;
 } else {
  if (!o1.isShare()) {
  return -1;
  } else if (!o2.isShare()) {
  return 1;
  } else {
  if (o1.getStopNumber() > 0) {
   return -1;
  } else if (o2.getStopNumber() > 0) {
   return 1;
  } else {
   return 0;
  }
  }
 }
 }
}

这个函数有明显的先到先得的问题，比如对于compareFlightPrice(a, b) ，如果ab都是非共享非经停，那么这个就会把a排到前面，但如果调用compareFlightPrice(b, a) ，b又会排到前面，所以必须判断a是非共享非经停且b不是非共享非经停，才能让a排在前面。

当然除了改比较函数，还有一个解决方式是：给jvm添加启动参数。

-Djava.util.Arrays.useLegacyMergeSort=true

还需要注意的是，并不一定你的集合中存在相等的元素，并且比较函数不符合上面的严谨定义，就一定会稳定浮现此异常，实际上我们在生产环境出现此异常的概率很小，毕竟java并不会蠢到先去把整个数组都校验一遍，实际上它是在排序的过程中发现你不符合此条件的。所以有可能某种集合顺序让你刚好绕过了此判断。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作能带来一定的帮助，如果有疑问大家可以留言交流，谢谢大家对我们的支持。

赞 (0)

相关推荐

  • Java中内存异常StackOverflowError与OutOfMemoryError详解

    Java中内存异常StackOverflowError与OutOfMemoryError详解

     Java中内存异常StackOverflowError与OutOfMemoryError详解 使用Java开发,经常回遇到内存异常的情况,而StackOverflowError和OutOfMemoryError便是最常遇见的错误. 首先,看看这两种错误的解释: 如果当前线程请求的栈深度大于虚拟机所允许的最大深度,将抛出StackOverflowError异常. 如果虚拟机在扩展栈时无法申请到足够的内存空间,则抛出OutOfMemoryError异常. 这里把异常分为两种情况,但是存在一些相互重

  • Java数组越界问题实例解析

    Java中数组初始化和OC其实是一样的,分为动态初始化和静态初始化, 动态初始化:指定长度,由系统给出初始化值 静态初始化:给出初始化值,由系统给出长度 在我们使用数组时最容易出现的就是数组越界问题,好了,这里有个简单的例子 int [][] array = {{1,2,3},{1,4}}; System.out.println(array[1][2]); 这是一个二维数组,很明显,数组越界了,控制台中会打印如下信息: Exception in thread "main" java.l

  • Java异常处理运行时异常（RuntimeException）详解及实例

      Java异常处理运行时异常(RuntimeException)详解及实例 RuntimeException RunntimeException的子类: ClassCastException 多态中,可以使用Instanceof 判断,进行规避 ArithmeticException 进行if判断,如果除数为0,进行return NullPointerException 进行if判断,是否为null ArrayIndexOutOfBoundsException 使用数组length属性,避免越

  • java中的connection reset 异常处理分析

    在Java中常看见的几个connection rest exception, Broken pipe, Connection reset,Connection reset by peer Socked reset case Linux中会有2个常见的sock reset 情况下的错误代码 ECONNRESET 该错误被描述为"connection reset by peer",即"对方复位连接",这种情况一般发生在服务进程较客户进程提前终止.当服务进程终止时会向客户

  • 利用Java异常机制实现模拟借书系统

    利用Java异常机制实现模拟借书系统

    本文介绍的是利用java语言实现一个控制台版的模拟借书系统,在开始本文的正式内容之前,我们先来了解一下Java异常机制. 什么是异常? 异常,不正常也.Exception是Exception event的缩写,因此异常是一个事件,该事件发生在程序运行时. 异常会影响程序的连续性,使程序中断.在Java中,一切皆对象,所以要定义异常,也需要使用对象.异常对象里 封装了异常类型和程序发生异常时的状态. 我们经常说的抛出异常就是创建异常对象,并提交给运行系统. 异常捕获机制与try-catch 当异常

  • java.net.MalformedURLException异常的解决方法

    java.net.MalformedURLException at java.net.URL.<init>(URL.java:619) at java.net.URL.<init>(URL.java:482) at java.net.URL.<init>(URL.java:431) 代码中URL url = new URL(someUrl);这一行出现java.net.MalformedURLException异常 解决方法是,对someUrl中的参数名和参数值都URL

  • java中排序报：Comparison method violates its general contract异常的解决

    java中排序报：Comparison method violates its general contract异常的解决

    前言 上周线上的一段排序的java代码出现了一个Comparison method violates its general contract,在解决这个问题的途中学到了一些知识这里总结分享一下. 异常原因 这个排序导致的异常将会在java7以上的版本出现,所以如果你的JDK从6升级到了7或者8,那一定要小心此异常. 在java7的兼容列表中,就有对此排序不兼容的说明: Area: API: Utilities Synopsis: Updated sort behavior for Arrays

  • Java中Druid连接池连接超时获取不到连接的解决

    Java中Druid连接池连接超时获取不到连接的解决

    错误内容: com.alibaba.druid.pool.GetConnectionTimeoutException: wait millis 30000, active 600, maxActive 600, creating 0 detail: Service Error:Cannot find a proper coonection from STDB 错误日志截图: 解决过程: 1.添加了三个参数 作用是如果超过3分钟,连接未释放,那么关闭连接,并报错. 2.进行请求,并查看日志 确认获

  • Laravel 5.4中migrate报错: Specified key was too long error的解决

    前言 大家都知道,我们经常做项目都团队协作开发,每个人都在自己本地的数据库,如果你曾经出现过让同事手动在数据库结构中添加字段的情况,数据库迁移可以解决你这个问题. 不仅如此,在线上部署的时候,也避免了手动导入数据库或手动修改数据结构的麻烦,数据迁移帮你方便的维护着数据结构. 但方便的同时也会伴随着一些问题,下面这篇文章将详细给大家介绍关于Laravel5.4中migrate报错Specified key was too long error的解决方法,下面话不多说了,来一起看看详细的介绍吧. 发

  • Java中的回调

    又忙了一周,事情差不多解决了,终于有可以继续写我的博客了(各位看官久等了). 这次我们来谈一谈Java里的一个很有意思的东西--回调. 什么叫回调,一本正经的来讲,在计算机程序设计中,回调函数是指通过函数参数传递到其它代码的,某一块可执行代码的引用.这一设计允许了底层代码调用在高层定义的子程序. 别急别急,且听我慢慢道来. 举个栗子,设置这样一个情景,老板安排员工做事,然后让他做完后跟他电话说一声.老板当然不会在那里一直等员工做完事情才去做其他事,而是只交代完任务就去忙自己的事情了. 这个例子包

  • 浅谈Java中Collections.sort对List排序的两种方法

    目录 一.Collections.sort的简单使用 二.问题提出 三.Comparable实现排序 四.Comparator实现排序 五.Comparable 与Comparator区别 一.Collections.sort的简单使用 说到List的排序,第一反应当然是使用Collections.sort,方便简单.下面实现一下~~ private void sortStrings() { List<String> list = new ArrayList<String>();

  • 浅谈java中的TreeMap 排序与TreeSet 排序

    TreeMap: package com; import java.util.Comparator; import java.util.TreeMap; public class Test5 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub TreeMap<String, String> tree = new TreeMap<String,

  • java中实现Comparable接口实现自定义排序的示例

    实例如下所示: class Student implements Comparable{ String name; int gpa; @Override public int compareTo(Object arg0) { // TODO Auto-generated method stub Student s = (Student)arg0; if(gpa == s.gpa) return name.compareTo(s.name); else if(gpa < s.gpa) return

  • 详解Java中Method的Invoke方法

    在写代码的时候,发现从父类class通过getDeclaredMethod获取的Method可以调用子类的对象,而子类改写了这个方法,从子类class通过getDeclaredMethod也能获取到Method,这时去调用父类的对象也会报错.虽然这是很符合多态的现象,也符合java的动态绑定规范,但还是想弄懂java是如何实现的,就学习了下Method的源代码.  Method的invoke方法 1.先检查 AccessibleObject的override属性是否为true. Accessib

  • java中List对象排序通用方法

    本文实例讲述了java中List对象排序通用方法.分享给大家供大家参考.具体分析如下: 在数据库中查出来的列表list中,往往需要对不同的字段重新排序,一般的做法都是使用排序的字段,重新到数据库中查询.如果不到数据库查询,直接在第一次查出来的list中排序,无疑会提高系统的性能. 只要把第一次查出来的结果存放在session中,就可以对list重新排序了.一般对list排序可以使用Collections.sort(list),但如果list中包含是一个对象的话,这种方法还是行不通的.那要怎么排序

  • Java中对list map根据map某个key值进行排序的方法

    实例如下所示: package test; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; public class java_ListMapSort { public static void main(String[] args)

随机推荐