集合13-TreeMap使用场景简析

0- 继承结构

1- 简介

• TreeMap的底层实现原理

基于红黑树实现的排序Map

• TreeMap增删改查的时间复杂度

TreeMap的增删改查和统计相关的操作的时间复杂度都为 O(logn)

• TreeMap的key和value的要求

1. 由于实现了Map接口，则key的值不允许重复（重复则覆盖），也不允许为null，按照key的自然顺序排序或者Comparator接口指定的排序方法进行排序。

2. value允许重复，也允许为null，当key重复时，会覆盖此value值。

2- TreeMap的使用场景

考虑如下场景：

• 需要基于排序的统计功能：

由于TreeMap是基于红黑树的实现的排序Map，对于增删改查以及统计的时间复杂度都控制在O(logn)的级别上，相对于HashMap和LikedHashMap的统计操作的(最大的key，最小的key，大于某一个key的所有Entry等等)时间复杂度O(n)具有较高时间效率。

• 需要快速增删改查的存储功能：

相对于HashMap和LikedHashMap 这些 hash表的时间复杂度O(1)（不考虑冲突情况），TreeMap的增删改查的时间复杂度为O(logn)就显得效率较低。

• 需要快速增删改查而且需要保证遍历和插入顺序一致的存储功能：

相对于HashMap和LikedHashMap 这些 hash表的时间复杂度O(1)（不考虑冲突情况），TreeMap的增删改查的时间复杂度为O(logn)就显得效率较低。但是HashMap并不保证任何顺序性。LikedHashMap额外保证了Map的遍历顺序与put顺序一致的有序性。

综上：场景1适合使用TreeMap，场景2适合使用HashMap，场景3适合使用LikedHashMap，需要注意它们都是非线程安全的，当在并发场景下可以使用其他并发集合或者调用者在调用层去控制并发使得操作串行执行。

3- TreeMap的方法列表

http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

4- 按照Value进行排序

import java.util.*;
/**
 * @author zhanglbjames@163.com
 * @version Created on 2017/6/9.
 */
public class TestTreeMap {
    public static void main(String[] args){
        // 创建hashmap
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        hashMap.put(1,5);
        hashMap.put(2,4);
        hashMap.put(3,3);
        hashMap.put(4,2);
        hashMap.put(5,1);
        hashMap.put(7,1);

        // 创建Value比较器
        ValueComparator valueComparator = new ValueComparator(hashMap);
        // 创建TreeMap
        TreeMap<Integer,Integer> treeMap = new TreeMap<>(valueComparator);
        //TreeMap<Integer,Integer> treeMap = new TreeMap<>();

        // 将HashMap中所有数据放入 TreeMap中
        //treeMap.putAll(hashMap);
        // 为了观察每次变化，进行分开put

        System.out.println("--------------------- put into TreeMap --------------------");
        System.out.println(treeMap.put(1,5));
        System.out.println(treeMap.put(2,4));
        System.out.println(treeMap.put(3,3));
        System.out.println(treeMap.put(4,2));
        System.out.println(treeMap.put(5,1));
        System.out.println(treeMap.put(7,1));

        System.out.println("---------------------- sort result -------------------------");
        // 迭代TreeMap的结果
        Iterator<Map.Entry<Integer,Integer>> iterator = treeMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer,Integer> entry = iterator.next();
            System.out.println("key : "+entry.getKey()+" value : " + entry.getValue());
        }
        System.out.println("after sorted, the size : " +treeMap.size());
    }
}

class ValueComparator implements Comparator<Integer> {

    // 一定要持有能根据Key的值找到对应Value值的Map，只有这样才能在compare方法中比较key对应的value
    // 默认传入的比较器都是针对key的比较器，如果想修改为Value的比较器需要通过持有k-v的Map
    private Map<Integer,Integer> map;

    public ValueComparator(Map map) {
        this.map = map;
    }
    @Override
    public int compare(Integer o1, Integer o2) {

        if (map.get(o1) > map.get(o2)){
            return 1;
        }else if(map.get(o1) < map.get(o2)){
            return -1;
        }
        // 如果比较value，相同的value的Key将会发生合并，即Value的值是不允许重复的
        // 必须返回 0，否则get方法将返回null
        else return 0;
    }
}

输出结果：

--------------------- put into TreeMap --------------------
null
null
null
null
null
1
---------------------- sort result -------------------------
key : 5 value : 1
key : 4 value : 2
key : 3 value : 3
key : 2 value : 4
key : 1 value : 5
after sorted, the size : 5

说明：

1. TreeMap默认是根据Key来比较来排序的

2. TreeMap的构造方法允许使用指定的比较器来比较

3. 可以实现通过比较Value来排序，通过指定比较器来实现，注意比较器的compare方法接收的两个参数都是Key，必须通过Key来获取对应的Value来比较
   才能实现按照Value来排序，否则还是按照key来排序的。

4. TreeMap底层是红黑树来实现的，红黑树不允许重复的比较关键字， 所以如果比较器（如果没有指定比较器，则默认使用Key的自然顺序或者Key实现的比较接口方法来比较）的比较结果为0，即比较关键字相等，则将会发生覆盖value，但是key不变的情况。
   具体如下：

• 如果按照Key来排序，则相同的Key的Value值将会发生覆盖，即value值等于最近put方法的指定的value值，Key不变；
• 如果按照Value来排序，则相同的Value的key将会发生覆盖，注意和1的区别：key还是原来的key,value还是原来的value，只是进行了一次没有意义的value = value 的等值赋值的过程。

TreeMap红黑树部分方法详解参考链接