一、问题

今天在提交代码前做测试时,突然遇到以下错误:

Exception in thread "main" java.lang.IllegalArgumentException: Comparison method violates its general contract!
	at java.util.TimSort.mergeHi(Unknown Source)
	at java.util.TimSort.mergeAt(Unknown Source)
	at java.util.TimSort.mergeForceCollapse(Unknown Source)
	at java.util.TimSort.sort(Unknown Source)
	at java.util.Arrays.sort(Unknown Source)
	at java.util.ArrayList.sort(Unknown Source)
	at java.util.Collections.sort(Unknown Source)

后来经过测试,发现是偶发的,但对于某种情况下,却是必现的,出错的代码模拟如下:

public class PropItem {
	private String name;
	private String number;
	public PropItem(String name, String number) {
		this.name = name;
		this.number = number;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String getNumber() {
		return number;
	}
	public void setNumber(String number) {
		this.number = number;
	}
}
public static void main(String[] args) {
	List<PropItem> items = new ArrayList<>();
	items.add(new PropItem("编码", "number"));
	items.add(new PropItem("名称", "name"));
	items.add(new PropItem("状态", "status"));
	items.add(new PropItem("是否启用", "enable"));
	items.add(new PropItem("创建人", "creator"));
	items.add(new PropItem("修改人", "modifier"));
	items.add(new PropItem("创建时间", "createtime"));
	items.add(new PropItem("修改时间", "modifytime"));
	items.add(new PropItem("描述", "description"));
	items.add(new PropItem("英文名", "englishname"));
	items.add(new PropItem("备注", "abandonment basefactor0"));
	items.add(new PropItem("备注", "abandonment basefactor1"));
	items.add(new PropItem("备注", "abandonment basefactor2"));
	items.add(new PropItem("备注", "abandonment basefactor3"));
	items.add(new PropItem("备注", "abandonment basefactor4"));
	items.add(new PropItem("备注", "abandonment basefactor5"));
	items.add(new PropItem("备注", "abandonment basefactor6"));
	items.add(new PropItem("备注", "abandonment basefactor7"));
	items.add(new PropItem("备注", "abandonment basefactor8"));
	items.add(new PropItem("备注", "abandonment basefactor9"));
	items.add(new PropItem("其他说明", "abandonment asstfactor0"));
	items.add(new PropItem("其他说明", "abandonment asstfactor1"));
	items.add(new PropItem("其他说明", "abandonment asstfactor2"));
	items.add(new PropItem("其他说明", "abandonment asstfactor3"));
	items.add(new PropItem("其他说明", "abandonment asstfactor4"));
	items.add(new PropItem("其他说明", "abandonment asstfactor5"));
	items.add(new PropItem("其他说明", "abandonment asstfactor6"));
	items.add(new PropItem("其他说明", "abandonment asstfactor7"));
	items.add(new PropItem("其他说明", "abandonment asstfactor8"));
	items.add(new PropItem("其他说明", "abandonment asstfactor9"));
	items.add(new PropItem("科目", "abandonment accfield"));
	items.add(new PropItem("数据类型", "functionality.datatype"));
	items.add(new PropItem("功能", "functionality.function"));
	
	Collections.sort(items, new Comparator<PropItem>() {
		@Override
		public int compare(PropItem prop, PropItem other) {
			if(prop.getNumber().length() < other.getNumber().length()){
				return 1;
			}
			return -1;
		}
	});
}

运行上面main方法中的程序就会重现。

二、解决方法

在网上查了下,解决方法很简单,有两种:

  • 设置java.util.Arrays.useLegacyMergeSort参数为true
System.setProperty("java.util.Arrays.useLegacyMergeSort", "true");

如上图所示,在Java SE 6以上的版本中重写Comparator接口的compare方法时,应该实现大于、小于和等于的条件;但在SE 5.0中,可以只实现大于和小于的条件。该参数默认为false,设置为true表示使用5.0版本的比较方式。

  • compare方法中,添加等于时的判断
Collections.sort(items, new Comparator<PropItem>() {
	@Override
	public int compare(PropItem prop, PropItem other) {
		return other.getNumber().length() - prop.getNumber().length();
	}
});

三、补充

1、重现条件

StackOverflow上的Ceekay指出了重现此问题的条件:

I just ran into the same error and spent a good amount of time tracking it down. To help others who run into this error it is important to know how to test TimSort. The checks that violate the transitivity contract and throw this error are deep in the algorithm and require a test to meet certain criteria before this problem can be reproduced.

Create a list with 32 or more objects. Within that list, there needs to two or more runs. Each run must contain 3 or more objects. Once you meet those two criteria you can begin testing for this failure.

A run is defined as a sub-set of the list where each item is already in the desired ordered state.

条件如下:

  • 列表(List)中要有32个或以上的对象

  • 在这个列表中需要有2个或多个run(runTimSort中的概念)

  • 每个run必须包含3个或以上的对象

2、错误解释

Comparison method violates its general contract的简单翻译就是:’比较方法违反了通用原则’,看下面的例子:

引用自StackOverflow上CESDewar的评论
if ( one.length() == 0 ) {
    return 1;                   // empty string sorts last
}
if ( two.length() == 0 ) {
    return -1;                  // empty string sorts last                  
}
return one.compareToIgnoreCase( two );

上面的代码中,如果one和’two’都是空字符串时,程序返回了1而不是0,因此比较器报告为违规。

参考资料: