7.TreeMap源码解析

1.数据结构
TreeMap的底层数据结构是红黑树，和HashMap的红黑树结构一样。不同的是，TreeMap利用红黑树左节点小，右节点大的性质，根据key进行排序，使每个元素能够插入到红黑树的适当位置，维护了key的大小关系，适用于key需要排序的场景。因为底层使用的是平衡红黑树的结构，所以containsKey、get、put、remove等方法的时间复杂度都是log(n)。
源码

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
  //比较器，如果外部有传进来Comparator比较器，首先用外部的
  //如果外部比较器为空，则使用key实现的Comparable的compareTo方法
  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> {}
}

2.新增
新增key和value的源码如下所示。
源码

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
  public V put(K key, V value) {
    Entry<K,V> t = root;
    //判断红黑树的节点是否为空，为空的话，新增的节点直接作为根节点
    if (t == null) {
      //compare方法限制了key不能为null
      compare(key, key); 
      //成为根节点
      root = new Entry<>(key, value, null);
      size = 1;
      modCount++;
      return null;
    }
    int cmp;
    Entry<K,V> parent;
    //根据红黑树左小右大的特性，进行判断，找到新增节点的父节点
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
      //自旋找到key应该新增的位置
      do {
          //一次循环结束时，parent就是上次比过的对象
          parent = t;
          //通过compare来比较key的大小
          cmp = cpr.compare(key, t.key);
          //key小于t，把t左边的值赋予t，因为红黑树左边的值比较小，循环再比
          if (cmp < 0)
              t = t.left;
          //key大于t，把t右边的值赋予t，因为红黑树右边的值比较大，循环再比
          else if (cmp > 0)
              t = t.right;
          //如果相等的话，直接覆盖原值
          else
              return t.setValue(value);
          //t为空，说明已经到叶子节点了
      } 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)
              t = t.left;
          else if (cmp > 0)
              t = t.right;
          else
              return t.setValue(value);
      } while (t != null);
    }
    //在父节点的左边或右边插入新增节点
    Entry<K,V> e = new Entry<>(key, value, parent);
        //cmp代表最后一次对比的大小，小于0 ，代表e在上一节点的左边
    if (cmp < 0)
      parent.left = e;
    //大于0 ，代表e在上一节点的右边，相等的情况第二步已经处理了
    else
      parent.right = e;
    //着色旋转，直至达到平衡
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
  }
}

源码解析

1. 新增节点时，利用红黑树左小右大的特性，从根节点不断往下查找，直到节点的值是null为止，节点为null说明到达了叶子结点。
2. 查找过程中，若发现key值已经存在，则直接覆盖。
3. TreeMap是不支持key是null的。