Вы обычно используете HashSet или HashMap реализацию, когда вам нужно использовать Set или Map? Вы знаете про TreeMap или TreeSet? Если нет, то вам повезло, потому что мы рассмотрим, что это такое, почему и когда они могут быть полезны.

Реализация и сложность

Подобно тому, как HashSet реализуется с использованием HashMap, TreeSet реализуется с использованием TreeMap. Сам TreeMap реализован с использованием красно-черного дерева, которое представляет собой самобалансирующееся двоичное дерево поиска. Поскольку в нем используется двоичное дерево, операции put(), contains() и remove() имеют временную сложность O (log n). Кроме того, поскольку дерево сбалансировано, временная сложность наихудшего случая также составляет O (log n).

С другой стороны, HashMap имеет среднюю временную сложность O (1) для операций put(), contains() и remove(). Наихудшая временная сложность для этих операций составляет O (log n) с Java 8 и O (n) до этого.

С точки зрения пространственной сложности оба имеют сложность O (n). Однако TreeMap более экономичен, чем HashMap, потому что по умолчанию HashMap заполнен не более чем на 75%, чтобы избежать слишком большого количества коллизий. В результате остается неиспользуемое пространство. Это можно настроить с помощью коэффициента загрузки.

O (1) лучше O (log n), так зачем нам использовать что-то более медленное?

Навигация и сортировка

TreeMap и TreeSet равны Navigable и Sorted, что не относится к HashMap и HashSet. По умолчанию порядок является естественным, однако его можно изменить, указав Comparator в конструкторе.

NavigableSet

Интерфейс NavigableSet предлагает множество очень удобных методов:

  • lower(e): возвращает наибольший элемент, строго меньший, чем e, или null, если его нет
  • floor(e): то же, что и lower(e), но включает элементы, равные e
  • higher(e): возвращает наименьший элемент, строго превышающий e, или null, если его нет
  • ceiling(e): то же, что и higher(e), но включает элементы, равные e
  • pollFirst() и pollLast(): возвращает наименьший и наибольший элементы соответственно или null, если набор пуст

Давайте посмотрим на несколько примеров:

NavigableMap

NavigableMap предлагает те же методы, но с суффиксом Entry: lowerEntry(e), higherEntry(e) и т. Д. Порядок основан на ключах карты:

SortedSet

Благодаря этому интерфейсу у нас есть доступ к следующим функциям:

  • subSet(a, b): возвращает подмножество элементов, которые больше или равны a и строго меньше b.
  • headSet(e): возвращает набор элементов, которые строго меньше, чем e
  • tailSet(e): возвращает набор элементов, которые больше или равны e
  • first() и last(): возвращает наименьший и наибольший элементы соответственно

Опять же, пример, вероятно, будет иметь гораздо больше смысла:

SortedMap

Что касается NavigableMap, методы такие же, как SortedSet, но с суффиксом Map. Поведение такое же, и для упорядочивания используются ключи карты.

Итерация

Интерфейс Sorted дает одно главное преимущество TreeMap и TreeSet: итерация будет следовать отсортированному порядку. Когда дело доходит до HashSet или HashMap, порядок будет хеш-кодами, а не элементами. Это различие может быть критерием выбора одной реализации по сравнению с другой. Можно создать отсортированный контейнер из HashSet или HashMap, но сортировка обычно имеет сложность 0 (n log n).

Параллелизм

Оба TreeMap и TreeSet не являются потокобезопасными. Для обеспечения многопоточности можно использовать Collections.synchronizedNavigableMap(treeMap), Collections.synchronizedSortedMap(treeMap) или ConcurrentSkipListMap() (замените Map на Set для Sets). Он реализован с использованием списка пропуска вместо дерева, поскольку списки пропуска более эффективны в параллельных средах, но временные сложности и поведение остаются теми же.

Заключение

  • TreeMap и TreeSet более эффективны с точки зрения памяти по сравнению с их Hash аналогами. Если память важнее скорости, тогда эта структура данных может быть хорошим выбором.
  • TreeMap и TreeSet отсортированы и могут быть идеальным выбором, если вам нужно очень часто получать диапазоны или перебирать определенный порядок. Собственно, базы данных используют b-деревья в качестве индексов для ранжированных запросов по ​​тем же причинам.

Надеюсь, вы узнали что-то новое, спасибо за чтение!



Объекты-ценности спешат на помощь!
Избавьтесь от примитивной одержимости с помощью объектов-ценностей! medium.com





Книги для разработчиков программного обеспечения
5 замечательных книг, которые должен прочитать каждый инженер-программист medium.com



Некоторые ссылки