前言
上周線上的一段排序的java代碼出現了一個Comparison method violates its general contract，在解決這個問題的途中學到了一些知識這里總結分享一下。
異常原因
這個排序導致的異常將會在java7以上的版本出現，所以如果你的JDK從6升級到了7或者8，那一定要小心此異常。
在java7的兼容列表中，就有對此排序不兼容的說明：
|
1
2
3
4
5
6
|
Area: API: UtilitiesSynopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentExceptionDescription: The sorting algorithm used by java.util.Arrays.sort and (indirectly) by java.util.Collections.sort has been replaced. The new sort implementation may throw an IllegalArgumentException if it detects a Comparable that violates the Comparable contract. The previous implementation silently ignored such a situation.If the previous behavior is desired, you can use the new system property, java.util.Arrays.useLegacyMergeSort, to restore previous mergesort behavior.Nature of Incompatibility: behavioralRFE: 6804124 |
我從資料中查閱到java7開始引入了Timsort的排序算法。我之前一直以為大部分標準庫的內置排序算法都是快速排序。現在才得知很多語言內部都使用Timsort排序。隨后我在wiki百科上找到了這樣一句話：
t was implemented by Tim Peters in 2002 for use in the Python programming language.
所以這個排序自然是以他命名的。
隨后我又在網上找到了這樣一張圖排序比較的圖：
可以發現，Timsort在表現上比QuickSort還要好。
這篇博客不去詳細討論Timsort的實現（看上去這個算法還挺復雜的），我可能會寫另一篇博客單獨討論Timsort，簡單來說Timsort結合了歸并排序和插入排序。這個算法在實現過程中明確需要：嚴格的單調遞增或者遞減來保證算法的穩定性。
-
sgn(compare(x, y)) == -sgn(compare(y, x)) -
((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0 -
compare(x, y)==0 implies that sgn(compare(x, z))==sgn(compare(y, z)) for all z
看上去很像離散數學課中學習的集合的對稱性，傳遞性的關系。
所以異常的原因是因為排序算法不夠嚴謹導致的，實際上業務上的代碼經常不如純技術上的嚴謹。比如對于這樣一個算法：
選出航班中的最低價
那如果兩個相等低價同時存在，按照尋找最低價的邏輯如果這么寫：
|
1
2
3
|
if (thisPrice < lowPrice){ lowPrice = thisPrice;} |
那低價這個位置就是“先到先得”了。
但如果這么實現:
|
1
2
3
|
if(thisPrice <= lowPrice){ lowPrice = thisPrice;} |
那后面的低價就會覆蓋前面的，變成了“后來者居上”。編程中經常遇到先到先得和后來者居上這兩個問題。
所以對于上面那個需要提供嚴謹的判斷大小比較函數實現。所以如果是這樣的：
|
1
|
return x > y ? 1 : -1; |
那么就不符合此條件。
不過我們邏輯要比這個復雜，其實是這樣一個排序條件。按照：
- 價格進行排序，如果價格相等則起飛時間靠前的先排。
- 如果起飛時間也相等，就會按照：
- 非共享非經停>非經停>非共享>經停的屬性進行優先級選擇，如果這些屬性都全部相等，才只能算是相等了。
所以這個判斷函數的問題是：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public compareFlightPrice(flightPrice o1, flightPrice o2){ // 非經停非共享 if (o1.getStopNumber() == 0 && !o1.isShare()) { return -1; } else if (o2.getStopNumber() == 0 && !o2.isShare()) { return 1; } else { if (o1.getStopNumber() == 0) { return -1; } else if (o2.getStopNumber() == 0) { return 1; } else { if (!o1.isShare()) { return -1; } else if (!o2.isShare()) { return 1; } else { if (o1.getStopNumber() > 0) { return -1; } else if (o2.getStopNumber() > 0) { return 1; } else { return 0; } } } }} |
這個函數有明顯的先到先得的問題，比如對于compareFlightPrice(a, b) ，如果ab都是非共享非經停，那么這個就會把a排到前面，但如果調用compareFlightPrice(b, a) ，b又會排到前面，所以必須判斷a是非共享非經停且b不是非共享非經停，才能讓a排在前面。
當然除了改比較函數，還有一個解決方式是：給jvm添加啟動參數。
|
1
|
-Djava.util.Arrays.useLegacyMergeSort=true |
還需要注意的是，并不一定你的集合中存在相等的元素，并且比較函數不符合上面的嚴謹定義，就一定會穩定浮現此異常，實際上我們在生產環境出現此異常的概率很小，畢竟java并不會蠢到先去把整個數組都校驗一遍，實際上它是在排序的過程中發現你不符合此條件的。所以有可能某種集合順序讓你剛好繞過了此判斷。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流，謝謝大家對服務器之家的支持。
原文鏈接：http://www.pulpcode.cn/2017/06/18/comparison-method-violates-its-general-contractfor-sort/
