34. Как устроена TreeMap, сложность основных операций?

Класс TreeMap<K, V> представляет отображение в виде дерева. Он наследуется от класса AbstractMap и реализует интерфейс NavigableMap, а следовательно, также и интерфейс SortedMap. Поэтому в отличие от коллекции HashMap в TreeMap все объекты автоматически сортируются по возрастанию их ключей.

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

Класс TreeMap имеет следующие конструкторы:

• TreeMap(): создает пустое отображение в виде дерева
• TreeMap(Map<? extends K,? extends V> map): создает дерево, в которое добавляет все элементы из отображения map
• TreeMap(SortedMap<K, ? extends V> smap): создает дерево, в которое добавляет все элементы из отображения smap
• TreeMap(Comparator<? super K> comparator): создает пустое дерево, где все добавляемые элементы впоследствии будут отсортированы компаратором.

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

SortedMap — интерфейс, который расширяет Map и добавляет методы, актуальные для отсортированного набора данных:

• firstKey(): возвращает ключ первого элемента мапы;
• lastKey(): возвращает ключ последнего элемента;
• headMap(K end): возвращает мапу, которая содержит все элементы текущей, от начала до элемента с ключом end;
• tailMap(K start): возвращает мапу, которая содержит все элементы текущей, начиная с элемента start и до конца;
• subMap(K start, K end): возвращает мапу, которая содержит все элементы текущей,начиная с элемента start и до элемента с ключом end.

NavigableMap — интерфейс, который расширяет SortedMap и добавляет методы для навигации между элементами мапы:

• firstEntry(): возвращает первый пару “ключ-значение”;
• lastEntry(): возвращает последнюю пару “ключ-значение”;
• pollFirstEntry(): возвращает и удаляет первую пару;
• pollLastEntry(): возвращает и удаляет последнюю пару;
• ceilingKey(K obj): возвращает наименьший ключ k, который больше или равен ключу obj. Если такого ключа нет, возвращает null;
• floorKey(K obj): возвращает самый большой ключ k, который меньше или равен ключу obj. Если такого ключа нет, возвращает null;
• lowerKey(K obj): возвращает наибольший ключ k, который меньше ключа obj. Если такого ключа нет, возвращает null;
• higherKey(K obj): возвращает наименьший ключ k, который больше ключа obj. Если такого ключа нет, возвращает null;
• ceilingEntry(K obj): аналогичен методу ceilingKey(K obj), только возвращает пару “ключ-значение” (или null);
• floorEntry(K obj): аналогичен методу floorKey(K obj), только возвращает пару “ключ-значение” (или null);
• lowerEntry(K obj): аналогичен методу lowerKey(K obj), только возвращает пару “ключ-значение” (или null);
• higherEntry(K obj): аналогичен методу higherKey(K obj), только возвращает пару “ключ-значение” (или null);
• descendingKeySet(): возвращает NavigableSet, содержащий все ключи, отсортированные в обратном порядке;
• descendingMap(): возвращает NavigableMap, содержащую все пары, отсортированные в обратном порядке;
• navigableKeySet(): возвращает объект NavigableSet, содержащий все ключи в порядке хранения;
• headMap(K upperBound, boolean incl): возвращает мапу, которая содержит пары от начала и до элемента upperBound. Аргумент incl указывает, нужно ли включать элемент upperBound в возвращаемую мапу;
• tailMap(K lowerBound, boolean incl): функционал похож на предыдущий метод, только возвращаются пары от lowerBound и до конца;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): как и в предыдущих методах, возвращаются пары от lowerBound и до upperBound, аргументы lowIncl и highIncl указывают, включать ли граничные элементы в новую мапу.

Предыдущий вопрос: 33. Что такое LinkedHashMap?

Следующий вопрос: 35. Что такое WeakHashMap?

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку:напишите мне