java 排序報：Comparison method violates its general contract異常的解決方法

這篇文章主要給大家介紹了關於java中排序報：Comparison method violates its general contract異常的解決方法，文中介紹的非常詳細，對大家具有一定的參考學習價值，需要的朋友們下面來一起看看吧。

前言

上週線上的一段排序的java程式碼出現了一個Comparison method violates its general contract ，在解決這個問題的途中學到了一些知識這裡總結分享一下。

異常原因

這個排序導致的例外將會在java7以上的版本出現，所以如果你的JDK從6升級到了7或8，那一定要小心這個異常。

在java7的相容清單中，就有對此排序不相容的說明：

Area: API: Utilities
Synopsis: Updated sort behavior for Arrays and Collections may throw an IllegalArgumentException
Description: 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: behavioral
RFE: 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
  

看起來很像離散數學課中學習的集合的對稱性，傳遞性的關係。

所以異常的原因是因為排序演算法不夠嚴謹導致的，實際上業務上的程式碼經常不如純技術上的嚴謹。例如對於這樣一個演算法：

選出航班中的最低價

那如果兩個相等低價同時存在，按照尋找最低價的邏輯如果這麼寫：

if (thisPrice < lowPrice){
 lowPrice = thisPrice;
}

那低價這個位置就是「先到先得」了。

但如果這麼實現:

if(thisPrice <= lowPrice){
 lowPrice = thisPrice;
}

那後面的低價就會覆蓋前面的，變成了「後來者居上」。 程式中常遇到先到先得和後來者居上這兩個問題。

所以對於上面那個需要提供嚴謹的判斷大小比較函數實作。所以如果是這樣的：

return x > y ? 1 : -1;

那麼就不符合此條件。

不過我們邏輯要比這個複雜，其實是這樣一個排序條件。依照：

• 價格進行排序，如果價格相等則起飛時間靠前的先排。

• 如果起飛時間也相等，就會依照：

• 非共享非經停>非經停>非共享>經停的屬性進行優先權選擇，如果這些屬性都全部相等，才只能算是相等了。

所以這個判斷函數的問題是：

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新增啟動參數。

-Djava.util.Arrays.useLegacyMergeSort=true

還需要注意的是，並不一定你的集合中存在相等的元素，並且比較函數不符合上面的嚴謹定義，就一定會穩定浮現此異常，實際上我們在生產環境出現這個異常的機率很小，畢竟java並不會蠢到先去把整個數組都校驗一遍，實際上它是在排序的過程中發現你不符合此條件的。所以有可能某種集合順序讓你剛好繞過了這個判斷。

以上是java 排序報：Comparison method violates its general contract異常的解決方法的詳細內容。更多資訊請關注PHP中文網其他相關文章！