Geek Answers Handbook

What is the "natural order" in TreeMap?

Possible duplicate:
How can I sort map keys in Java?

In the TreeMap class, the Java API says:

Implementation of NavigableMap based on Red-Black. The card is sorted in accordance with the natural order of its keys or the comparator provided at the time the card was created, depending on which constructor is used.

What is meant by natural order? The class used as the key should not implement the Comparable interface, but what order will be used instead?

+6
source share
5 answers

If you try this on your own, you will find that you cannot use a TreeMap that has a K that does not implement Comparable (unless you explicitly provide a Comparator via the TreeMap constructor).

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

Exception in thread "main" java.lang.ClassCastException: application cannot be added to java.lang.Comparable

The javadoc for put() states this explicitly:

Throws:
ClassCastException - if the specified key cannot compare with the keys currently on the map

The link in javadocs for TreeMap for "Natural Ordering" will lead you to the Comparable interface

+5
source

The "natural" order is the order implied by the implementation of the Comparable interface Comparable objects used as keys in the TreeMap . In fact, RBTree should be able to tell which key is smaller than the other key, and there are two ways to provide this logic for RBTree implementation:

  • Comparable interface in the classes used as keys for TreeMap , or
  • Put a Comparator implementation that will compare outside the key class itself.
+4
source

This is a requirement to implement Comparable . It just does not apply at compile time.

 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)

If in doubt, read the TreeMap source . For example, line 541.

+2
source

Natural ordering is simply the order provided by the Comparable interface. You can create a TreeMap without a Comparator , but then any attempt to put any keys that do not implement the natural order throws a ClassCastException .

+1
source

Natural ordering is determined by keys.

So, if you use String, you will receive one order; An integer will give another.

I think Comparable is a requirement.

0
source

More articles:


All Articles