Что такое «естественный порядок» в TreeMap?

Возможный дубликат:
Как отсортировать ключи карты в Java?

В классе TreeMap API Java говорит:

Реализация NavigableMap на основе красно-черного дерева. Карта сортируется в соответствии с естественным порядком ее ключей или компаратором, предоставленным во время создания карты, в зависимости от того, какой конструктор используется.

Что понимается под естественным порядком? Класс, используемый в качестве ключа, не должен реализовывать интерфейс Comparable, но какой порядок будет использоваться вместо этого?


java treemap
person John Threepwood    schedule 30.12.2012    source источник
comment
Суть моего вопроса в том, чтобы понять термин «естественный порядок», а не в том, как сортировать ключи Карты в целом.   -  person John Threepwood    schedule 30.12.2012
comment
Для целого числа естественный порядок означает восходящий порядок, а для строк — алфавитный порядок.   -  person Akash Bisariya    schedule 08.04.2019

Ответы (5)


arrow_upward
8
arrow_downward

Если бы вы попробовали это сами, вы бы обнаружили, что вы не можете использовать TreeMap, у которого есть K, который не реализует Comparable (если вы явно не предоставите Comparator через конструктор TreeMap).

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

Исключение в потоке "main" java.lang.ClassCastException: приложение не может быть преобразовано в java.lang.Comparable

В javadoc для put() это прямо указано:

Выдает:
ClassCastException — если указанный ключ нельзя сравнить с ключами, которые в данный момент находятся на карте.

Ссылка в javadocs для TreeMap для "Естественного Заказ" приведет вас к интерфейсу Comparable

person Brian Roach    schedule 30.12.2012

arrow_upward
5
arrow_downward

«Естественный» порядок — это порядок, подразумеваемый реализацией Comparable с помощью объектов, используемых в качестве ключей в TreeMap. По сути, RBTree должен уметь определять, какой ключ меньше другого ключа, и есть два способа реализовать эту логику в реализации RBTree:

  • Реализовать интерфейс Comparable в классе(ах) используются как ключи к TreeMap, или
  • Предоставьте реализацию Comparator, которая будет выполнять сравнение вне самого ключевого класса.
person Sergey Kalinichenko    schedule 30.12.2012

arrow_upward
3
arrow_downward

Это требование для реализации 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)

В случае сомнений прочитайте TreeMap источник. Строка 541, например.

person James    schedule 30.12.2012
comment
Внедрение Comparable НЕОБХОДИМО. - Это НЕ жесткое требование. Если вы создаете экземпляр TreeMap с Comparator, ключи не должны реализовывать Comparable. - person Stephen C; 30.12.2012
comment
@StephenC - я, конечно, мог бы быть более ясным в своей формулировке, но вопрос в основном задавался в контексте естественного упорядочения, которое применимо только в том случае, если вы не используете экземпляр TreeMap, созданный с помощью Comparator в первую очередь (или , я полагаю, если вы явно создали экземпляр с компаратором, который дал естественное упорядочение - но это сделало бы вопрос довольно бессмысленным), и в этом случае мой ответ остается в силе - он не обеспечивает, чтобы класс был Comparable, но он будет ClassCastException во время выполнения, если это не так. - person James; 30.12.2012

arrow_upward
2
arrow_downward

Естественный порядок — это просто порядок, обеспечиваемый интерфейсом Comparable. Вы можете создать TreeMap без Comparator, но тогда любая попытка поставить какие-либо ключи, которые не реализуют естественный порядок, вызовет ClassCastException.

person GOTO 0    schedule 30.12.2012

arrow_upward
0
arrow_downward

Естественный порядок определяется ключами.

Итак, если вы используете String, вы получите один заказ; Целое даст другое.

Я думаю, что Comparable является требованием.

person duffymo    schedule 30.12.2012
comment
Спасибо. Я могу создать объект TreeMap с самодельным классом, который не реализует интерфейс Comparable. По крайней мере у меня ошибок нет. API также не накладывает ограничений на общий тип ключа. - person John Threepwood; 30.12.2012
comment
Итак, какой заказ вы получаете? Это лучший способ ответить на такие вопросы: пусть JVM скажет вам. - person duffymo; 30.12.2012
comment
Да и нет. Я хочу знать правильный ответ, а не сгенерированный тестом ответ, который может создать у меня ложное впечатление :-) - person John Threepwood; 30.12.2012