Руководство Java TreeMap

TreeMap
Как TreeMap хранит данные?
Examples
TreeMap с ключом null

1. TreeMap

В этой статье мы рассмотрим класс TreeMap, который является реализацией (implementation) интерфейса Map и находится в наборе связанных классов и интерфейсов Java (Java Collection Framework).

public class TreeMap<K,V> extends AbstractMap<K,V>
                    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

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

Map<K,V>	SortedMap<K,V> NavigableMap<K,V>	TreeMap<K,V>
Дубликаты ключей не допускаются.
Может разрешить ключ null и значения null.		Допускается только ключ null, если имеется подходящий Comparator.
Порядок ключей не гарантируется.	Ключи сортируются в порядке возрастания на основе их естественного порядка или в соответствии с предоставленным Comparator.

Наследует функции интерфейса SortedMap. Все ключи of TreeMap должны быть типа Comparable (сопоставимого), или вы должны предоставить Comparator (компаратор) для TreeMap, который сравнивает ключи. В противном случае будет вызвано исключение ClassCastException. Comparator предоставляется в момент создания объекта TreeMap с помощью одного из его конструкторов.

TreeMap constructors

TreeMap()

TreeMap(Map<? extends K,? extends V> m)    

TreeMap(Comparator<? super K> comparator)

// Using the same ordering as the specified sortedMap.
TreeMap(SortedMap<K,? extends V> m)

HashMap
IdentityHashMap
WeakHashMap
LinkedHashMap
EnumMap
ConcurrentHashMap
ConcurrentSkipListMap
Map
ConcurrentMap
ConcurrentNavigableMap
SortedMap
NavigableMap

2. Как TreeMap хранит данные?

TreeMap использует comparator.compare(key1,key2) для сравнения двух ключей, если предоставляется Comparator. В противном случае он использует key1.compareTo(key2) для сравнения двух ключей. TreeMap редназначена для обеспечения того, чтобы операции по поиску, обновлению или удалению карты займет как можно меньше времени за счет уменьшения количества операций сравнения ключей. В этом разделе мы узнаем о том, как TreeMap хранит свои данные.

Entry<K,V> - это класс, используемый для хранения отображения, которое состоит из 5 свойств: key, value, parent, left, right. TreeMap управляет ссылкой на корневую Entry - root. Операции по поиску на TreeMap начнется с корневой Entry и распространится на лист дерева.

Entry<K,V>

K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;

Для удобства понимания давайте посмотрим, что происходит, когда мы добавим сопоставления к TreeMap<Integer,String>.

TreeMap<Integer, String> map = new TreeMap<>();

// keys = 5, 3, 9, 7, 1, 11.
map.put(5, "Five");
map.put(3,  "Three");
map.put(9,  "Nine");
map.put(7, "Seven");
map.put(1, "One");
map.put(11, "Eleven");

На рисунке выше показана древовидная структура of TreeMap. Первое отображение, добавленное в TreeMap, будет корнем (root) дерева, отображение с меньшим ключом будет размещено слева, а отображение с большим ключом будет размещено справа.

get(key)?

map.get(7); // key =  7

Операция поиска сопоставления всегда начинается с корневой Entry. Ключ для поиска будет сравниваться с ключом текущей Entry, если он больше, он будет сравниваться с ключом следующей Entry справа. В противном случае, если он меньше, он будет сравниваться с ключом следующей Entry слева, пока не будет найден или не достигнет листьев дерева.

remove(key)?

Далее давайте посмотрим, что делает TreeMap для удаления сопоставления.

map.remove(5); // Remove the mapping has key = 5.

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

put(key,value)?

map.put(2, "Two");

3. Examples

Как мы все знаем, класс Integer реализует interface Comparable, поэтому объекты Integer можно сравнивать друг с другом. TreeMap с ключами типа Integer не нуждается в Comparator.

TreeMapEx1.java

package org.o7planning.treemap.ex;

import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx1 {

    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}

Output:

[1, 3, 5, 7, 9, 11]
1 --> One
3 --> Three
5 --> Five
7 --> Seven
9 --> Nine
11 --> Eleven

Например: Используйте пользовательский Comparator для изменения порядка ключей.

TreeMap_reverseOrder_ex1.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMap_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeMap<Integer, String> map = new TreeMap<>(reverseOrderComparator);
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}

Output:

[11, 9, 7, 5, 3, 1]
11 --> Eleven
9 --> Nine
7 --> Seven
5 --> Five
3 --> Three
1 --> One

См. Дополнительные примеры использования пользовательского Comparator, а также инструкции по навигации, поиску ключа или сопоставлению:

4. TreeMap с ключом null

TreeMap допускает ключи null только в том случае, если она снабжена Comparator, поддерживающим сравнение ключа null с другими ключами.

TreeMap_nullKey_ex1.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}

Output:

--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Например: Напишим пользовательский Comparator, который поддерживает сравнение ключа null с другими ключами:

TreeMap_nullKey_ex2.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex2 {

    public static void main(String[] args) {  
        Comparator<String> comparator = new StringNullComparator();

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1 == o2) {
            return 0; // o1 = o2
        }
        if(o1 == null)  {
            return -1; // o1 < o2
        }
        if(o2 == null)  {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}

Output:

--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Руководство Java TreeMap

1. TreeMap

2. Как TreeMap хранит данные?

3. Examples

4. TreeMap с ключом null

Руководства Java Collections Framework

Руководства Java Collections Framework

Новейшие статьи