«1. Обзор

В этой статье мы собираемся изучить реализацию TreeMap интерфейса Map из Java Collections Framework (JCF).

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

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

Упомянутые статьи настоятельно рекомендуется прочитать, прежде чем приступить к этой.

2. Сортировка по умолчанию в TreeMap

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

Давайте посмотрим на естественный порядок в тесте: 

@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");

    assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString());
}

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

Точно так же, когда мы используем строки, они будут отсортированы в их естественном порядке, то есть в алфавитном порядке: 

@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() {
    TreeMap<String, String> map = new TreeMap<>();
    map.put("c", "val");
    map.put("b", "val");
    map.put("a", "val");
    map.put("e", "val");
    map.put("d", "val");

    assertEquals("[a, b, c, d, e]", map.keySet().toString());
}

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

3. Пользовательская сортировка в TreeMap

Если нас не устраивает естественное упорядочение TreeMap, мы также можем определить собственное правило упорядочения с помощью компаратора при построении древовидной карты.

В приведенном ниже примере мы хотим, чтобы целочисленные ключи были упорядочены в порядке убывания: 

@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
    TreeMap<Integer, String> map = 
      new TreeMap<>(Comparator.reverseOrder());
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");
        
    assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString());
}

Хэш-карта не гарантирует порядок хранения ключей и, в частности, не гарантирует, что этот порядок останется неизменным в течение время, но древовидная карта гарантирует, что ключи всегда будут отсортированы в соответствии с указанным порядком.

4. Важность сортировки TreeMap

Теперь мы знаем, что TreeMap хранит все свои записи в отсортированном порядке. Из-за этого атрибута древовидных карт мы можем выполнять такие запросы, как; найти «самый большой», найти «самый маленький», найти все ключи меньше или больше определенного значения и т. д.

Приведенный ниже код охватывает лишь небольшой процент этих случаев: 

@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
    TreeMap<Integer, String> map = new TreeMap<>();
    map.put(3, "val");
    map.put(2, "val");
    map.put(1, "val");
    map.put(5, "val");
    map.put(4, "val");
        
    Integer highestKey = map.lastKey();
    Integer lowestKey = map.firstKey();
    Set<Integer> keysLessThan3 = map.headMap(3).keySet();
    Set<Integer> keysGreaterThanEqTo3 = map.tailMap(3).keySet();

    assertEquals(new Integer(5), highestKey);
    assertEquals(new Integer(1), lowestKey);
    assertEquals("[1, 2]", keysLessThan3.toString());
    assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString());
}

5. Внутренний Реализация TreeMap

TreeMap реализует интерфейс NavigableMap и основывает свою внутреннюю работу на принципах красно-черных деревьев: 

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

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

Во-первых, красно-черное дерево — это структура данных, состоящая из узлов; представьте перевернутое манговое дерево с корнями в небе и ветвями, растущими вниз. Корень будет содержать первый элемент, добавленный в дерево.

Правило состоит в том, что, начиная с корня, любой элемент в левой ветви любого узла всегда меньше, чем элемент в самом узле. Те, что справа, всегда больше. То, что определяет больше или меньше, определяется естественным порядком элементов или определенным компаратором при построении, как мы видели ранее.

Это правило гарантирует, что элементы карты дерева всегда будут отсортированы и предсказуемы.

Во-вторых, красно-черное дерево — это самобалансирующееся бинарное дерево поиска. Этот атрибут и описанное выше гарантируют, что основные операции, такие как поиск, получение, размещение и удаление, занимают логарифмическое время O(log n).

Ключевым моментом здесь является самобалансирование. Продолжая вставлять и удалять записи, представьте, что дерево становится длиннее с одной стороны и короче с другой.

Это будет означать, что операция займет меньше времени на более короткой ветке и больше времени на ветке, которая находится дальше всего от корня, чего мы бы не хотели.

Поэтому об этом позаботились при проектировании красно-черных деревьев. Для каждой вставки и удаления максимальная высота дерева на любом ребре поддерживается на уровне O (log n), т. е. дерево непрерывно уравновешивается.

«Так же, как хэш-карта и связанная хэш-карта, древовидная карта не синхронизируется, и поэтому правила ее использования в многопоточной среде аналогичны правилам в двух других реализациях карты.

6. Выбор правильной карты

Изучив реализации HashMap и LinkedHashMap ранее, а теперь и TreeMap, важно провести краткое сравнение между тремя, чтобы понять, какая из них подходит.

Хэш-карта хороша как реализация карты общего назначения, которая обеспечивает быстрое хранение и операции поиска. Однако он терпит неудачу из-за хаотичного и беспорядочного расположения записей.

Это приводит к плохой работе в сценариях с большим количеством итераций, поскольку вся емкость базового массива влияет на обход, а не только на количество записей.

Связанная хеш-карта обладает хорошими атрибутами хэш-карты и упорядочивает записи. Он работает лучше при большом количестве итераций, поскольку учитывается только количество записей независимо от емкости.

Древовидная карта выводит упорядочение на новый уровень, предоставляя полный контроль над тем, как должны быть отсортированы ключи. С другой стороны, он предлагает худшую общую производительность, чем два других варианта.

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

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

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

Полный исходный код всех примеров, использованных в этой статье, можно найти в проекте GitHub.