为什么使用Collections.sort的程序仅对32或更大的列表失败？

以下程序抛出以下exception：

java.lang.IllegalArgumentException: Comparison method violates its general contract! 

我理解Comparator的问题。 请参阅无法复制：“比较方法违反了其总合同！”

我不明白为什么它只对32或更大的List s失败。 谁有人解释一下？

 class Experiment { private static final class MyInteger { private final Integer num; MyInteger(Integer num) { this.num = num; } } private static final Comparator COMPARATOR = (r1, r2) -> { if (r1.num == null || r2.num == null) return 0; return Integer.compare(r1.num, r2.num); }; public static void main(String[] args) { MyInteger[] array = {new MyInteger(0), new MyInteger(1), new MyInteger(null)}; Random random = new Random(); for (int length = 0;; length++) { for (int attempt = 0; attempt < 100000; attempt++) { List list = new ArrayList(); int[] arr = new int[length]; for (int k = 0; k < length; k++) { int rand = random.nextInt(3); arr[k] = rand; list.add(array[rand]); } try { Collections.sort(list, COMPARATOR); } catch (Exception e) { System.out.println(arr.length + " " + Arrays.toString(arr)); return; } } } } } 

Answer 1

它取决于实现，但在openjdk 8中，数组的大小是根据MIN_MERGE检查的，它等于32.这避免了对mergeLo / mergeHi的调用，这会引发exception。

来自JDK / jdk / openjdk / 7u40-b43 8-b132 7-b147 – 8-b132 / java.util.TimSort ：

 static  void sort(T[] a, int lo, int hi, Comparator c, T[] work, int workBase, int workLen) { assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; int nRemaining = hi - lo; if (nRemaining < 2) return; // Arrays of size 0 and 1 are always sorted // If array is small, do a "mini-TimSort" with no merges if (nRemaining < MIN_MERGE) { int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; } /** * March over the array once, left to right, finding natural runs, * extending short natural runs to minRun elements, and merging runs * to maintain stack invariant. */ TimSort ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi, c); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; } 

Answer 2

Java 8使用TimSort算法对输入进行排序。 在TimSort ，当长度至少为32时发生合并阶段。当长度低于32时，则使用可能不检测合同违规的简单排序算法。 让TimSort.java的源代码注释说明TimSort.java ：

 class TimSort { /** * This is the minimum sized sequence that will be merged. Shorter * sequences will be lengthened by calling binarySort. If the entire * array is less than this length, no merges will be performed. * * This constant should be a power of two. It was 64 in Tim Peter's C * implementation, but 32 was empirically determined to work better in * this implementation. In the unlikely event that you set this constant * to be a number that's not a power of two, you'll need to change the * {@link #minRunLength} computation. * * If you decrease this constant, you must change the stackLen * computation in the TimSort constructor, or you risk an * ArrayOutOfBounds exception. See listsort.txt for a discussion * of the minimum stack length required as a function of the length * of the array being sorted and the minimum merge sequence length. */ private static final int MIN_MERGE = 32;