第一次面试，我差点被面试官打，就因为Collections.sort

本文转载自微信公众号「稀饭下雪」，第次打因作者帅气的面试小饭饭。转载本文请联系稀饭下雪公众号。差点

该篇文章主要分享隐藏在Collections.sort()中的被面坑，有兴趣的试官看看，已经知道的第次打因可以无视。

是面试这样的，今天在review邓老弟的差点代码的时候，看到一段这样的被面实现

大家先看看这种写法有没有问题?

觉得没有问题的hxd们就要好好看这篇文章了。

我记得那是试官三年前的一个下雨天，那雨下的第次打因比依萍回陆家拿生活费那天还大

依萍

我颤颤巍巍的走进了一家办公室，脚步沉重，面试毕竟这是差点我第一次面试

「底气不足的小饭饭：」 你好，我是被面小饭饭，我是试官来面试的

瘦小的亿华云计算我

「彪形大汉：」 小李是吧，坐

一面面试官

我是xxx公司的面试官斯坦森，看你简历还不错，很少会有实习生敢写精通java的，来，我考考你

这么写有什么问题吗?

「底气不足的小饭饭：」 卧槽，竟然还有姓斯的，不过还好，这道题不难 (⊙o⊙)…

这很简单，updateTime1和updateTime2都是long类型，用int强转有可能导致溢出

「彪形大汉：」 嗯，对，还有呢

继续说下去

「底气不足的小饭饭：」 还有?我想想看

还有就是这样会导致排序出现混乱，可能导致大的在前面

「彪形大汉：」 嗯，对，还有呢

「底气不足的小饭饭：」 还有?没有了啊，其他的我不知道了

「彪形大汉：」 嗯，你能答出前两个，对Java的了解算是熟悉了，香港云服务器不过还没达到精通的程度

还有一个问题，当溢出的时候被int强转会变成负数，从而导致这个函数被调用的时候极有可能会触发以下异常

「已经丢了offer的小饭饭：」 为什么会出发异常?

「彪形大汉：」 你可能不知道，

Collections.sort()在JDK6和JDK7中实现的底层排序算法是不一样的在JDK6中使用的是MergeSort排序，而在JDK7中使用的是TimSort，

使用TimSort排序算法对比较大小的要求更高

问题原因是，对某些数据来说，上述代码会导致compare(a,b)<0并且compare(b,a)<0，也就是a

当这类数据遇到某些特殊情况时，就会发生这个异常。

给你贴一波大家都看不懂的源码占占字数

private void mergeHi(int base1, int len1, int base2, int len2) {          assert len1 > 0 && len2 > 0 && base1 + len1 == base2;         // Copy second run into temp array         T[] a = this.a; // For performance         T[] tmp = ensureCapacity(len2);         int tmpBase = this.tmpBase;         System.arraycopy(a, base2, tmp, tmpBase, len2);         int cursor1 = base1 + len1 - 1;  // Indexes into a         int cursor2 = tmpBase + len2 - 1; // Indexes into tmp array         int dest = base2 + len2 - 1;     // Indexes into a         // Move last element of first run and deal with degenerate cases         a[dest--] = a[cursor1--];         if (--len1 == 0) {              System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);             return;         }         if (len2 == 1) {              dest -= len1;             cursor1 -= len1;             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);             a[dest] = tmp[cursor2];             return;         }         Comparator<? super T> c = this.c;  // Use local variable for performance         int minGallop = this.minGallop;    //  "    "       "     "      "     outer:         while (true) {              int count1 = 0; // Number of times in a row that first run won             int count2 = 0; // Number of times in a row that second run won             /*              * Do the straightforward thing until (if ever) one run              * appears to win consistently.              */             do {                  assert len1 > 0 && len2 > 1;                 if (c.compare(tmp[cursor2], a[cursor1]) < 0) {                      a[dest--] = a[cursor1--];                     count1++;                     count2 = 0;                     if (--len1 == 0)                         break outer;                 } else {                      a[dest--] = tmp[cursor2--];                     count2++;                     count1 = 0;                     if (--len2 == 1)                         break outer;                 }             } while ((count1 | count2) < minGallop);             /*              * One run is winning so consistently that galloping may be a              * huge win. So try that, and continue galloping until (if ever)              * neither run appears to be winning consistently anymore.              */             do {                  assert len1 > 0 && len2 > 1;                 count1 = len1 - gallopRight(tmp[cursor2], a, base1, len1, len1 - 1, c);                 if (count1 != 0) {                      dest -= count1;                     cursor1 -= count1;                     len1 -= count1;                     System.arraycopy(a, cursor1 + 1, a, dest + 1, count1);                     if (len1 == 0)                         break outer;                 }                 a[dest--] = tmp[cursor2--];                 if (--len2 == 1)                     break outer;                 count2 = len2 - gallopLeft(a[cursor1], tmp, tmpBase, len2, len2 - 1, c);                 if (count2 != 0) {                      dest -= count2;                     cursor2 -= count2;                     len2 -= count2;                     System.arraycopy(tmp, cursor2 + 1, a, dest + 1, count2);                     if (len2 <= 1)  // len2 == 1 || len2 == 0                         break outer;                 }                 a[dest--] = a[cursor1--];                 if (--len1 == 0)                     break outer;                 minGallop--;             } while (count1 >= MIN_GALLOP | count2 >= MIN_GALLOP);             if (minGallop < 0)                 minGallop = 0;             minGallop += 2;  // Penalize for leaving gallop mode         }  // End of "outer" loop         this.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to field         if (len2 == 1) {              assert len1 > 0;             dest -= len1;             cursor1 -= len1;             System.arraycopy(a, cursor1 + 1, a, dest + 1, len1);             a[dest] = tmp[cursor2];  // Move first elt of run2 to front of merge         } else if (len2 == 0) {              throw new IllegalArgumentException(                 "Comparison method violates its general contract!");         } else {              assert len1 == 0;             assert len2 > 0;             System.arraycopy(tmp, tmpBase, a, dest - (len2 - 1), len2);         }     } 

看不懂没关系，我也看不懂，不过原理大概是这样的，我们假定：

a<b && b<a，也就是代码中出现的源码下载bug

假定输入数组a[] = { 5,a,7,12,4,b,8,8}，其中待归并的两个有序数组分别是{ 5,a,7,12}和{ 4,b,8,8}

假定b<7&&7>b。这样可以触发“特殊情况”，即：a和b在某一次归并操作后，会同时成为“是否移动元素”的临界条件。

首先，我们有两个有序数组A和B，如下图所示。

找到待归并区间、做好准备操作：

这样，在划分完待归并区间后，得到的结果是这样的：

第一次归并操作：C2落在了元素b上;

然后，开始第一次归并操作。由于B[C2]>A[C1]，我们需要从C2开始，在数组B中找到一个下标n，使得B[n]

这里需要注意两点：首先，临界点的比较条件是B[n]

这样，第一轮归并完成后的结果是这样的：

第二次归并操作：C1落在了元素a上：

接下来做第二次归并操作。由于A[C1]>B[C2](这是先决条件里的第三点：b<7&&7>b)，我们需要从C1开始，从A中找到一个下标m，使得A[m]

这里需要注意比较的顺序性和区间半包性。

这一轮操作完，得到的结果是：

第三、四步操作：出现空集、死循环

可以看到，由于此时A[C1]

然后，由于B[C2]

如果不加干预，排序操作会在这里无限循环下去。TimSort中的干预方式就是当检测到空集时，抛出异常。

「没看懂没关系，总归就是能答出以下三个，其实就算你满分了：」

updateTime1和updateTime2都是long类型，用int强转有可能导致溢出 导致排序出现混乱 因为溢出变成负数，导致排序出现空集、死循环，而TimSort中的干预方式就是当检测到空集时，抛出异常

「彪形大汉：」 虽然你这道题答的一半，但是我给你个补救的机会，怎么解决这个问题

「恢复斗志的小饭饭：」 确保compare(a,b)操作中，如果a>b，那么b

也就是说需要满足以下条件

(x op y)的结果必须与(y op x)的结果相反。即，如果a>b，那么b 传递性。即，如果a>b, b>c，那么a>c。 x==y时，(x op z) = ( y op z )

其实最好是将答案委托给Java基础类，也就是

「彪形大汉：」 嗯，不错，算是达到及格线了，你再坐会，我去叫下二面的面试官。

这个时候另一个彪形大汉走了进来

二面面试官

面试流程未完，待续...........

原文链接：https://mp.weixin.qq.com/s/wPIKqEUgP2mTqFvUAv84Uw

很赞哦!（598）