Skip to content

SortedMap NavigableMap TreeMap

Лекция: Основные структуры данных в Java

Введение

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

1. SortedMap

Определение: SortedMap — это интерфейс, который расширяет интерфейс Map и представляет собой отображение, в котором ключи отсортированы в естественном порядке или по заданному компаратору.

Основные методы: - Comparator<? super K> comparator(): Возвращает компаратор, используемый для сортировки ключей, или null, если ключи отсортированы в естественном порядке. - SortedMap<K, V> subMap(K fromKey, K toKey): Возвращает представление части карты, содержащей ключи от fromKey (включительно) до toKey (исключительно). - SortedMap<K, V> headMap(K toKey): Возвращает представление части карты, содержащей ключи, меньшие toKey. - SortedMap<K, V> tailMap(K fromKey): Возвращает представление части карты, содержащей ключи, большие или равные fromKey. - K firstKey(): Возвращает первый (наименьший) ключ в карте. - K lastKey(): Возвращает последний (наибольший) ключ в карте.

2. NavigableMap

Определение: NavigableMap — это расширение интерфейса SortedMap, которое добавляет методы для навигации по карте. Он позволяет находить ближайшие ключи, а также предоставляет методы для работы с диапазонами.

Основные методы: - K lower(K key): Возвращает наибольший ключ, меньший, чем указанный ключ, или null, если такого ключа нет. - K floor(K key): Возвращает наибольший ключ, меньший или равный указанному ключу, или null, если такого ключа нет. - K ceiling(K key): Возвращает наименьший ключ, больший или равный указанному ключу, или null, если такого ключа нет. - K higher(K key): Возвращает наименьший ключ, больший, чем указанный ключ, или null, если такого ключа нет. - NavigableSet<K> navigableKeySet(): Возвращает набор ключей, отсортированных в порядке навигации.

3. TreeMap

Определение: TreeMap — это реализация интерфейсов NavigableMap и SortedMap, которая использует красно-черное дерево для хранения ключей. Это обеспечивает логарифмическое время выполнения операций поиска, вставки и удаления.

Основные характеристики: - Ключи в TreeMap отсортированы в естественном порядке или по заданному компаратору. - TreeMap не допускает null ключей, но допускает null значения. - TreeMap является не синхронизированной структурой данных, поэтому для многопоточных приложений может потребоваться внешняя синхронизация.

Пример использования:

import java.util.TreeMap;

public class Example {
    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<>();
        map.put("Apple", 1);
        map.put("Banana", 2);
        map.put("Cherry", 3);

        System.out.println("Первый ключ: " + map.firstKey());
        System.out.println("Последний ключ: " + map.lastKey());
        System.out.println("Подмножество от 'Apple' до 'Cherry': " + map.subMap("Apple", "Cherry"));
    }
}

Заключение

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

Если у вас есть вопросы или вы хотите углубиться в какую-либо из тем, не стесняйтесь задавать их!

пример

[[Programming/java/1. osnovi/Тема 6. Основные структуры данных/Урок 8. SortedMap _ NavigableMap _ TreeMap/задание|задание]]