NavigableSet, особенности и внутреннее устройство
NavigableSet — это один из интерфейсов в Java Collection Framework, который расширяет интерфейс SortedSet. Он предоставляет дополнительные методы для навигации по элементам в наборе на основе их естественного порядка или на основе компаратора, заданного при создании набора. NavigableSet — это специализированная коллекция, которая особенно полезна, когда вам нужно работать с отсортированными наборами данных, и когда важны операции, связанные с поиском ближайших элементов или диапазонов значений.
Особенности NavigableSet
Упорядоченность элементов:
NavigableSet, как и его родительский интерфейс SortedSet, гарантирует, что элементы хранятся в упорядоченном виде. Упорядоченность может быть основана на естественном порядке элементов (если элементы реализуют интерфейс Comparable) или на пользовательском компараторе, переданном в конструктор.
Поддержка поиска ближайших элементов:
NavigableSet предоставляет методы для поиска элементов, которые являются ближайшими к заданному значению. Например, методы ceiling(E e), floor(E e), higher(E e), и lower(E e) позволяют найти наименьший элемент, который больше или равен заданному, наибольший элемент, который меньше или равен заданному, и так далее.
Поддержка поднаборов:
NavigableSet поддерживает создание поднаборов с помощью методов subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive), headSet(E toElement, boolean inclusive), и tailSet(E fromElement, boolean inclusive). Эти методы возвращают новые представления набора, которые включают или исключают определенные диапазоны значений.
Реверсированная версия:
Метод descendingSet() возвращает представление набора в обратном порядке. Это особенно полезно, когда необходимо выполнить операции с набором в порядке, обратном естественному.
Безопасность и неизменяемость:
NavigableSet предоставляет неизменяемые представления поднаборов, что обеспечивает безопасность при многопоточном доступе.
Внутреннее устройство NavigableSet
Хотя интерфейс NavigableSet не определяет, как именно должны быть реализованы коллекции, обычно используется одна из следующих реализаций:
TreeSet:
Самая распространенная реализация NavigableSet в Java — это класс TreeSet. TreeSet основан на структуре данных красно-черного дерева, которая обеспечивает логарифмическое время выполнения основных операций (вставка, удаление, поиск). Поскольку TreeSet является упорядоченной структурой данных, элементы в нем всегда хранятся в отсортированном порядке.
ConcurrentSkipListSet:
Еще одна реализация NavigableSet — это ConcurrentSkipListSet. Этот класс основан на структуре данных, называемой "skip list" (список с пропусками). В отличие от TreeSet, который не является потокобезопасным, ConcurrentSkipListSet предоставляет безопасный для многопоточного использования набор с логарифмическим временем доступа. Это делает его идеальным выбором для использования в средах, где требуется потокобезопасность без блокировок.
NavigableSet будет полезен в следующих сценариях:
Диапазонные запросы:
Если вам нужно работать с подмножествами данных на основе диапазонов, то NavigableSet идеально подходит, так как он позволяет легко извлекать элементы в заданном диапазоне.
Поиск ближайших значений:
Если задача требует частого поиска ближайших значений (например, в географических приложениях для поиска ближайших координат), то NavigableSet предоставляет необходимые методы для таких операций.
Обратный порядок:
Когда нужно получить элементы в порядке, обратном их естественному порядку, метод descendingSet() упрощает эту задачу.
#Java #Training #Medium #NavigableSet
NavigableSet — это один из интерфейсов в Java Collection Framework, который расширяет интерфейс SortedSet. Он предоставляет дополнительные методы для навигации по элементам в наборе на основе их естественного порядка или на основе компаратора, заданного при создании набора. NavigableSet — это специализированная коллекция, которая особенно полезна, когда вам нужно работать с отсортированными наборами данных, и когда важны операции, связанные с поиском ближайших элементов или диапазонов значений.
Особенности NavigableSet
Упорядоченность элементов:
NavigableSet, как и его родительский интерфейс SortedSet, гарантирует, что элементы хранятся в упорядоченном виде. Упорядоченность может быть основана на естественном порядке элементов (если элементы реализуют интерфейс Comparable) или на пользовательском компараторе, переданном в конструктор.
Поддержка поиска ближайших элементов:
NavigableSet предоставляет методы для поиска элементов, которые являются ближайшими к заданному значению. Например, методы ceiling(E e), floor(E e), higher(E e), и lower(E e) позволяют найти наименьший элемент, который больше или равен заданному, наибольший элемент, который меньше или равен заданному, и так далее.
Поддержка поднаборов:
NavigableSet поддерживает создание поднаборов с помощью методов subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive), headSet(E toElement, boolean inclusive), и tailSet(E fromElement, boolean inclusive). Эти методы возвращают новые представления набора, которые включают или исключают определенные диапазоны значений.
Реверсированная версия:
Метод descendingSet() возвращает представление набора в обратном порядке. Это особенно полезно, когда необходимо выполнить операции с набором в порядке, обратном естественному.
Безопасность и неизменяемость:
NavigableSet предоставляет неизменяемые представления поднаборов, что обеспечивает безопасность при многопоточном доступе.
Внутреннее устройство NavigableSet
Хотя интерфейс NavigableSet не определяет, как именно должны быть реализованы коллекции, обычно используется одна из следующих реализаций:
TreeSet:
Самая распространенная реализация NavigableSet в Java — это класс TreeSet. TreeSet основан на структуре данных красно-черного дерева, которая обеспечивает логарифмическое время выполнения основных операций (вставка, удаление, поиск). Поскольку TreeSet является упорядоченной структурой данных, элементы в нем всегда хранятся в отсортированном порядке.
NavigableSet<Integer> navigableSet = new TreeSet<>();
navigableSet.add(5);
navigableSet.add(2);
navigableSet.add(9);
System.out.println(navigableSet); // [2, 5, 9]
ConcurrentSkipListSet:
Еще одна реализация NavigableSet — это ConcurrentSkipListSet. Этот класс основан на структуре данных, называемой "skip list" (список с пропусками). В отличие от TreeSet, который не является потокобезопасным, ConcurrentSkipListSet предоставляет безопасный для многопоточного использования набор с логарифмическим временем доступа. Это делает его идеальным выбором для использования в средах, где требуется потокобезопасность без блокировок.
NavigableSet<String> navigableSet = new ConcurrentSkipListSet<>();
navigableSet.add("banana");
navigableSet.add("apple");
navigableSet.add("cherry");
System.out.println(navigableSet); // [apple, banana, cherry]
NavigableSet будет полезен в следующих сценариях:
Диапазонные запросы:
Если вам нужно работать с подмножествами данных на основе диапазонов, то NavigableSet идеально подходит, так как он позволяет легко извлекать элементы в заданном диапазоне.
Поиск ближайших значений:
Если задача требует частого поиска ближайших значений (например, в географических приложениях для поиска ближайших координат), то NavigableSet предоставляет необходимые методы для таких операций.
Обратный порядок:
Когда нужно получить элементы в порядке, обратном их естественному порядку, метод descendingSet() упрощает эту задачу.
#Java #Training #Medium #NavigableSet
Основные методы NavigableSet и примеры использования
Основные методы NavigableSet
E lower(E e)
Возвращает наибольший элемент в наборе, который меньше заданного элемента e. Если такого элемента нет, возвращает null.
E floor(E e)
Возвращает наибольший элемент в наборе, который меньше или равен заданному элементу e. Если такого элемента нет, возвращает null.
E ceiling(E e)
Возвращает наименьший элемент в наборе, который больше или равен заданному элементу e. Если такого элемента нет, возвращает null.
E higher(E e)
Возвращает наименьший элемент в наборе, который больше заданного элемента e. Если такого элемента нет, возвращает null.
E pollFirst() и E pollLast()
Эти методы удаляют и возвращают первый и последний элемент набора соответственно. Если набор пуст, они возвращают null.
NavigableSet<E> descendingSet()
Возвращает представление текущего набора в обратном порядке. Любые изменения в этом представлении будут отражаться на исходном наборе и наоборот.
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
Возвращает поднабор элементов от fromElement до toElement, при этом можно указать, включать ли эти элементы в поднабор.
NavigableSet<E> headSet(E toElement, boolean inclusive)
Возвращает поднабор элементов от начала набора до toElement. Можно указать, включать ли элемент toElement в поднабор.
NavigableSet<E> tailSet(E fromElement, boolean inclusive)
Возвращает поднабор элементов от fromElement до конца набора. Можно указать, включать ли элемент fromElement в поднабор.
Примеры использования NavigableSet
Пример 1: Фильтрация диапазона значений
Предположим, у нас есть набор температур за неделю, и мы хотим получить все температуры в диапазоне от 15 до 25 градусов:
Пример 2: Поиск ближайшей даты
Допустим, у нас есть набор дат, и мы хотим найти ближайшую дату, которая будет после сегодняшнего дня:
#Java #Training #Medium #NavigableSet
Основные методы NavigableSet
E lower(E e)
Возвращает наибольший элемент в наборе, который меньше заданного элемента e. Если такого элемента нет, возвращает null.
NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));
System.out.println(set.lower(3)); // Output: 2
E floor(E e)
Возвращает наибольший элемент в наборе, который меньше или равен заданному элементу e. Если такого элемента нет, возвращает null.
System.out.println(set.floor(3)); // Output: 3
System.out.println(set.floor(6)); // Output: 5
E ceiling(E e)
Возвращает наименьший элемент в наборе, который больше или равен заданному элементу e. Если такого элемента нет, возвращает null.
System.out.println(set.ceiling(3)); // Output: 3
System.out.println(set.ceiling(0)); // Output: 1
E higher(E e)
Возвращает наименьший элемент в наборе, который больше заданного элемента e. Если такого элемента нет, возвращает null.
System.out.println(set.higher(3)); // Output: 4
System.out.println(set.higher(5)); // Output: null
E pollFirst() и E pollLast()
Эти методы удаляют и возвращают первый и последний элемент набора соответственно. Если набор пуст, они возвращают null.
NavigableSet<String> set = new TreeSet<>(Arrays.asList("apple", "banana", "cherry"));
System.out.println(set.pollFirst()); // Output: apple
System.out.println(set.pollLast()); // Output: cherry
System.out.println(set); // Output: [banana]NavigableSet<E> descendingSet()
Возвращает представление текущего набора в обратном порядке. Любые изменения в этом представлении будут отражаться на исходном наборе и наоборот.
NavigableSet<String> set = new TreeSet<>(Arrays.asList("apple", "banana", "cherry"));
NavigableSet<String> descendingSet = set.descendingSet();
System.out.println(descendingSet); // Output: [cherry, banana, apple]NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
Возвращает поднабор элементов от fromElement до toElement, при этом можно указать, включать ли эти элементы в поднабор.
NavigableSet<Integer> set = new TreeSet<>(Arrays.asList(1, 2, 3, 4, 5));
NavigableSet<Integer> subSet = set.subSet(2, true, 4, false);
System.out.println(subSet); // Output: [2, 3]
NavigableSet<E> headSet(E toElement, boolean inclusive)
Возвращает поднабор элементов от начала набора до toElement. Можно указать, включать ли элемент toElement в поднабор.
NavigableSet<Integer> headSet = set.headSet(4, true);
System.out.println(headSet); // Output: [1, 2, 3, 4]
NavigableSet<E> tailSet(E fromElement, boolean inclusive)
Возвращает поднабор элементов от fromElement до конца набора. Можно указать, включать ли элемент fromElement в поднабор.
NavigableSet<Integer> tailSet = set.tailSet(3, false);
System.out.println(tailSet); // Output: [4, 5]
Примеры использования NavigableSet
Пример 1: Фильтрация диапазона значений
Предположим, у нас есть набор температур за неделю, и мы хотим получить все температуры в диапазоне от 15 до 25 градусов:
NavigableSet<Integer> temperatures = new TreeSet<>(Arrays.asList(10, 15, 20, 25, 30));
NavigableSet<Integer> comfortableTemperatures = temperatures.subSet(15, true, 25, true);
System.out.println(comfortableTemperatures); // Output: [15, 20, 25]
Пример 2: Поиск ближайшей даты
Допустим, у нас есть набор дат, и мы хотим найти ближайшую дату, которая будет после сегодняшнего дня:
NavigableSet<LocalDate> dates = new TreeSet<>(Arrays.asList(
LocalDate.of(2023, 8, 20),
LocalDate.of(2023, 9, 5),
LocalDate.of(2023, 10, 10)
));
LocalDate today = LocalDate.of(2023, 8, 25);
LocalDate nextDate = dates.ceiling(today);
System.out.println(nextDate); // Output: 2023-09-05
#Java #Training #Medium #NavigableSet