Рубрики
Без рубрики

Руководство по древовидной карте на Java

Краткое и практическое руководство по TreeMap на Java.

Автор оригинала: baeldung.

1. Обзор

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

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

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

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

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

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

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

@Test
public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() {
    TreeMap 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 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 , в отличие от hashmap и linkedhashmap, нигде не использует принцип хеширования, поскольку он не использует массив для хранения своих записей.

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

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

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

@Test
public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() {
    TreeMap 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 хранит все свои записи в отсортированном порядке. Из-за этого атрибута древовидных карт мы можем выполнять такие запросы, как: найти “самый большой” и “самый маленький”, найти все ключи меньше или больше определенного значения и т. Д.

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

@Test
public void givenTreeMap_whenPerformsQueries_thenCorrect() {
    TreeMap 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 keysLessThan3 = map.headMap(3).keySet();
    Set 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 реализует навигационную карту интерфейс и основывает свою внутреннюю работу на принципах красно-черных деревьев :

public class TreeMap extends AbstractMap
  implements NavigableMap, Cloneable, java.io.Serializable

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Читайте ещё по теме: