TreeMap 类

TreeMap集合是基于红黑树（Red-Black tree）的 NavigableMap实现。该集合最重要的特点就是可排序，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator 进行排序。Tree两张实现排序方法，一种方式是实现java.lang.Comparable接口，并实现其compareTo()方法。第二种方式是单独写一个类去实现java.util.Comparator接口，并实现compare()方法，然后创建实例并作为TreeMap的构造方法参数进行传参

public class TreeMap<K,V> extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, java.io.Serializable

这里有个特殊接口NavigableMap，先看看TreeMap接口

public interface NavigableMap<K,V> extends SortedMap<K,V>

NavigableMap方法

    // 找到第一个比指定的key小的值Map.Entry<K,V> lowerEntry(K key);// 找到第一个比指定的key小的keyK lowerKey(K key);// 找到第一个小于或等于指定key的值Map.Entry<K,V> floorEntry(K key);// 找到第一个小于或等于指定key的keyK floorKey(K key);//  找到第一个大于或等于指定key的值Map.Entry<K,V> ceilingEntry(K key);//找到第一个大于或等于指定key的keyK ceilingKey(K key);// 找到第一个大于指定key的值Map.Entry<K,V> higherEntry(K key);//找到第一个大于指定key的keyK higherKey(K key);// 获取最小值Map.Entry<K,V> firstEntry();// 获取最大值Map.Entry<K,V> lastEntry();// 删除最小的元素Map.Entry<K,V> pollFirstEntry();// 删除最大的元素Map.Entry<K,V> pollLastEntry();//返回一个倒序的MapNavigableMap<K,V> descendingMap();// 返回一个Navigable的key的集合，NavigableSet和NavigableMap类似NavigableSet<K> navigableKeySet();// 对上述集合倒序NavigableSet<K> descendingKeySet();

SortedMap接口

    // 排序比较器Comparator<? super K> comparator();// 获取其中一段SortedMap<K,V> subMap(K fromKey, K toKey);// 获取小于toKey的键值对SortedMap<K,V> headMap(K toKey);/// 获取大于fromKey的键值对SortedMap<K,V> tailMap(K fromKey);// 返回此映射中当前第一个键K firstKey();// 返回映射中当前最后一个键K lastKey();// 与父接口Map中的定义一样，但有顺序Set<K> keySet();// 与父接口Map中的定义一样，但有顺序（根据key的顺序）Collection<V> values();// 与父接口Map中的定义一样，但有顺序（根据key的顺序）Set<Map.Entry<K, V>> entrySet();

SortedMap提供了获取最大值与最小值的方法，但对于一个已经排序的数据集，除了最大值与最小值之外，
我们还想对任何一个元素，找到比它小的值和比它大的值，还可以按照原有的顺序倒序排序等，
这时候就可以用NavigableMap接口

回到TreeMap，先看看成员变量及构造函数

    //这是一个比较器，方便插入查找元素等操作private final Comparator<? super K> comparator;//红黑树的根节点：每个节点是一个Entryprivate transient Entry<K,V> root;//集合元素数量private transient int size = 0;//集合修改的记录private transient int modCount = 0;public TreeMap() {comparator = null;}public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;}public TreeMap(Map<? extends K, ? extends V> m) {comparator = null;putAll(m);}public TreeMap(SortedMap<K, ? extends V> m) {comparator = m.comparator();try {buildFromSorted(m.size(), m.entrySet().iterator(), null, null);} catch (java.io.IOException cannotHappen) {} catch (ClassNotFoundException cannotHappen) {}}

从成员变量和构造函数可以看出，TreeMap没有用到数组槽，并且有一个Entry的root结点，它完全就是一颗树。

看看插入方法

public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {//如果root为null 说明是添加第一个元素 直接实例化一个Entry 赋值给rootcompare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;//如果root不为null，说明已存在元素 // split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) { //如果比较器不为null 则使用比较器//找到元素的插入位置do {parent = t; //parent赋值cmp = cpr.compare(key, t.key);//当前key小于节点key 向左子树查找if (cmp < 0)t = t.left;else if (cmp > 0)//当前key大于节点key 向右子树查找t = t.right;else //相等的情况下 直接更新节点值return t.setValue(value);} while (t != null);}else { //如果比较器为null 则使用默认比较器if (key == null)//如果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)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);//定义一个新的节点//根据比较结果决定插入到左子树还是右子树if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);//保持红黑树性质  插入后进行修正size++;//元素树自增modCount++;return null;}

完全一颗红黑树，所以其他方法就不在这叙述，想要了解的翻翻JDK源码。