优质博文：IT-BLOG-CN
背景：昨天有人问我，他想将Map中的Key按照顺序进行遍历，我说直接使用keySet方法获取到Set集合，因为它是集成Collection接口，所以包含了sort方法后遍历取value值即可。但当看到TreeMap的那一刻，我发现自己错了。
再说一个很重要的概念：
【1】TreeMap的key不能为null，value可以为null;
【2】HashMap的key可以为null，value可以为null;
【3】ConcurrentHashMap和HashTable的key和value都不可以为null;
一、TreeMap 结构
如类图所示：TreeMap也是一种Map实现了SortedMap<K,V>接口，说明他内部对Key进行了排序。而HashMap内部的Key是无序的。TreeMap的底层是一颗红黑树，这是一种自然平衡二叉搜索树，可以保证在插入，删除，查找等操作中的时间复杂度为O(log n)
使用TreeMap时，放入的Key必须实现Comparable接口。String、Integer这些类已经实现了Comparable接口，因此可以直接作为Key使用。作为Value的对象则没有任何要求。
如果作为Key的class没有实现Comparable接口，那么，必须在创建TreeMap时同时指定一个自定义排序算法，我们可以先看下TreeMap的构造器：
// 默认构造函数。使用该构造函数，TreeMap中的元素按照自然排序进行排列。TreeMap() // 创建的TreeMap包含MapTreeMap(Map<? extends K, ? extends V> copyFrom) // 指定Tree的比较器TreeMap(Comparator<? super K> comparator) // 创建的TreeSet包含copyFromTreeMap(SortedMap<K, ? extends V> copyFrom)实际开发中案例：Comparator接口要求实现一个比较方法，它负责比较传入的两个元素p1和p2，如果p1 < p2，则返回负数，通常是-1，如果p1 == p2，则返回0，如果p1 > p2，则返回正数，通常是1。TreeMap内部根据比较结果对Key进行排序。
import java.util.*;public class Main { public static void main(String[] args) { Map<Person, Integer> map = new TreeMap<>(new Comparator<Person>() { public int compare(Person p1, Person p2) { return p1.name.compareTo(p2.name); } }); map.put(new Person("Tim"), 1); map.put(new Person("Baby"), 2); map.put(new Person("Luna"), 3); for (Person key : map.keySet()) { System.out.println(key); } // {Person: Baby}, {Person: Luna}, {Person: Tim} System.out.println(map.get(new Person("Baby"))); // 2 }}class Person { public String name; Person(String name) { this.name = name; } public String toString() { return "{Person: " + name + "}"; }}Person类并未覆写equals()和hashCode()，因为TreeMap不使用equals()和hashCode()。
二、TreeMap API
基础数据：
// 创建一个 TreeMapTreeMap<String, Integer> map = new TreeMap<>();// 向 TreeMap 中添加键值对map.put("Alice", 90);map.put("Bob", 80);map.put("Charlie", 70);map.put("David", 60);TreeMap因为排序等特性，所以包含了一些特殊的API这里简单介绍一下：
【1】firstKey和lastKey：分别返回TreeMap中最小和最大的键；
// 返回 TreeMap 中最小和最大的键System.out.println(map.firstKey()); // AliceSystem.out.println(map.lastKey()); // David【2】lowerKey和higherKey：分别返回TreeMap中小于和大于给定键的最近的键；
// 返回 TreeMap 中小于和大于给定键的最近的键System.out.println(map.lowerKey("Bob")); // AliceSystem.out.println(map.higherKey("Bob")); // Charlie【3】floorKey和ceilingKey：分别返回TreeMap中小于等于和大于等于给定键的最近的键；
// 返回 TreeMap 中小于等于和大于等于给定键的最近的键System.out.println(map.floorKey("Bob")); // BobSystem.out.println(map.ceilingKey("Bob")); // Bob【4】subMap：返回一个子映射，包含给定范围内的所有键值对；
// 返回一个子映射，包含给定范围内的所有键值对System.out.println(map.subMap("Alice", true, "Charlie", true)); // {Alice=90, Bob=80, Charlie=70}【5】headMap和tailMap：分别返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对；
// 返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对System.out.println(map.headMap("Charlie", true)); // {Alice=90, Bob=80, Charlie=70}System.out.println(map.tailMap("Charlie", true)); // {Charlie=70, David=60}【6】firstEntry和lastEntry：分别返回TreeMap中最小和最大的键值对；
// 返回 TreeMap 中最小和最大的键值对System.out.println(map.firstEntry()); // Alice=90System.out.println(map.lastEntry()); // David=60【7】lowerEntry和higherEntry：分别返回TreeMap中小于和大于给定键的最近的键值对；
// 返回 TreeMap 中小于和大于给定键的最近的键值对System.out.println(map.lowerEntry("Bob")); // Alice=90System.out.println(map.higherEntry("Bob")); // Charlie=70【8】floorEntry和ceilingEntry：分别返回TreeMap中小于等于和大于等于给定键的最近的键值对；
// 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对System.out.println(map.floorEntry("Bob")); // Bob=80System.out.println(map.ceilingEntry("Bob")); // Bob=80【9】pollFirstEntry和pollLastEntry：分别返回并删除TreeMap中最小和最大的键值对；
// 返回并删除 TreeMap 中最小和最大的键值对System.out.println(map.pollFirstEntry()); // Alice=90System.out.println(map.pollLastEntry()); // David=60根据上述的API可知，如果遇到如下场景时，应当想到使用TreeMap：
【1】需要按照键的自然顺序或者指定的比较器进行排序的场景，例如字典，排行榜，日程安排等。
【2】需要快速找到映射中最小或者最大的键或者值的场景，例如优先队列，堆，区间查询等。
【3】需要快速找到映射中某个范围内的所有键或者值的场景，例如范围搜索，前缀匹配，区间统计等。
三、注意事项
【1】如果使用自然顺序进行排序，则需要保证键是可比较的（实现了Comparable接口），否则会抛出ClassCastException异常。
【2】如果使用指定的比较器进行排序，则需要保证比较器是一致的（满足自反性，对称性，传递性），否则可能导致排序结果不正确或者抛出ClassCastException异常。
【3】如果在遍历TreeMap的过程中修改了其结构（添加或删除了元素），则可能导致ConcurrentModificationException异常或者不确定的行为。
【4】如果在遍历TreeMap的过程中修改了其元素（改变了键或者值），则可能导致排序结果不正确或者不确定的行为。
【5】TreeMap不是线程安全的，如果多个线程同时访问或修改TreeMap，则需要进行同步处理。