前面学习了Map接口的实现类LinkedHashMap，LinkedHashMap存储的元素是有序的，可以保持元素的插入顺序，但不能对元素进行自动排序。在一些编程应用场景中，如果在数据的存储过程中，能够自动对数据进行排序，将会极大提高编程效率，程序员无需再为数据排序编写必要的代码。例如，一般大量的数据都被存储在大型数据库中，程序员需要能够按照多个键对索引排序以提供搜索效率。
Map接口有一个重要的实现类TreeMap，TreeMap可以实现存储元素的自动排序。在TreeMap中，键值对之间按键有序，TreeMap的实现基础是平衡二叉树。
1、TreeMap 的存储结构
TreeMap使用的存储结构是平衡二叉树，也称为红黑树。它首先是一棵二叉树，具有二叉树所有的特性，即树中的任何节点的值大于它的左子节点，且小于它的右子节点，如果是一棵左右完全均衡的二叉树，元素的查找效率将获得极大提高。最坏的情况就是一边倒，只有左子树或只有右子树，这样势必会导致二叉树的检索效率大大降低。为了维持二叉树的平衡，程序员们提出了各种实现的算法，其中平衡二叉树就是其中的一种算法。平衡二叉树的数据结构如下图所示：
TreeMap存储结构
2、TreeMap 的构造函数
TreeMap 提供了三个常用的构造函数，说明如下：
● TreeMap()
使用该构造函数，TreeMap中的key按照自然排序进行排列。
● TreeMap(Map<? extends K, ? extends V> copyFrom)
使用该构造函数，用指定的Map填充TreeMap，TreeMap中的key按照自然排序进行排列。
● TreeMap(Comparator<? super K> comparator)
使用该构造函数，指定元素排序所用的比较器，key排列顺序由比较器指定。
2、TreeMap 元素的存取
同HashMap一样，TreeMap提供了get和put方法用于元素的存取。
● put(K key, V value)
该方法用于添加一个Entry（结点，包括key和value）到TreeMap对象，key为与指定值将要关联的键，value为使用指定键关联的值。如果key对应的值已经存在，则将key对应的值修改为value。
● V get(Object key)
该方法用于获取指定key的value，key为与value相关联的键。
案例1：建立TreeMapTest1类，实例化TreeMap对象，进行对象元素的添加和修改操作。
在map包下新建TreeMapTest1类。代码如下：
package map;
import java.util.TreeMap;
/**
* @ClassName: TreeMapTest1
* @Description: 集合框架（TreeMap类）案例1
* @author 编程训练营
* @date
*
*/
public class TreeMapTest1 {
/**
* @Title: main
* @Description:Java程序入口main方法
* @param @param args 参数
* @return void 返回类型
* @throws
*/
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<Integer, String>();
// 添加元素
map.put(8, "eight");
map.put(6, "six");
map.put(3, "three");
map.put(12, "twelve");
map.put(9, "nine");
map.put(11, "eleven");
System.out.println("输出map:" + map);
// 获取key为3的元素
String value = (String) map.get(3);
System.out.println("key为3的value为: " + value);
// 修改key为3前的元素
map.put(3, "sixteen");
System.out.println("输出修改后的map: " + map);
}
}案例代码实例化TreeMap对象。首先用put方法添加了6个Entry结点，然后用get方法获取指定key的值，再用put方法修改指定key的值。
程序执行结果如下图所示：
从图中输出结果可以看出，TreeMap按照传入的key进行自动排序。
3、TreeMap 的遍历
同HashMap、LinkedHashMap相同，TreeMap也不能用迭代器、foreach等方法遍历。如果需要遍历TreeMap，可以通过TreeMap的keySet方法返回TreeMap中key值的集合进行遍历。
案例2：建立TreeMapTest2类，实例化TreeMap对象，进行集合的遍历操作。
在map包下新建TreeMapTest2测试类。代码如下：
package map;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
/**
* @ClassName: TreeMapTest2
* @Description: 集合框架（TreeMap类）案例2
* @author 编程训练营
* @date
*
*/
public class TreeMapTest2 {
/**
* @Title: main
* @Description: Java程序入口main方法
* @param @param args 参数
* @return void 返回类型
* @throws
*/
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<Integer, String>();
// 添加元素
map.put(8, "eight");
map.put(6, "six");
map.put(3, "three");
map.put(12, "twelve");
map.put(9, "nine");
map.put(11, "eleven");
System.out.println("输出map:" + map);
// 获取key为3的元素
String value = (String) map.get(3);
System.out.println("key为3的value为: " + value);
// 修改key为3前的元素
map.put(3, "sixteen");
System.out.println("输出修改后的map: " + map);
//获取Map中的所有key与value的对应关系
Set<Entry<Integer, String>> entrySet =map.entrySet();
//遍历Set集合
Iterator<Map.Entry<Integer, String>> it=entrySet.iterator();
while(it.hasNext()){
//得到每一对对应关系
Map.Entry<Integer, String> entry = it.next();
//通过每一对对应关系获取对应的key
Integer key = entry.getKey();
//通过每一对对应关系获取对应的value
String strValue = entry.getValue();
System.out.println(key+"="+value);
}
}
}案例代码获取TreeMap所有的键值对(Entry)对象，并以Set集合形式返回。然后，通过遍历包含键值对(Entry)对象的Set集合，得到每一个键值对。
程序执行结果如下图所示：
HashMap通过hashcode对其内容进行快速查找，而 TreeMap中所有的元素都保持着某种固定的顺序，如果你需要得到一个有序的结果你就应该使用TreeMap。HashMap通常比TreeMap效率要高一些，一个是哈希表，一个是二叉树，建议多使用HashMap，在需要排序的Map时候才用TreeMap。