2012-12-30 121 views
6

可能重複:
How can I sort the keys of a Map in Java?什麼是TreeMap中的「自然排序」?

TreeMap類的Java API表示:基於

紅黑樹NavigableMap實現。該地圖根據其按鍵的自然順序或在地圖創建時提供的比較器進行排序,具體取決於使用哪個構造函數。

什麼是自然排序?用作鍵的類不必實現接口,但將使用什麼順序呢?

+6

我的問題的關鍵是要理解術語'自然排序',而不是如何排序一般地圖的鍵。 –

回答

5

如果你這個嘗試自己你會發現,你不能用一個TreeMap具有K沒有實現Comparable(除非你明確地通過TreeMap構造提供Comparator)。

public class App 
{ 
    public static void main(String[] args) 
    { 
     TreeMap<App,String> tm = new TreeMap<App,String>(); 
     tm.put(new App(), "value"); 
    } 
} 

異常在線程 「主要」 java.lang.ClassCastException:

:應用程序不能轉換爲java.lang.Comparable的

的爲put()美國這個明確的javadoc

拋出:
ClassCastException - 如果指定的鍵不能與在地圖

的「自然排序」中javadocs for TreeMap中的鏈接可以到Comparable接口

0

自然排序由鍵確定。

所以,如果你使用一個字符串,你會得到一個排序;整數會給另一個。

我認爲可比是一個要求。

+0

謝謝。我可以用一個自制的類創建一個沒有實現Comparable接口的TreeMap對象。至少,我沒有錯誤。該API也不對關鍵的泛型類型進行限制。 –

+0

那麼你訂購什麼?這是回答這些問題的最佳方法:讓JVM告訴你。 – duffymo

+0

是的,沒有。我想知道正確的答案,而不是測試生成的答案,這可能會給我一個錯誤的印象:-) –

4

「自然」排序是由在TreeMap中用作鍵的對象實現Comparable接口所​​暗示的順序。從本質上講,RBTree必須能夠分辨哪個鍵比其他鍵更小,並有該邏輯提供給RBTree實現方式有兩種:

  • 實現類(ES)Comparable接口用作鍵TreeMap
  • 提供Comparator的實現,它將在關鍵類本身之外進行比較。
1

自然排序當前鍵僅僅是由Comparable接口提供的順序。您可以創建一個TreeMap而不需要Comparator,但是如果嘗試將任何不執行自然順序的密鑰投入,將會發出ClassCastException

2

要求實施Comparable。它只是在編譯時沒有執行。

jamlong% cat Wah.java 

import java.util.*; 

public class Wah { 

    public static void main(String[] args) { 
     TreeMap<Wah, Integer> wah = new TreeMap<Wah, Integer>(); 
     wah.put(new Wah(), 1); 
     wah.put(new Wah(), 2); 
    } 
} 

jamlong% java Wah 

Exception in thread "main" java.lang.ClassCastException: Wah cannot be cast to java.lang.Comparable 
    at java.util.TreeMap.put(TreeMap.java:542) 
    at Wah.main(Wah.java:8) 

當有疑問時,read the TreeMap source。例如,541行。

+0

*「這是一個要求實施可比較。」 - - 這不是一個硬性要求。如果你用'Comparator'實例化'TreeMap',這些鍵不需要實現'Comparable'。 –

+0

@StephenC - 我當然可以在我的措辭中更加清楚,但問題基本上是在「自然順序」的背景下提出的,這隻適用於如果您沒有使用第一個比較器實例化的TreeMap (或者,我想,如果你明確地實例化了一個給出自然排序的比較器,但這會讓問題變得毫無意義),在這種情況下,我的答案是 - 它不強制類是Comparable,但是如果不是,它會在運行時出現ClassCastException。 – James