Класс Java TreeMap

Класс Java TreeMap хранит пары ключ-значение, очень похожие на класс HashMap. Разница в том, что TreeMap предоставляет эффективный способ хранения пар ключ/значение в отсортированном порядке. Класс TreeMap — это реализация NavigableMap на основе красно-черного дерева.

В этом руководстве по Java TreeMap мы познакомимся с классом TreeMap, методами, вариантами использования и другими важными деталями.

1. Иерархия TreeMap в фреймворке коллекции

Класс TreeMap расширяет класс AbstractMap и реализует интерфейс NavigableMap. Здесь 'K' — тип ключей, а 'V' — тип сопоставленных значений с ключами.

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable {// ...implementation...}

2. Особенности TreeMap

Важные моменты, касающиеся класса Java TreeMap:

• Он хранит пары ключ-значение, подобно HashMap.
• Он допускает только отдельные ключи. Дубликаты ключей невозможны.
• Он не может иметь нулевой ключ, но может иметь несколько нулевых значений.
• Он хранит ключи в отсортированном порядке(естественном порядке) или с использованием компаратора, предоставленного во время создания карты.
• Он обеспечивает гарантированные затраты времени log(n) для операций containsKey, get, put и remove.
• Он не синхронизирован. Используйте Collections.synchronizedSortedMap(new TreeMap()) для работы в параллельной среде.
• Итераторы, возвращаемые методом итератора, являются отказоустойчивыми.

3. Конструкторы

TreeMap имеет пять типов конструкторов:

• TreeMap(): создает новую пустую древовидную карту, используя естественный порядок ее ключей.
• TreeMap(Comparator c): создает новую пустую карту дерева, упорядоченную в соответствии с заданным компаратором.
• TreeMap(Map map): создает новую древовидную карту, содержащую те же сопоставления, что и заданная карта, упорядоченные в соответствии с естественным порядком ее ключей.
• TreeMap(SortedMap map): создает новую древовидную карту, содержащую те же сопоставления и использующую тот же порядок, что и указанная отсортированная карта.

4. Методы

Ниже приведены основные методы, которые нам следует изучить при работе с TreeMap:

• void clear(): удаляет все пары ключ-значение из карты.
• void size(): возвращает количество пар ключ-значение, присутствующих в этой карте.
• void isEmpty(): возвращает true, если эта карта не содержит сопоставлений ключ-значение.
• boolean containsKey(Object key): возвращает «true», если указанный ключ присутствует в карте.
• boolean containsValue(Object key): возвращает «true», если указанное значение сопоставлено хотя бы с одним ключом в карте.
• Object get(Object key): извлекает значение, сопоставленное указанному ключу, или null, если эта карта не содержит сопоставления для ключа.
• Object remove(Object key): удаляет пару ключ-значение для указанного ключа из карты, если она присутствует.
• Компаратор comparator(): возвращает компаратор, используемый для упорядочивания ключей в этой карте, или null, если эта карта использует естественный порядок своих ключей.
• Объект firstKey(): возвращает первый(наименьший) ключ, находящийся в данный момент в древовидной карте.
• Объект lastKey(): возвращает последний(наибольший) ключ в древовидной карте.
• Object ceilingKey(Object key): возвращает наименьший ключ, больший или равный заданному ключу, или null, если такого ключа нет.
• Object higherKey(Object key): возвращает наименьший ключ, строго больший указанного ключа.
• NavigableMap descendingMap(): возвращает обратный порядок отображения, содержащихся на этой карте.

5. Примеры древовидных карт

5.1 Сортировка пар ключ-значение в естественном порядке

Программа на Java, демонстрирующая использование TreeMap, хранящего пары ключ-значение в естественном порядке.

//Natual ordering by deafultTreeMap<Integer, String> pairs = new TreeMap<>();pairs.put(2, "B");pairs.put(1, "A");pairs.put(3, "C");String value = pairs.get(3); //get methodSystem.out.println(value);value = pairs.getOrDefault(5, "oops"); //getOrDefault methodSystem.out.println(value);//Iteration exampleIterator<Integer> iterator = pairs.keySet().iterator();while(iterator.hasNext()) {Integer key = iterator.next();System.out.println("Key: " + key + ", Value: " + pairs.get(key));}//Remove examplepairs.remove(3);System.out.println(pairs);System.out.println(pairs.containsKey(1)); //containsKey methodSystem.out.println(pairs.containsValue("B")); //containsValue methodSystem.out.println(pairs.ceilingKey(2));

Вывод программы.

CoopsKey: 1, Value: AKey: 2, Value: BKey: 3, Value: C{1=A, 2=B}truetrue2

5.2 Индивидуальный заказ с использованием компаратора

TreeMap<Integer, String> pairs = new TreeMap<>(Collections.reverseOrder());pairs.put(2, "B" );pairs.put(1, "A");pairs.put(3, "C");System.out.println(pairs);

Вывод программы.

{3=C, 2=B, 1=A}

6. Когда использовать TreeMap?

Независимо от того, используется ли порядок по умолчанию или пользовательский порядок с использованием компаратора, TreeMap обеспечивает эффективный метод хранения и извлечения содержащейся в нем информации в отсортированном виде. Это делает его превосходным инструментом для сценариев, где информация должна отображаться в отсортированном порядке. Например, информация о сотрудниках на основе их возраста или номеров телефонов в любом мобильном приложении.

Другим полезным вариантом использования может стать словарь, в котором информация записывается и отображается в отсортированном виде.

На самом деле они полезны везде, где нужно сортировать информацию и нужен быстрый случайный доступ. Если случайный доступ не нужен, то лучше использовать отсортированный набор или список.

7. Производительность TreeMap

TreeMap обеспечивает производительность log(n) для большинства операций, таких как add(), remove() и contains(). HashMap выполняет с постоянной производительностью O(1) для тех же операций. Таким образом, HashMap выполняет намного лучше, чем TreeMap.

TreeMap лучше справляется с управлением памятью, поскольку не поддерживает внутренний массив для хранения пар ключ-значение. В HashMap размер массива определяется во время инициализации или изменения размера, что часто больше, чем необходимо в данный момент. Это тратит память. С TreeMap такой проблемы нет.

8. Параллелизм

Обе версии Map, HashMap и TreeMap не синхронизированы, и программисту необходимо управлять одновременным доступом к картам.

Мы можем получить синхронизированное представление древовидной карты явно с помощью Collections.synchronizedSortedMap(new TreeMap()).

Map<Integer, String> syncTreeMap = Collections.synchronizedSortedMap(new TreeMap<Integer, String>());syncTreeMap.put(1, "A");syncTreeMap.put(2, "B" );syncTreeMap.put(3, "C");

9. Заключение

В этом уроке мы узнали о классе Java TreeMap и его внутренностях. Мы увидели, как он хранит пары ключ-значение в отсортированном виде – либо в естественном порядке(по умолчанию), либо в каком-то пользовательском порядке ключей(используя предоставленный компаратор).

Мы обсудили, как и когда использовать TreeMap в приложениях реального времени, и сравнили его производительность с HashMap, чтобы лучше понять, когда использовать ту или иную версию Map.

Напишите мне в комментариях ваши вопросы, связанные с работой с TreeMap в Java.