0- 繼承結(jié)構(gòu)
1- 簡(jiǎn)介
- TreeMap的底層實(shí)現(xiàn)原理
基于紅黑樹(shù)實(shí)現(xiàn)的排序Map
- TreeMap增刪改查的時(shí)間復(fù)雜度
TreeMap的增刪改查和統(tǒng)計(jì)相關(guān)的操作的時(shí)間復(fù)雜度都為 O(logn)
- TreeMap的key和value的要求
- 由于實(shí)現(xiàn)了Map接口，則key的值不允許重復(fù)（重復(fù)則覆蓋）丧慈，也不允許為null扫茅，按照key的自然順序排序或者Comparator接口指定的排序方法進(jìn)行排序。
- value允許重復(fù)，也允許為null硅卢，當(dāng)key重復(fù)時(shí)低飒，會(huì)覆蓋此value值。
2- TreeMap的使用場(chǎng)景
考慮如下場(chǎng)景：
- 需要基于排序的統(tǒng)計(jì)功能：
由于TreeMap是基于紅黑樹(shù)的實(shí)現(xiàn)的排序Map桑驱，對(duì)于增刪改查以及統(tǒng)計(jì)的時(shí)間復(fù)雜度都控制在O(logn)的級(jí)別上竭恬，相對(duì)于HashMap和LikedHashMap的統(tǒng)計(jì)操作的(最大的key跛蛋，最小的key，大于某一個(gè)key的所有Entry等等)時(shí)間復(fù)雜度O(n)具有較高時(shí)間效率痊硕。
- 需要快速增刪改查的存儲(chǔ)功能：
相對(duì)于HashMap和LikedHashMap 這些 hash表的時(shí)間復(fù)雜度O(1)（不考慮沖突情況）赊级，TreeMap的增刪改查的時(shí)間復(fù)雜度為O(logn)就顯得效率較低。
- 需要快速增刪改查而且需要保證遍歷和插入順序一致的存儲(chǔ)功能：
相對(duì)于HashMap和LikedHashMap 這些 hash表的時(shí)間復(fù)雜度O(1)（不考慮沖突情況）寿桨，TreeMap的增刪改查的時(shí)間復(fù)雜度為O(logn)就顯得效率較低此衅。但是HashMap并不保證任何順序性。LikedHashMap額外保證了Map的遍歷順序與put順序一致的有序性亭螟。
綜上：場(chǎng)景1適合使用TreeMap挡鞍，場(chǎng)景2適合使用HashMap，場(chǎng)景3適合使用LikedHashMap预烙，需要注意它們都是非線(xiàn)程安全的墨微，當(dāng)在并發(fā)場(chǎng)景下可以使用其他并發(fā)集合或者調(diào)用者在調(diào)用層去控制并發(fā)使得操作串行執(zhí)行。
3- TreeMap的方法列表
http://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
4- 按照Value進(jìn)行排序
import java.util.*;
/**
* @author zhanglbjames@163.com
* @version Created on 2017/6/9.
*/
public class TestTreeMap {
public static void main(String[] args){
// 創(chuàng)建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);
// 創(chuàng)建Value比較器
ValueComparator valueComparator = new ValueComparator(hashMap);
// 創(chuàng)建TreeMap
TreeMap<Integer,Integer> treeMap = new TreeMap<>(valueComparator);
//TreeMap<Integer,Integer> treeMap = new TreeMap<>();
// 將HashMap中所有數(shù)據(jù)放入 TreeMap中
//treeMap.putAll(hashMap);
// 為了觀察每次變化扁掸，進(jìn)行分開(kāi)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的結(jié)果
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> {
// 一定要持有能根據(jù)Key的值找到對(duì)應(yīng)Value值的Map翘县，只有這樣才能在compare方法中比較key對(duì)應(yīng)的value
// 默認(rèn)傳入的比較器都是針對(duì)key的比較器，如果想修改為Value的比較器需要通過(guò)持有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將會(huì)發(fā)生合并锈麸，即Value的值是不允許重復(fù)的
// 必須返回 0，否則get方法將返回null
else return 0;
}
}
輸出結(jié)果：
--------------------- 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
說(shuō)明：
TreeMap默認(rèn)是根據(jù)Key來(lái)比較來(lái)排序的
TreeMap的構(gòu)造方法允許使用指定的比較器來(lái)比較
可以實(shí)現(xiàn)通過(guò)比較Value來(lái)排序牺蹄，通過(guò)指定比較器來(lái)實(shí)現(xiàn)忘伞，注意比較器的compare方法接收的兩個(gè)參數(shù)都是Key，必須通過(guò)Key來(lái)獲取對(duì)應(yīng)的Value來(lái)比較
才能實(shí)現(xiàn)按照Value來(lái)排序沙兰，否則還是按照key來(lái)排序的氓奈。TreeMap底層是紅黑樹(shù)來(lái)實(shí)現(xiàn)的，紅黑樹(shù)不允許重復(fù)的比較關(guān)鍵字鼎天， 所以如果比較器（如果沒(méi)有指定比較器舀奶，則默認(rèn)使用Key的自然順序或者Key實(shí)現(xiàn)的比較接口方法來(lái)比較）的比較結(jié)果為0，即比較關(guān)鍵字相等斋射，則將會(huì)發(fā)生覆蓋value育勺，但是key不變的情況。
具體如下：
- 如果按照Key來(lái)排序罗岖，則相同的Key的Value值將會(huì)發(fā)生覆蓋怀大，即value值等于最近put方法的指定的value值，Key不變呀闻；
- 如果按照Value來(lái)排序化借，則相同的Value的key將會(huì)發(fā)生覆蓋，注意和1的區(qū)別：key還是原來(lái)的key,value還是原來(lái)的value捡多，只是進(jìn)行了一次沒(méi)有意義的value = value 的等值賦值的過(guò)程蓖康。
