TreeMap в Java
Класс TreeMap реализует интерфейс карты, аналогичный классу HashMap. Он сохраняет свои записи в порядке возрастания, отсортированные в соответствии с естественным упорядочением ключей или в соответствии с Компаратором зависит от аргумента конструктора. В отличие от LinkedHashMap и HashMap, TreeMap не использует хеширование для хранения ключей. Он использует структуру данных, называемую деревом Red-Black.
Красное - черное дерево - своеобразное самобалансирующееся двоичное дерево поиска, которое обладает следующими красно-черными свойствами:
1. Every node is either red or black. 2. Root of tree is always black. 3. Every leaf (NULL) is black. 4. If a node is red, then both its children are black. 5. Every path from root to a NULL node has same number of black nodes.
Реализация TreeMap не синхронизирована. Если несколько потоков одновременно обращаются к TreeMap, и по крайней мере один из потоков модифицирует TreeMap структурно, он должен быть синхронизирован извне. Класс TreeMap идеально подходит для перемещения ключей в отсортированном порядке. Клавиши можно сортировать с помощью интерфейса Comparable или интерфейса Comparator. Вы можете указать порядок сортировки при создании TreeMap, предоставив явный компаратор для TreeMap. Кроме того, он предоставляет методы firstKey() и lastKey() для возврата первого и последнего ключей на карте и headMap (toKey) и tailMap (fromKey) для возврата части карты, ключи которой меньше, чем toKey и больше, чем или равно от Key.
Следующая программа Java иллюстрирует несколько методов, поддерживаемых этой базой данных TreeMap:
import Java.util.*; class TestClass { public static void main (String[] args) throws Java.lang.Exception { // Как создать TreeMap? TreeMapdays = new TreeMap (); // Как добавить пары Key / Value в TreeMap? days.put(1,"Sunday"); days.put(2,"Monday"); days.put(3,"Tuesday"); days.put(4,"Wednesday"); days.put(5,"Thursday"); days.put(6,"Friday"); days.put(7,"Saturday"); // Как проходить через TreeMap? for(Map.Entry m:days.entrySet()){ System.out.println(m.getKey()+" "+m.getValue()); } // Как удалить определенный элемент из TreeMap? days.remove(3); Set > set = days.entrySet(); for (Map.Entry sg : set) { System.out.println("Key :"+sg.getKey() + " Value :"+days.get(sg.getKey())); } // Как найти ключ в TreeMap? Integer key=4; if(days.containsKey(key)){ System.out.println("Key " + key + " found"); }else{ System.out.println("Key " + key+ " does not exist"); } // Как получить ключ от его значения в TreeMap? Integer iKey= null; String value="Monday"; for(Map.Entry entry: days.entrySet()){ if(value.equals(entry.getValue())){ iKey = (Integer)entry.getKey(); break; // нарушение, потому что его одна к одной карте } } System.out.println("Found Key : "+ iKey +" value: " + value); // Как удалить весь элемент из TreeMap? days.clear(); // Как найти размер TreeMap? System.out.println("After remove: "+ days.size()); } }