/ Java  

Java TreeMap

TreeMap

In the Map collection framework, in addition to HashMap, TreeMap is also one of the collection objects commonly used in work.

Compared with HashMap, TreeMap is a Map collection that can compare elements, and sorts the key value. For comparasion, you can use the natural order of the elements, or you can use a custom comparator in the collection to sort;

Unlike HashMap‘s hash mapping, the underlying structure of the TreeMap is a tree structure. As for the specific form, you can simply understand it as an inverted tree — roots up, leaves down. In computer terms, TreeMap implements the structure of a red-black tree, forming a binary tree.



TreeMap inherits AbstractMap and implements Map, Cloneable, NavigableMap, and Serializable interfaces.

  1. TreeMap inherits AbstractMap, and AbstractMap implements the Map interface and implements the methods defined in the Map interface, reducing the complexity of subclass inheritance;

  2. TreeMap implements the Map interface and becomes a member of the Map framework, which can store elements in the form of key-value;

  3. TreeMap implements the NavigableMap interface, which means that it has stronger element searching capabilities;

  4. TreeMap implements the Cloneable interface and implements the clone() method, so it can be cloned;

  5. TreeMap implements the Java.io.Serializable interface, supports serialization operations, and can be transmitted through the Hessian protocol;

For Cloneable, Serializable, we are familiar with it. Basically, every class in the Java collection framework will implement these 2 interfaces. But what does the NavigableMap interface do and what functions does it define? Next, let’s take a look at the source code of NavigableMap!



Let’s first introduce the SortedMap interface in the NavigableMap system:

For SortedMap, this class is the parent interface in the TreeMap, and it is also the most critical interface different from the HashMap system.

The main reason is the first method defined in the SortedMap interface: Comparator<?Super K> comparator();

With the comparator, the inserted elements can be sorted.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public interface SortedMap<K,V> extends Map<K,V> {
    
    //Returns the element comparator. If the order is natural, return null;
    Comparator<? super K> comparator();
    
    //Returns the collection from `fromKey` to `toKey`: with head but no tail
    java.util.SortedMap<K,V> subMap(K fromKey, K toKey);

    //Returns the collection from head to `toKey`: without 'toKey'
    java.util.SortedMap<K,V> headMap(K toKey);

    //Returns the collection from `fromKey` to tail: with 'fromKey'
    java.util.SortedMap<K,V> tailMap(K fromKey);
    
    //Returns the first element in the collection
    K firstKey();
   
    //Returns the last element in the collection
    K lastKey();
    
    //Returns all keys in the collection
    Set<K> keySet();
    
    //Returns all values in the collection:
    Collection<V> values();
    
    //Returns key-value map of elements
    Set<Map.Entry<K, V>> entrySet();
}

The NavigableMap interface is a further extension of SortedMap: it mainly adds search and retrieval operations for elements in the collection, such as returning elements in a range in the collection, returning elements less than a certain value, and so on.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public interface NavigableMap<K,V> extends SortedMap<K,V> {

    //Returns the first element less than the key
    Map.Entry<K,V> lowerEntry(K key);

    //Returns the first key less than the key:
    K lowerKey(K key);

    //Returns the first element less than or equal to the key
    Map.Entry<K,V> floorEntry(K key);

    //Returns the first key less than or equal to the key
    K floorKey(K key);

    //Returns the first element greater than or equal to the key
    Map.Entry<K,V> ceilingEntry(K key);

    //Returns the first key greater than or equal to the key
    K ceilingKey(K key);

    //Returns the first element greater than the key
    Map.Entry<K,V> higherEntry(K key);

    //Returns the first key greater than the key:
    K higherKey(K key);

    //Returns the first element
    Map.Entry<K,V> firstEntry();

    //Returns the last element
    Map.Entry<K,V> lastEntry();

    //Returns the first element, and delete it from the collection
    Map.Entry<K,V> pollFirstEntry();

    //Returns the last element, and delete it from the collection
    Map.Entry<K,V> pollLastEntry();

    //Returns the Map collection in reverse order
    java.util.NavigableMap<K,V> descendingMap();

    NavigableSet<K> navigableKeySet();

    //Returns keys in reverse order in the collection:
    NavigableSet<K> descendingKeySet();

    java.util.NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                       K toKey, boolean toInclusive);

    java.util.NavigableMap<K,V> headMap(K toKey, boolean inclusive);

    java.util.NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);

    SortedMap<K,V> subMap(K fromKey, K toKey);

    SortedMap<K,V> headMap(K toKey);

    SortedMap<K,V> tailMap(K fromKey);
}

In fact, the purpose of NavigableMap is very simple and straightforward, which is to enhance the search and retrieval functions for the elements in the collection. When the subclass TreeMap is implemented, the above functions are naturally obtained;

TreeMap has the following characteristics:

  • Duplicate keys are not allowed;
  • Can insert null key, null value;
  • Can sort elements;
  • Unordered collection (insertion and traversal order are inconsistent);

TreeMap basic operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public class TreeMapOperations {
    public static void main(String[] agrs){
        //Create TreeMap：
        TreeMap<String,Integer> treeMap = new TreeMap<String,Integer>();

        //Add elements
        treeMap.put("hello",1);
        treeMap.put("world",2);
        treeMap.put("i",3);
        treeMap.put("am",4);
        treeMap.put("a",4);
        treeMap.put("developer",4);

        //Traverse elements
        Set<Map.Entry<String,Integer>> entrySet = treeMap.entrySet();
        for(Map.Entry<String,Integer> entry : entrySet){
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }

        //get all keys
        Set<String> keySet = treeMap.keySet();
        for(String strKey : keySet){
            System.out.println("key:" + strKey);
        }

        //get all values:
        Collection<Integer> valueList = treeMap.values();
        for(Integer intValue:valueList){
            System.out.println("values" + intValue);
        }

        //get elements
        //get element whose key is "developer"
        Integer getValue = treeMap.get("developer");
        //get first key
        String firstKey = treeMap.firstKey();
        //get last key
        String lastKey =treeMap.lastKey();
        //get first element whose key is less than "developer"
        String lowerKey =treeMap.lowerKey("developer");
        //get first element whose key is greater than "developer"
        String ceilingKey =treeMap.ceilingKey("developer");
        //get collections whose key is from "i"到"a"的元素
        SortedMap<String,Integer> sortedMap =treeMap.subMap("i","a");

        //delete elemetns
        //delete element whose key is "developer"
        Integer removeValue = treeMap.remove("developer");
        // clear collection
        treeMap.clear(); 

        // if collection is empty
        boolean isEmpty = treeMap.isEmpty();
        //if collection contains element whose key is "developer"
        boolean isContain = treeMap.containsKey("developer");
    }
}

TreeMap sorting

In the previous section, the code showed the simple use of TreeMap. In the first section, I mentioned that TreeMap is a collection that can sort elements. So how to sort it?

Use natural order of elements

When using natural order sorting, there are two cases: one is the object defined by Jdk, and the other is the object we define.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class SortedObject implements Comparable<SortedObject> {
    private int age;

    public SortedObject(int age){
        this.age = age;
    }
    
    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    //implement compareTo(T o) method：
    public int compareTo(SortedObject sortedObject) {
        int num = this.age - sortedObject.getAge();
        if(num==0){
            return 0;
        }else if(num>0){
            return 1;
        }else{
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //Natural order
        naturalSort();
    }
    
    public static void naturalSort(){
        //First case: Integer object
        TreeMap<Integer,String> treeMapFirst = new TreeMap<Integer, String>();
        treeMapFirst.put(1,"developer");
        treeMapFirst.put(6,"developer");
        treeMapFirst.put(3,"developer");
        treeMapFirst.put(10,"developer");
        treeMapFirst.put(7,"developer");
        treeMapFirst.put(13,"developer");
        System.out.println(treeMapFirst.toString());

        //Second case: SortedObject object
        TreeMap<SortedObject,String> treeMapSecond = new TreeMap<SortedObject, String>();
        treeMapSecond.put(new SortedObject(10),"developer");
        treeMapSecond.put(new SortedObject(1),"developer");
        treeMapSecond.put(new SortedObject(13),"developer");
        treeMapSecond.put(new SortedObject(4),"developer");
        treeMapSecond.put(new SortedObject(0),"developer");
        treeMapSecond.put(new SortedObject(9),"developer");
        System.out.println(treeMapSecond.toString());
    }
}

In the natural order comparison, the elements being compared need to implement the Comparable interface, otherwise when adding an element to the collection will have “java.lang.ClassCastException: com.jiaboyan.collection.map.SortedObject cannot be cast to java.lang.Comparable “ exception;

This is because when the put() method is called, the element will be converted into a Comparable type object, so when the element passed in does not implement the Comparable interface, it cannot be converted and an exception will be reported;

Use custom comparator

To use a custom comparator for sorting, you need to pass the custom comparator object to the TreeMap constructor when you create the TreeMap object;

A custom comparator object needs to implement the Comparator interface and implement the compare method compare(T o1, T o2);

It is worth noting that if you use a custom comparator to sort, the compared objects no longer need to implement the Comparable interface;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class SortedObject {
    private int age;

    public SortedObject(int age){
        this.age = age;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

public class SortedObjectComparator implements Comparator<SortedObject> {
    public int compare(SortedObject sortedTest1, SortedObject sortedTest2) {
        int num = sortedTest1.getAge() - sortedTest2.getAge();

        if(num==0){
            return 0;
        }else if(num>0){
            return 1;
        }else{
            return -1;
        }
    }
}

public class TreeMapTest {
    public static void main(String[] agrs){
        //custom comparator
        customSort();
    }

    public static void customSort(){
        TreeMap<SortedObject,String> treeMap = new TreeMap<SortedObject, String>(new SortedObjectComparator());

        treeMap.put(new SortedObject(10),"hello");
        treeMap.put(new SortedObject(21),"my");
        treeMap.put(new SortedObject(15),"name");
        treeMap.put(new SortedObject(2),"is");
        treeMap.put(new SortedObject(1),"nick");
        treeMap.put(new SortedObject(7),"li");
        System.out.println(treeMap.toString());
    }
}

This is the basic operation and usage of TreeMap. I will post another blog to look at TreeMap‘s source code in Java.