TreeMap

TreeMap 是一个有序的key-value集合，它是通过红黑树实现的。
（红黑树一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。在我们好理解的二叉查找树上增加了五点要求，以促进树的平衡，想了解等多请点击链接。）

构造函数

1. TreeMap() 使用默认构造函数构造TreeMap的时候，使用默认的比较器来进行key的比较，对TreeMap进行升序排序;
2. TreeMap(Comparator<? super K> comparator) 带比较器(comparator)的构造函数，用户可以自定义比较器，按照自己的需要对TreeMap进行排序；
3. TreeMap(Map<? extends K, ? extends V> copyFrom) 基于一个map创建一个新的TreeMap，使用默认比较器升序排序
4. TreeMap(SortedMap<K, ? extends V> copyFrom) 基于一个SortMap创建一个新的TreeMap（SortMap是有序的）

常用方法

Method	Description
Map.Entry<K,V> ceilingEntry(K key)	返回一个键-值映射关系，它与大于等于给定键的最小键关联；如果不存在这样的键，则返回 null。
Map.Entry<K,V> pollFirstEntry()	移除并返回与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
Map.Entry<K,V> pollLastEntry()	移除并返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
Map.Entry<K,V> lowerEntry(K key)	返回一个键-值映射关系，它与严格小于给定键的最大键关联；如果不存在这样的键，则返回 null。
Map.Entry<K,V> higherEntry(K key)	返回一个键-值映射关系，它与严格大于给定键的最小键关联；如果不存在这样的键，则返回 null。
Map.Entry<K,V> floorEntry(K key)	返回一个键-值映射关系，它与小于等于给定键的最大键关联；如果不存在这样的键，则返回 null。
Map.Entry<K,V> firstEntry()	返回一个与此映射中的最小键关联的键-值映射关系；如果映射为空，则返回 null。
K ceilingKey(K key)	返回大于等于给定键的最小键；如果不存在这样的键，则返回 null。
void clear()	从此映射中移除所有映射关系。
Object clone()	返回此 TreeMap 实例的浅表副本。
Comparator<? super K> comparator()	返回对此映射中的键进行排序的比较器；如果此映射使用键的自然顺序，则返回 null。
boolean containsKey(Object key)	如果此映射包含指定键的映射关系，则返回 true。
boolean containsValue(Object value)	如果此映射为指定值映射一个或多个键，则返回 true。
Set<Map.Entry<K,V>> entrySet()	返回此映射中包含的映射关系的 Set 视图。
K firstKey()	返回此映射中当前第一个（最低）键。
K floorKey(K key)	返回小于等于给定键的最大键；如果不存在这样的键，则返回 null。
V get(Object key)	返回指定键所映射的值，如果对于该键而言，此映射不包含任何映射关系，则返回 null。
SortedMap<K,V> headMap(K toKey)	返回此映射的部分视图，其键值严格小于 toKey。
K higherKey(K key)	返回严格大于给定键的最小键；如果不存在这样的键，则返回 null。
Set<K> keySet()	返回此映射包含的键的 Set 视图。
Map.Entry<K,V> lastEntry()	返回与此映射中的最大键关联的键-值映射关系；如果映射为空，则返回 null。
K lastKey()	返回映射中当前最后一个（最高）键。
K lowerKey(K key)	返回严格小于给定键的最大键；如果不存在这样的键，则返回 null。
V put(K key, V value)	将指定值与此映射中的指定键进行关联。
void putAll(Map<? extends K,? extends V> map)	将指定映射中的所有映射关系复制到此映射中。
V remove(Object key)	如果此 TreeMap 中存在该键的映射关系，则将其删除。
int size()	返回此映射中的键-值映射关系数。
SortedMap<K,V> subMap(K fromKey, K toKey)	返回此映射的部分视图，其键值的范围从 fromKey（包括）到 toKey（不包括）。
SortedMap<K,V> tailMap(K fromKey)	返回此映射的部分视图，其键大于等于 fromKey。
Collection<V> values()	返回此映射包含的值的 Collection 视图。
NavigableSet<K> descendingKeySet()	返回此映射中所包含键的逆序 NavigableSet 视图。
NavigableMap<K,V> descendingMap()	返回此映射中所包含映射关系的逆序视图。
NavigableMap<K,V> headMap(K toKey, boolean inclusive)	返回此映射的部分视图，其键小于（或等于，如果 inclusive 为 true）toKey。
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	返回此映射的部分视图，其键的范围从 fromKey 到 toKey。
NavigableSet<K> navigableKeySet()	返回此映射中所包含键的 NavigableSet 视图。
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)	返回此映射的部分视图，其键大于（或等于，如果 inclusive 为 true）fromKey。

遍历

1. 遍历键值对

// for循环遍历
for (Map.Entry entry : treeMap.entrySet()) {
    // other code
}

//Iterator遍历
Iterator iterator = treeMap.entrySet().iterator();
while (iterator.hasNext()) {
     Map.Entry entry = (Map.Entry) iterator.next();
     // other code
}

2. 遍历键key

// for循环遍历
for (Object key:treeMap.keySet()) {
    // other code
}

//Iterator遍历
Iterator iterator = ttreeMap.keySet().iterator();
while (iterator.hasNext()) {
     key = (Object) iterator.next();
     // other code
}

3. 遍历值value

// for循环遍历
for (Object value:treeMap.values()) {
    // other code
}

//Iterator遍历
Iterator iterator = treeMap..values().iterator();
while (iterator.hasNext()) {
     value = (Object) iterator.next();
     // other code
}

例子

前面说到，hashmap是无序的，而treemap是有序的，且默认比较器比较key值升序排序，可以写个小例子看看：

import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        HashMap<Integer, String> hmap = new HashMap<>();
        hmap.put(13, "Yellow");
        hmap.put(3, "Red");
        hmap.put(2, "Green");
        hmap.put(33, "Blue");
        System.out.println("key & values in hmap:");
        for (Map.Entry entry : hmap.entrySet()) {
            System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
        }
        TreeMap<Integer, String> tmap = new TreeMap<>(hmap);
        System.out.println("key & values in tmap:");
        for (Map.Entry entry : tmap.entrySet()) {
            System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
        }
    }
}

结果：

key & values in hmap:
key: 33, value: Blue
key: 2, value: Green
key: 3, value: Red
key: 13, value: Yellow
key & values in tmap:
key: 2, value: Green
key: 3, value: Red
key: 13, value: Yellow
key: 33, value: Blue

可以看出，hmap中没有排序，实际看到的打印出的“顺序”是键值对的添加顺序的倒序；而tmap则是按key的大小升序排序的。

• 另一个例子

import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapTest {
    public static void main(String[] args) {
        TreeMap<Integer, String> tmap = new TreeMap<>();
        System.out.println("tmap is empty: " + tmap.isEmpty());
        tmap.put(13, "Yellow");
        tmap.put(3, "Red");
        tmap.put(2, "Green");
        tmap.put(33, "Blue");
        System.out.println("key & values in tmap:");
        for (Map.Entry entry : tmap.entrySet()) {
            System.out.println("key: " + entry.getKey() + ", value: " + entry.getValue());
        }
        System.out.println("size of tmap is: " + tmap.size());
        System.out.println("tmap contains value Purple: " + tmap.containsValue("Purple"));
        System.out.println("tmap contains key 12: " + tmap.containsKey(12));
        System.out.println("last key in tmap is: " + tmap.lastKey());
        System.out.println("key is 14 & value is " + tmap.get(14));
        System.out.println("remove key 13");
        tmap.remove(13);
        System.out.println("tmap contains key 13: " + tmap.containsKey(13));
        System.out.println("key in tmap:");
        Iterator iterator = tmap.keySet().iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println("clear tmap");
        tmap.clear();
        System.out.println("size of tmap: " + tmap.size());
    }
}

结果：

tmap is empty: true
key & values in tmap:
key: 2, value: Green
key: 3, value: Red
key: 13, value: Yellow
key: 33, value: Blue
size of tmap is: 4
tmap contains value Purple: false
tmap contains key 12: false
last key in tmap is: 33
key is 14 & value is null
remove key 13
tmap contains key 13: false
key in tmap:
2
3
33
clear tmap
size of tmap: 0