1. Обзор
В этой статье мы собираемся изучить реализацию TreeMap интерфейса карты из 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 и его внутреннюю реализацию. Поскольку он является последним в серии общих реализаций интерфейса Map, мы также кратко обсудили, где он лучше всего подходит по отношению к двум другим.
Полный исходный код всех примеров, использованных в этой статье, можно найти в проекте GitHub .