第一次面試，我差點(diǎn)被面試官打，就因?yàn)镃ollections.sort
本文轉(zhuǎn)載自微信公眾號「稀飯下雪」，作者帥氣的小飯飯。轉(zhuǎn)載本文請聯(lián)系稀飯下雪公眾號。
該篇文章主要分享隱藏在Collections.sort()中的坑，有興趣的看看，已經(jīng)知道的可以無視。
是這樣的，今天在review鄧?yán)系艿拇a的時(shí)候，看到一段這樣的實(shí)現(xiàn)
大家先看看這種寫法有沒有問題?
覺得沒有問題的hxd們就要好好看這篇文章了。
我記得那是三年前的一個(gè)下雨天，那雨下的比依萍回陸家拿生活費(fèi)那天還大
依萍
我顫顫巍巍的走進(jìn)了一家辦公室，腳步沉重，畢竟這是我第一次面試
「底氣不足的小飯飯：」 你好，我是小飯飯，我是來面試的
瘦小的我
「彪形大漢：」 小李是吧，坐
一面面試官
我是xxx公司的面試官斯坦森，看你簡歷還不錯(cuò)，很少會有實(shí)習(xí)生敢寫精通java的，來，我考考你
這么寫有什么問題嗎?
「底氣不足的小飯飯：」 臥槽，竟然還有姓斯的，不過還好，這道題不難 (⊙o⊙)…
這很簡單，updateTime1和updateTime2都是long類型，用int強(qiáng)轉(zhuǎn)有可能導(dǎo)致溢出
「彪形大漢：」 嗯，對，還有呢
繼續(xù)說下去
「底氣不足的小飯飯：」 還有?我想想看
還有就是這樣會導(dǎo)致排序出現(xiàn)混亂，可能導(dǎo)致大的在前面
「彪形大漢：」 嗯，對，還有呢
「底氣不足的小飯飯：」 還有?沒有了啊，其他的我不知道了
「彪形大漢：」 嗯，你能答出前兩個(gè)，對Java的了解算是熟悉了，不過還沒達(dá)到精通的程度
還有一個(gè)問題，當(dāng)溢出的時(shí)候被int強(qiáng)轉(zhuǎn)會變成負(fù)數(shù)，從而導(dǎo)致這個(gè)函數(shù)被調(diào)用的時(shí)候極有可能會觸發(fā)以下異常
「已經(jīng)丟了offer的小飯飯：」 為什么會出發(fā)異常?
「彪形大漢：」 你可能不知道，
Collections.sort()在JDK6和JDK7中實(shí)現(xiàn)的底層排序算法是不一樣的在JDK6中使用的是MergeSort排序，而在JDK7中使用的是TimSort，
使用TimSort排序算法對比較大小的要求更高
問題原因是，對某些數(shù)據(jù)來說，上述代碼會導(dǎo)致compare(a,b)<0并且compare(b,a)<0，也就是a
當(dāng)這類數(shù)據(jù)遇到某些特殊情況時(shí)，就會發(fā)生這個(gè)異常。
給你貼一波大家都看不懂的源碼占占字?jǐn)?shù)
- 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);
- }
- }
看不懂沒關(guān)系，我也看不懂，不過原理大概是這樣的，我們假定：
a<b && b<a，也就是代碼中出現(xiàn)的bug
假定輸入數(shù)組a[] = {5,a,7,12,4,b,8,8}，其中待歸并的兩個(gè)有序數(shù)組分別是{5,a,7,12}和{4,b,8,8}
假定b<7&&7>b。這樣可以觸發(fā)“特殊情況”，即：a和b在某一次歸并操作后，會同時(shí)成為“是否移動元素”的臨界條件。
首先，我們有兩個(gè)有序數(shù)組A和B，如下圖所示。
找到待歸并區(qū)間、做好準(zhǔn)備操作：
這樣，在劃分完待歸并區(qū)間后，得到的結(jié)果是這樣的：
第一次歸并操作：C2落在了元素b上;
然后，開始第一次歸并操作。由于B'[C2]>A'[C1]，我們需要從C2開始，在數(shù)組B'中找到一個(gè)下標(biāo)n，使得B'[n]
這里需要注意兩點(diǎn)：首先，臨界點(diǎn)的比較條件是B'[n]
這樣，第一輪歸并完成后的結(jié)果是這樣的：
第二次歸并操作：C1落在了元素a上：
接下來做第二次歸并操作。由于A'[C1]>B'[C2](這是先決條件里的第三點(diǎn)：b<7&&7>b)，我們需要從C1開始，從A'中找到一個(gè)下標(biāo)m，使得A'[m]
這里需要注意比較的順序性和區(qū)間半包性。
這一輪操作完，得到的結(jié)果是：
第三、四步操作：出現(xiàn)空集、死循環(huán)
可以看到，由于此時(shí)A'[C1]
然后，由于B'[C2]
如果不加干預(yù)，排序操作會在這里無限循環(huán)下去。TimSort中的干預(yù)方式就是當(dāng)檢測到空集時(shí)，拋出異常。
「沒看懂沒關(guān)系，總歸就是能答出以下三個(gè)，其實(shí)就算你滿分了：」
- updateTime1和updateTime2都是long類型，用int強(qiáng)轉(zhuǎn)有可能導(dǎo)致溢出
- 導(dǎo)致排序出現(xiàn)混亂
- 因?yàn)橐绯鲎兂韶?fù)數(shù)，導(dǎo)致排序出現(xiàn)空集、死循環(huán)，而TimSort中的干預(yù)方式就是當(dāng)檢測到空集時(shí)，拋出異常
「彪形大漢：」 雖然你這道題答的一半，但是我給你個(gè)補(bǔ)救的機(jī)會，怎么解決這個(gè)問題
「恢復(fù)斗志的小飯飯：」 確保compare(a,b)操作中，如果a>b，那么b
也就是說需要滿足以下條件
- (x op y)的結(jié)果必須與(y op x)的結(jié)果相反。即，如果a>b，那么b
- 傳遞性。即，如果a>b, b>c，那么a>c。
- x==y時(shí)，(x op z) = ( y op z )
其實(shí)最好是將答案委托給Java基礎(chǔ)類，也就是
「彪形大漢：」 嗯，不錯(cuò)，算是達(dá)到及格線了，你再坐會，我去叫下二面的面試官。
這個(gè)時(shí)候另一個(gè)彪形大漢走了進(jìn)來
二面面試官
面試流程未完，待續(xù)...........
原文鏈接：https://mp.weixin.qq.com/s/wPIKqEUgP2mTqFvUAv84Uw
