第一次面試，我差點被面試官打，就因為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
