基本概念：
- TreeMap是基于红黑树（Red-Black tree）的NavigableMap实现。
- 该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的Comparator进行排序，具体取决于使用的构造方法。
- TreeMap可以对添加进来的元素进行排序，可以按照默认的排序方式，也可以自己指定排序方式。
1.TreeMap存储并排序我们自定义的类，那么必须自己定义比较机制：一种方式是User类去实现java.lang.Comparable接口，并实现其compareTo()方法。
2.写一个类（如MyComparator）去实现java.util.Comparator接口，并实现compare()方法，然后将MyComparator类实例对象作为TreeMap的构造方法参数进行传参（当然也可以使用匿名内部类），这些比较方法是怎么被调用的将在源码中讲解。
源码分析
类名及类成员变量
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{ // 比较器对象 private final Comparator<? super K> comparator; // 根节点 private transient Entry<K,V> root; // 集合大小 private transient int size = 0; // 树结构被修改的次数 private transient int modCount = 0; // 静态内部类用来表示节点类型 static final class Entry<K,V> implements Map.Entry<K,V> { K key; // 键 V value; // 值 Entry<K,V> left; // 指向左子树的引用（指针） Entry<K,V> right; // 指向右子树的引用（指针） Entry<K,V> parent; // 指向父节点的引用（指针） boolean color = BLACK; // } } 复制代码
类构造方法
public TreeMap() { // 1,无参构造方法 comparator = null; //默认比较机制 } public TreeMap(Comparator<? super K> comparator) { // 2，自定义比较器的构造方法 this.comparator = comparator; } public TreeMap(Map<? extends K, ? extends V> m) { // 3，构造已知Map对象为TreeMap comparator = null; // 默认比较机制 putAll(m); } public TreeMap(SortedMap<K, ? extends V> m) { // 4，构造已知的SortedMap对象为TreeMap comparator = m.comparator(); // 使用已知对象的构造器 try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } } 复制代码
put()方法详解
public V put(K key, V value) { Entry<K,V> t = root; // 获取根节点 // 如果根节点为空，则该元素置为根节点 if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; // 集合大小为1 modCount++; // 结构修改次数自增 return null; } int cmp; Entry<K,V> parent; Comparator<? super K> cpr = comparator; // 比较器对象 // 如果比较器对象不为空，也就是自定义了比较器 if (cpr != null) { do { // 循环比较并确定元素应插入的位置(也就是找到该元素的父节点) parent = t; // t就是root // 调用比较器对象的compare()方法，该方法返回一个整数 cmp = cpr.compare(key, t.key); if (cmp < 0) // 待插入元素的key"小于"当前位置元素的key，则查询左子树 t = t.left; else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树 t = t.right; else // "相等"则替换其value。 return t.setValue(value); } while (t != null); } // 如果比较器对象为空，使用默认的比较机制 else { if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; // 取出比较器对象 do { // 同样是循环比较并确定元素应插入的位置(也就是 找到该元素的父节点) parent = t; cmp = k.compareTo(t.key); // 同样调用比较方法并返回一个整数 if (cmp < 0) // 待插入元素的key"小于"当前位置元素的key，则查询左子树 t = t.left; else if (cmp > 0) // 待插入元素的key"大于"当前位置元素的key，则查询右子树 t = t.right; else // "相等"则替换其value。 return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); // 根据key找到父节点后新建一个节点 if (cmp < 0) // 根据比较的结果来确定放在左子树还是右子树 parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; // 集合大小+1 modCount++; // 集合结构被修改次数+1 return null; } 复制代码
自定义比较器的使用，说了这么多关于比较器的内容？
先来看下面这段代码
public class LiboExample { public static void main(String[] args) { Map<String, String> map = new TreeMap<>(); map.put("ddd", "444"); map.put("ccc", "333"); map.put("bbb", "222"); map.put("aaa", "111"); Set<Entry<String, String>> entrySet = map.entrySet(); for (Entry<String, String> each : entrySet) { System.out.println(each.getKey()+"::"+each.getValue()); } } } 复制代码
输出结果如下，结果是排序过的，那是因为String类实现了Comparable接口并实现了compareTo()方法，该方法按字典顺序比较两个字符串。
aaa::111 bbb::222 ccc::333 ddd::444 复制代码
下面我们写个自定义User类，使用2种方式将类对象按照age字段从小到大排序。
方式1，User实现Comparable接口并实现了compareTo()方法
User类
public class User implements Comparable<User>{ private String username; private int age; public User(String username, int age) { this.username = username; this.age = age; } @Override public String toString() { return "User [username=" + username + ", age=" + age + "]"; } @Override public int compareTo(User user) { int temp = this.age - user.age; return temp == 0 ? this.username. compareTo(user.username) : temp; } } 复制代码
测试代码
public class TreeMapDemo1 { public static void main(String[] args) { Map<User, String> map = new TreeMap<>(); map.put(new User("jimmy1", 30), "hello"); map.put(new User("jimmy2", 30), "hello"); map.put(new User("jimmy", 22), "hello"); map.put(new User("jimmy", 20), "hello"); Set<Entry<User, String>> entrySet = map.entrySet(); for (Entry<User, String> each : entrySet) { System.out.println(each.getKey()+"::"+each.getValue()); } } } 复制代码
输出结果如下，首先按age排序，若年龄相等则再按username的字母表顺序排序。
User [username=jimmy, age=20]::hello User [username=jimmy, age=22]::hello User [username=jimmy1, age=30]::hello User [username=jimmy2, age=30]::hello 复制代码
方式2，写一个类实现java.util.Comparator接口，并将该类对象传递给TreeMap的构造方法。
这种方式将实体类和比较机制解耦合，可以写很多个不同的比较器对象。
实体类
public class User3 { // User对象不再实现任何接口 private String username; private int age; public User3(String username, int age) { super(); this.username = username; this.age = age; } public String getUsername() { return username; } public void setUsername(String username) { this.username = username; } public int getAge() { return age; } public void setAge(int age) { this.age = age; } @Override public String toString() { return "User3 [username=" + username + ", age=" + age + "]"; } } 复制代码
比较器类
public class TreeMapComparator implements Comparator<User3>{ // 比较器类 @Override public int compare(User3 o1, User3 o2) { int temp = o1.getAge() - o2.getAge(); return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp; } } 复制代码
测试代码
public class TreeMapDemo3 { public static void main(String[] args) { Map<User3, String> map = new TreeMap<>(new TreeMapComparator()); map.put(new User3("jimmy1", 30), "hello"); map.put(new User3("jimmy2", 30), "hello"); map.put(new User3("jimmy", 22), "hello"); map.put(new User3("jimmy", 20), "hello"); Set<Entry<User3, String>> entrySet = map.entrySet(); for (Entry<User3, String> each : entrySet) { System.out.println(each.getKey()+"::"+each.getValue()); } } } 复制代码
输出结果如下，跟上面的相同。
User3 [username=jimmy, age=20]::hello User3 [username=jimmy, age=22]::hello User3 [username=jimmy1, age=30]::hello User3 [username=jimmy2, age=30]::hello 复制代码
当然，我们还可以不写比较器类，而是使用匿名内部类的形式来写比较器。
public class TreeMapDemo4 { public static void main(String[] args) { Map<User3, String> map = new TreeMap<>(new Comparator<User3>() { @Override public int compare(User3 o1, User3 o2) { int temp = o1.getAge() - o2.getAge(); return temp == 0 ? o1.getUsername().compareTo(o2.getUsername()) : temp; } }); map.put(new User3("jimmy1", 30), "hello"); map.put(new User3("jimmy2", 30), "hello"); map.put(new User3("jimmy", 22), "hello"); map.put(new User3("jimmy", 20), "hello"); Set<Entry<User3, String>> entrySet = map.entrySet(); for (Entry<User3, String> each : entrySet) { System.out.println(each.getKey()+"::"+each.getValue()); } } } 复制代码
一帮以getEntry()方法为基础的获取元素的方法，其中包括containsKey()，get()，remove()等。
final Entry<K,V> getEntry(Object key) { // 如果有自定义比较器对象，就按照自定义规则遍历二叉树 if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); @SuppressWarnings("unchecked") Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { //按照默认比较规则遍历二叉树 int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } return null; } 复制代码
一帮以getFirstEntry()，getLastEntry()为基础的获取头和尾元素的方法，其中包括：firstKey()，lastKey()；firstEntry()，lastEntry()；pollFirstEntry()，pollLastEntry()；
final Entry<K,V> getFirstEntry() { // 获取第一个元素也就是最小的元素，一直遍历左子树 Entry<K,V> p = root; if (p != null) while (p.left != null) p = p.left; return p; } final Entry<K,V> getLastEntry() { // 获取最后个元素也就是最大的元素，一直遍历右子树 Entry<K,V> p = root; if (p != null) while (p.right != null) p = p.right; return p; } 复制代码
keySet()和entrySet()方法，在将HashMap的时候已经讲过了，Map没有迭代器，要将Map转化为Set，用Set的迭代器才能进行元素迭代。
总结
TreeMap继承了Map的性质，同时其树结构又可以进行元素排序，用处很大。
