Введение
В интернете можно часто встретить вопросы про то, что такое TreeMap, как он устроен, и как им пользоваться. В данной статье я постараюсь кратко ответить на эти вопросы.Класс TreeMap расширяет класс AbstractMap и реализует интерфейс NavigatebleMap. Он создает коллекцию, которая для хранения элементов применяет дерево. Объекты сохраняются в отсортированном порядке по возрастанию. Время доступа и извлечения элементов достаточно мало, что делает класс TreeMap блестящим выбором для хранения больших объемов отсортированной информации, которая должна быть быстро найдена.
На рисунке 1 показана иерархия предков TreeMap.
Рисунок 1
TreeMap основан на Красно-Черном дереве, вследствие чего TreeMap сортирует элементы по ключу в естественном порядке или на основе заданного вами компаратора.TreeMap гарантирует скорость доступа log(n) для операций containsKey, get, put и remove.
Пример
Давайте рассмотрим простой пример использования TreeMapMap treeMap = new TreeMap<>();
treeMap.put("Bruce", "Willis");
treeMap.put("Arnold", "Schwarzenegger");
treeMap.put("Jackie", "Chan");
treeMap.put("Sylvester", "Stallone");
treeMap.put("Chuck", "Norris");
for(Map.Entry e : treeMap.entrySet()){
System.out.println(e.getKey()+" "+ e.getValue());
}
Вывод на консоль:
Arnold Schwarzenegger
Bruce Willis
Chuck Norris
Jackie Chan
Sylvester Stallone
Как видим, элементы отсортированы по ключу (Chuck Norris не первый :О).
Чтобы получить ключи и значения нужно использовать методы keySet() и values().
При попытке добавить null-элемент в TreeMap происходит исключение NullPointerException.
Конструкторы
В классе TreeMap присутствуют следующие конструкторы:1. TreeMap( )
2. TreeMap(Comparator comp)
3. TreeMap(Map m)
4. TreeMap(SortedMap sm)
Первый конструктор создает коллекцию, в которой все элементы отсортированы в натуральном порядке их ключей.
Второй конструктор создаст пустую коллекцию, элементы в которой будут отсортированы по закону, который определен в передаваемом компараторе.
Третий конструктор создаст TreeMap на основе уже имеющегося Map.
Четвертый конструктор создаст TreeMap на основе уже имеющегося SortedMap , элементы в которой будут отсортированы по закону передаваемой SortedMap .
Обратите внимание на то, что для сортировки используются ключи, а не значения.
Синхронизация
TreeMap не синхронизирован. По этому, если имеется множество потоков, работающих с данной коллекцией и хотя бы один поток может её изменять , то коллекцию нужно синхронизировать внешне.Можно воспользоваться стандартным механизмом синхронизации, при котором в качестве монитора передаться ссылка объекта, инкапсулирующий данную коллекцию. Если такого объекта нет, можно воспользоваться методом synchronizedSortedMap .
Например:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
Создание собственного порядка сортировки
Для определения собственного порядка следования элементов в коллекции, нужно реализовать интерфейс Comparator и передать объект своего компаратора в качестве конструктора TreeMappublic interface Comparator {
public int compare (Object object1, Object object2);
public boolean equals (Object object);
}
Или реализовать интерфейс Comparable у класса, который будет использоваться в качестве ключа.
public interface Comparable {
public int compareTo (Object objectToCompare);
}
Классы Integer, String, Double и т.п. реализуют интерфейс Comparable. Если вы создали собственный класс для ключей и не реализовали интерфейс Comparable (и не используете Comparator), то при попытке добавления объекта в коллекцию будет брошено исключение java.lang.ClassCastException!
Пример:
public class MyCustomKey implements Comparable{
private int value;
public MyCustomKey(int value){
this.value = value;
}
public int compareTo (MyCustomKey key){
int comparison =0;
// Note:
// Return -1 if this.value < key.value
// Return 0 if this.value = key.value
// Return 1 if this.value > key.value
// …. Реализация сравнения….
return(comparison);
}
public int hashCode(){
return(this.value *199);
}
}
Частая ошибка при использовании TreeMap, в том, что для класса ключа не определяется метод hashcode(). Если в данном случае использовать метод map.get(new MyCustomKey(
Структура данных
Как уже было сказано, TreeMap для хранения элементов применяет красно-черное дерево. Красно-черное дерево это частный случай двоичного дерева поиска.Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами.
ДДП позволяет выполнять следующие основные операции:
· Поиск вершины по ключу.
· Определение вершин с минимальным и максимальным значением ключа.
· Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.
· Вставка вершины.
· Удаление вершины.
У читателя, возможно, возникает вопрос, зачем нужны такие сложности, если можно просто хранить список пар [ключ, значение]. Ответ прост — операции с деревом работают быстрее. При реализации списком все функции требуют O(n) действий, где n — размер структуры. Операции с деревом же работают за O(h), где h — максимальная глубина дерева (глубина — расстояние от корня до вершины). В оптимальном случае, когда глубина всех листьев одинакова, в дереве будет n=2^h вершин. Значит, сложность операций в деревьях, близких к оптимуму будет O(log(n)).
Рисунок 2
В худшем случае дерево может принять вид, изображённый на рисунке 1. Сложность операций в таком случае будет как у списка.
Красно-черные деревья
Для того, чтобы ситуации как на рисунке 2 не было, применяют специальные сбалансированные деревья.Сбалансированные деревья:
1. B-дерево
2. АВЛ-дерево
3. Красно-чёрное дерево
….
Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или черный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:
1. Узел либо красный, либо чёрный.
2. Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
3. Все листья(NIL) — черные.
4. Оба потомка каждого красного узла — черные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.
Минутка философии
Некоторые считают, что красно-черные деревья это всего лишь проекция 2-3-4 деревьев в чисто бинарные, где "настоящие узлы" 2-3-4 деревьев — это черные, а подузлы с 3-мя или 4-мя потомками это красные. Если смотреть правила балансировки 2-3-4 деревьев, то они очень простые, а если смотреть правила балансировки красно-черных деревьев, то они выглядят как мантры и заклинания, где ничего непонятно. :)
Рисунок 3
Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь от корня к листу не более чем вдвое длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой 2. Кратчайшее возможное расстояние от корня до листа равно двум – когда оба узла черные. Длиннейшее расстояние от корня до листа равно четырем – узлы при этом покрашены (от корня к листу) так: красный–>черный–>красный–>черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты.
Поскольку согласно свойству 4 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться.
Если Вы с первого раза не поняли, как работает красно-черное дерево (как и я), то воспользуйтесь визуализатором по ссылке красно-черные деревья . Там пошагово рассказывают и показывают операции поиска и вставки элементов.
