What is 'natural ordering' in a TreeMap?

Question

Possible Duplicate:
How can I sort the keys of a Map in Java?

In class TreeMap the Java API says:

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

What is meant by natural ordering ? A class used as key does not have to implement the Comparable interface, but what ordering will be used instead ?

The point of my question is to understand the term 'natural ordering', not how to sort the keys of a Map in general. — John Threepwood, Dec 30 '12 at 01:50
For an integer, natural order mean ascending order and for strings, alphabetical order. — Akash Bisariya, Apr 08 '19 at 06:12

Brian Roach · Accepted Answer · 2012-12-30T01:59:41.157

If you were to try this yourself you'd 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: App cannot be cast to java.lang.Comparable

The javadoc for put() states this explicitly:

Throws:
ClassCastException - if the specified key cannot be compared with the keys currently in the map

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

score 5 · Answer 2 · answered Dec 30 '12 at 01:44

"Natural" ordering is the ordering implied by the implementation of the Comparable interface by the objects used as keys in the TreeMap. Essentially, RBTree must be able to tell which key is smaller than the other key, and there are two ways to supply that logic to the RBTree implementation:

Implement Comparable interface in the class(es) used as keys to TreeMap, or
Supply an implementation of the Comparator that would do comparing outside the key class itself.

score 4 · Answer 3 · edited Jan 02 '15 at 07:58

4

It is a requirement to implement Comparable. It's just not enforced 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)

When in doubt, read the TreeMap source. Line 541, for instance.

edited Jan 02 '15 at 07:58

ADTC

8,999
5
68
93

answered Dec 30 '12 at 01:56

James

8,512
1
26
28

*"It IS a requirement to implement Comparable."* - It is NOT a hard requirement. If you instantiate the `TreeMap` with a `Comparator`, the keys don't need to implement `Comparable`. – Stephen C Dec 30 '12 at 02:49
@StephenC - I certainly could have been more clear in my wording, but the question was basically asking in the context of the "Natural Ordering", which would only apply if you're not using a TreeMap instantiated with a Comparator in the first place (or, I suppose, if you explicitly instantiated with a Comparator which gave the Natural Ordering - but that would make the question rather nonsensical), in which case, my answer stands - it doesn't enforce that the class is Comparable, but it will ClassCastException at runtime if it's not. – James Dec 30 '12 at 06:52

score 2 · Answer 4 · answered Dec 30 '12 at 01:55

2

Natural ordering is just 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 a natural order will throw a ClassCastException.

answered Dec 30 '12 at 01:55

GOTO 0

42,323
22
125
158

score 0 · Answer 5 · answered Dec 30 '12 at 01:43

0

The natural ordering is determined by the keys.

So if you use a String you'll get one ordering; Integer will give another.

I think Comparable is a requirement.

answered Dec 30 '12 at 01:43

duffymo

305,152
44
369
561

Thank you. I can create a TreeMap object with a self-made class which does not implement the Comparable interface. At least, I get no errors. The API also makes no restrictions to the key generic type. – John Threepwood Dec 30 '12 at 01:47
So what ordering do you get? This is the best way to answer such questions: Let the JVM tell you. – duffymo Dec 30 '12 at 01:50
Yes and no. I want to know the correct answer, not a test-generated answer which could possibly give me a false impression :-) – John Threepwood Dec 30 '12 at 01:52

What is 'natural ordering' in a TreeMap?

5 Answers5