Интерфейс Map, который применяется в языке Java для создания словарей, не предусматривает никаких возможностей для сортировки. Но Java также предоставляет ряд
дополнительных интерфейсов: SortedMap и NavigableMap
Интерфейс SortedMap расширяет Map и позволяет обеспечить полное упорядочение своих ключей. По умолчанию элементы упорядочиваются в соответствии с естественным порядком
ключей (по возрастанию) или с помощью компаратора. Этот порядок, например, отражается при переборе коллекции.
SortedMap добавляет ряд методов:
K firstKey(): возвращает ключ первого элемента коллекции
K lastKey(): возвращает ключ последнего элемента коллекции
SortedMap<K, V> headMap(K end): возвращает объект SortedMap, который содержит все элементы оригинального SortedMap вплоть до элемента с ключом end
SortedMap<K, V> tailMap(K start): возвращает объект SortedMap, который содержит все элементы оригинального SortedMap, начиная с
элемента с ключом start
SortedMap<K, V> subMap(K start, K end): возвращает объект SortedMap, которые содержит все элементы оригинального
SortedMap вплоть от элемента с ключом start до элемента с ключом end
Интерфейс NavigableMap расширяет интерфейс SortedMap и обеспечивает возможность получения элементов коллекции относительно других элементов (условно говоря, навигацию).
Его основные методы:
Map.Entry<K, V> ceilingEntry(K key): возвращает элемент с наименьшим ключом k, который больше или равен ключу key
(k >=key). Если такого ключа нет, то возвращается null.
Map.Entry<K, V> floorEntry(K key): возвращает элемент с наибольшим ключом k, который меньше или равен ключу key (k <=key).
Если такого ключа нет, то возвращается null.
Map.Entry<K, V> higherEntry(K key): возвращает элемент с наименьшим ключом k, который больше ключа key (k >key).
Если такого ключа нет, то возвращается null.
Map.Entry<K, V> lowerEntry(K key): возвращает элемент с наибольшим ключом k, который меньше ключа key (k <key).
Если такого ключа нет, то возвращается null.
Map.Entry<K, V> firstEntry(): возвращает первый элемент коллекции
Map.Entry<K, V> lastEntry(): возвращает последний элемент коллекции
Map.Entry<K, V> pollFirstEntry(): возвращает и одновременно удаляет первый элемент из коллекции
Map.Entry<K, V> pollLastEntry(): возвращает и одновременно удаляет последний элемент из коллекции
K ceilingKey(K key): возвращает наименьший ключ k, который больше или равен ключу key (k >=key). Если такого ключа нет, то возвращается null.
K floorKey(K key): возвращает наибольший ключ k, который меньше или равен ключу key (k <=key). Если такого ключа нет, то возвращается null.
K lowerKey(K key): возвращает наибольший ключ k, который меньше ключа key (k <key). Если такого ключа нет, то возвращается null.
K higherKey(K key): возвращает наименьший ключ k, который больше ключа key (k >key). Если такого ключа нет, то возвращается null.
NavigableSet<K> descendingKeySet(): возвращает объект NavigableSet, который содержит все ключи коллекции в обратном порядке
NavigableMap<K, V> descendingMap(): возвращает коллекцию NavigableMap, которое содержит все элементы в обратном порядке
NavigableSet<K> navigableKeySet(): возвращает объект NavigableSet, который содержит все ключи коллекции
NavigableMap<K, V> headMap(K upperBound, boolean incl): возвращает коллекцию NavigableMap, которое содержит все
элементы оригинальной коллекции NavigableMap вплоть от элемента с ключом upperBound. Параметр incl при значении true указывает, что элемент с ключом upperBound также включается в выходной набор.
NavigableMap<K, V> tailMap(K lowerBound, boolean incl): возвращает коллекцию NavigableMap, которое содержит все
элементы оригинальной коллекции NavigableMap, начиная с элемента с ключом lowerBound. Параметр incl при значении true указывает, что элемент с ключом lowerBound также включается в выходной набор.
NavigableMap<K, V> subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): возвращает коллекцию
NavigableMap, которое содержит все
элементы оригинальной коллекции NavigableMap от элемента с ключом lowerBound до элемента с ключом upperBound. Параметры lowIncl и highIncl
при значении true включают в выходной набор элементы с ключами lowerBound и upperBound соответственно.
Встроенной реализацией выше упомянутых интерфейсов является класс TreeMap<K, V>. Он представляет коллекцию в виде дерева, где все элементы отсортированы.
Этот класс наследуется от класса AbstractMap и реализует интерфейс NavigableMap, а следовательно, также и
интерфейсы SortedMap и Map. Поэтому для управления элементами в дереве можно использовать методы интерфейса Map. Но в отличие от коллекции HashMap в TreeMap все объекты автоматически сортируются по возрастанию их ключей.
Класс TreeMap имеет следующие конструкторы:
TreeMap(): создает пустое коллекцию в виде дерева
TreeMap(Map<? extends K, ? extends V> map): создает дерево, в которое добавляет все элементы из коллекции map
TreeMap(SortedMap<K, ? extends V> smap): создает дерево, в которое добавляет все элементы из коллекции smap
TreeMap(Comparator<? super K> comparator): создает пустое дерево, где все добавляемые элементы впоследствии будут
отсортированы компаратором.
Элементы дерева должны реализовать интерфейс Comparable() для сортировки, либо необходимо предоставлять компаратор через последнюю версию конструктора. При этом порядок,
поддерживаемый в TreeMap, (независимо от того, предоставлен ли явный компаратор), должен быть согласован с equals(), чтобы эта сортированная
коллекция правильно реализовала интерфейс Map. Примеры создания дерева:
import java.util.Map;
import java.util.TreeMap;
public class Program{
public static void main(String[] args) {
// пустое дерево
var treeMap = new TreeMap<String,String>();
System.out.println(treeMap); // {}
// дерево на основе другого словаря
var dict = new TreeMap<String,String>(
Map.ofEntries(
Map.entry("+79876543210", "Tom"),
Map.entry("+79666543210", "Bob"),
Map.entry("+79176543210", "Sam"),
Map.entry("+79276543210", "Alice")
));
System.out.println(dict); // {blue=синий, green=зеленый, red=красный, yellow=желтый}
}
}
Обратите внимание на вывод второго дерева-словаря - dict:
{blue=синий, green=зеленый, red=красный, yellow=желтый}
Вне зависимости в каком порядке объекты были добавлены в дерево, они упорядочиваются по возрастанию. Так, в данном случае у нас переменная dict представляет условный словарь, а TreeMap позволяет
упорядочить данные словаря по возрастанию.
Добавление элементов:
import java.util.Map;
import java.util.TreeMap;
public class Program{
public static void main(String[] args) {
// пустое дерево
var dict = new TreeMap<String,String>();
// добавляем в него элементы
dict.put("red", "красный");
dict.put("green", "зеленый");
dict.put("blue", "синий");
System.out.println(dict); // {blue=синий, green=зеленый, red=красный}
// добавляем другой словарь с данными
var map = Map.ofEntries(
Map.entry("yellow", "желтый"),
Map.entry("black", "черный")
);
dict.putAll(map);
System.out.println(dict); // {black=черный, blue=синий, green=зеленый, red=красный, yellow=желтый}
}
}
Получение элементов:
import java.util.Map;
import java.util.Set;
import java.util.Collection;
import java.util.TreeMap;
public class Program{
public static void main(String[] args) {
// пустой словарь
var dict = new TreeMap<String,String>(
Map.ofEntries(
Map.entry("red", "красный"),
Map.entry("green", "зеленый"),
Map.entry("yellow", "желтый"),
Map.entry("blue", "синий"),
Map.entry("black", "черный")
)
);
// перебор элементов
for(var word : dict.entrySet()){
System.out.printf("%s: %s \n", word.getKey(), word.getValue());
}
// получим объект по ключу "red"
String red = dict.get("red");
System.out.println("`red` переводится как `" + red + "`"); // `red` переводится как `красный`
// получим весь набор ключей
Set<String> keys = dict.keySet();
System.out.println(keys); // [black, blue, green, red, yellow]
// получить набор всех значений
Collection<String> values = dict.values();
System.out.println(values); // [черный, синий, зеленый, красный, желтый]
// получаем все объекты, которые стоят начиная с объекта с ключом "green"
Map<String, String> afterGreen = dict.tailMap("green");
System.out.println(afterGreen); // {green=зеленый, red=красный, yellow=желтый}
// получаем все объекты, которые стоят до объекта с ключом "green"
Map<String, String> beforeGreen = dict.headMap("green");
System.out.println(beforeGreen); // {black=черный, blue=синий}
// получим последний элемент дерева
Map.Entry<String, String> lastItem = dict.lastEntry();
System.out.println(lastItem); // yellow=желтый
}
}
Изменение и удаление элементов:
import java.util.Map;
import java.util.TreeMap;
public class Program{
public static void main(String[] args) {
// пустой словарь
var dict = new TreeMap<String,String>(
Map.ofEntries(
Map.entry("red", "красный"),
Map.entry("green", "зеленый"),
Map.entry("yellow", "желтый"),
Map.entry("blue", "синий"),
Map.entry("black", "черный")
)
);
// меняем по ключу "red" значение на "червонный"
dict.replace("red", "червонный");
System.out.println(dict); // {black=черный, blue=синий, green=зеленый, red=червонный, yellow=желтый}
// меняем по ключу "red" значение на "алый", только если значение "красный"
dict.replace("red", "алый", "красный");
// удаляем yellow
dict.remove("yellow");
System.out.println(dict); // {black=черный, blue=синий, green=зеленый, red=червонный}
// получаем с удалением первый элемент
Map.Entry<String, String> firstWord = dict.pollFirstEntry();
System.out.println(firstWord); // black=черный
// получаем с удалением последний элемент
Map.Entry<String, String> lastWord = dict.pollLastEntry();
System.out.println(lastWord); // red=червонный
// удаляем все элементы
dict.clear();
System.out.println(dict); // {}
}
}
