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

不花时间的导读：这是《好好面试系列》第20篇原创文，该系列主要分享小饭饭面试别人、和被别人面试的经历，该篇文章主要分享隐藏在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<b && b<a，因为溢出强转为init变成负数导致的

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

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

    private void mergeHi(int base1, int len1, int base2, int len2) {assert len1 > 0 && len2 > 0 && base1 + len1 == base2;// Copy second run into temp arrayT[] a = this.a; // For performanceT[] tmp = ensureCapacity(len2);int tmpBase = this.tmpBase;System.arraycopy(a, base2, tmp, tmpBase, len2);int cursor1 = base1 + len1 - 1;  // Indexes into aint cursor2 = tmpBase + len2 - 1; // Indexes into tmp arrayint dest = base2 + len2 - 1;     // Indexes into a// Move last element of first run and deal with degenerate casesa[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 performanceint minGallop = this.minGallop;    //  "    "       "     "      "outer:while (true) {int count1 = 0; // Number of times in a row that first run wonint 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 == 0break 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" loopthis.minGallop = minGallop < 1 ? 1 : minGallop;  // Write back to fieldif (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]<A'[C1]。找到之后，将B'(n,C2]复制到D的位置上。复制完成后，将C2和D都向左移动若干个位置。

这里需要注意两点：首先，临界点的比较条件是B'[n]<A'[C1]，这是有顺序的；其次，复制的条件是B'(n,C2]，这是个半包区间。

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

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

接下来做第二次归并操作。由于A'[C1]>B'[C2]（这是先决条件里的第三点：b<7&&7>b），我们需要从C1开始，从A'中找到一个下标m，使得A'[m]<B'[C2]。找到之后，将A'(m,C1]复制到D的位置上。复制完成后，将C1和D都向左移动若干个位置。

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

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

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

可以看到，由于此时A'[C1]<B'[C2]，我们需要重复第一次归并操作。先C2开始，在数组B'中找到一个下标n，使得B'[n]<A'[C1]。但是，由于b<a（注意顺序），这一轮找到的n会等于C2。这就导致了需要复制到D中的元素集合B'(n,C2]是一个空集——或者用伪代码来说，我们需要将一个长度为0的数组复制到D的位置上去。

然后，由于B'[C2]<A'[C1]，我们需要重复第二次归并操作。但是很显然，由于a<b（同样注意顺序），我们又会得到一个空集。

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

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

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

• 导致排序出现混乱

• 因为溢出变成负数，导致排序出现空集、死循环，而TimSort中的干预方式就是当检测到空集时，抛出异常

❝

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

❞

❝

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

❞

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

• (x op y)的结果必须与(y op x)的结果相反。即，如果a>b，那么b<a。

• 传递性。即，如果a>b, b>c，那么a>c。

• x==y时，(x op z) = ( y op z )

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

❝

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

❞

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

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

--《好好面试系列文》--

高级开发竟然被构造器循环依赖难住了？

肥肥的主管和帅气的小饭饭讨论了下ForkJoinPool

聊聊Autowired的常考面试题

面试官告诉你什么是JMM和常考面试题

去年面了多个候选人，看看我挖的坑还有他们应该要补的Java基础(二)

去年面了多个候选人，看看我挖的坑还有他们应该要补的Java基础(一)

小饭饭：某游戏大厂高级开发，专门和主管抬杠的小组长。 想学dubbo的可以微信搜一搜：稀饭下雪，第一时间阅读Caffeine、dubbo等优秀框架的源码分析和教材讲解以及实际应用，有需要java面试资料的也可以关注一波，回复java资源获取我整理的专项资料。