本文共 14317 字，大约阅读时间需要 47 分钟。

前言

了解过hashmap和linkedhashmap的应该知道，hashmap不能保证有序，linkedhashmap可以保证插入顺序。但如果想保证key的大小顺序，就得用到treemap。treemap的底层实现是红黑树，不了解红黑树的可以查看。

先看成员变量

public class TreeMap
   
     extends AbstractMap
    
         implements NavigableMap
     
      , Cloneable, java.io.Serializable{
       // 用于接收外部比较器，插入时用于比对元素的大小    private final Comparator
       comparator;        // 根节点    private transient Entry
      
        root;        // 树中元素个数    private transient int size = 0;        ...}
      
     
    
   

我们就先关注这3个变量就行：比较器、根节点和元素个数。另外，我们还可以看出TreeMap的继承、实现关系：

1.TreeMap继承AbstractMap，意味着它是一个Map，是一个k-v集合。 2.实现NavigableMap接口，返回有序的key集合 3.实现Cloneable接口，表示能被克隆 4.实现了java.io.Serializable接口，表示能被序列化

数据结构

TreeMap是基于红黑树实现的，树节点Entry实现了Map.Entry，里面包括父节点、左右子节点、k-v、颜色

static final class Entry
   
     implements Map.Entry
    
      {
       K key;    V value;    Entry
     
       left;//左子节点    Entry
      
        right;//右子节点    Entry
       
         parent;//父节点    boolean color = BLACK;//颜色，红黑        ...}
       
      
     
    
   

构造器

空构造

默认使用key的自然顺序构建有序树，若key是String类型，就用String类的compareTo方法比较大小；若key为Integer类型，就用Integer的compareTo方法比较。并且，key的类型必须实现Comparable接口，否则无法比较大小。

public TreeMap() {
       comparator = null;//创建一颗空树}

带比较器参数的构造

自定义一个类，实现Compartor接口的compare方法。然后传入这个参数用来构造TreeMap

public TreeMap(Comparator
    comparator) {
       this.comparator = comparator;}

常规操作

put方法

主要就是两个步骤：构建排序二叉树，平衡二叉树

具体步骤： 1、以根节点为初始节点进行检索； 2、与当前节点进行对比，若新增节点值较大则以当前节点的右子节点作为新的当前节点，否则就以当前节点的左子节点作为新的当前节点； 3、循环递归步骤2直到检索出合适的叶子结点 4、将新增节点与步骤3中找到的节点进行对比，若新增节点较大则添加为右子节点，否则为左子节点 do while是核心算法，该算法可以使新增节点找到正确的位置

public V put(K key, V value) {
       Entry
   
     t = root;//二叉树的当前节点    if (t == null) {
   //空树，无元素，直接插入        compare(key, key); // 比较key，但是真的有意义吗？都是null了比较个毛线？        //为k-v键值对创建Entry节点，并作为根节点        root = new Entry<>(key, value, null);        size = 1;        modCount++;//修改次数自增        return null;    }    int cmp;//key排序返回的结果    Entry
    
      parent;//父节点       Comparator
      cpr = comparator;//指定的比较器    if (cpr != null) {
   // 外部比较器        do {
               parent = t;//父节点指向上一次循环的t            cmp = cpr.compare(key, t.key);//比较新增节点和当前节点的key的大小            //新增节点的key < 当前节点的key，则以当前节点的左子节点作为新的当前节点            if (cmp < 0)                t = t.left;            //新增节点的key > 当前节点的key，则以当前节点的右子节点作为新的当前节点                else if (cmp > 0)                t = t.right;            //返回值等于0，表示两个key值相等，则新值覆盖旧值，并返回新值                 else                return t.setValue(value);        } while (t != null);    }    else {
   // cpr为空，则采用默认比较器创建TreeMap集合         if (key == null)//key为null就抛出异常            throw new NullPointerException();        @SuppressWarnings("unchecked")            Comparable
      k = (Comparable
     ) 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);    }    //新增节点作为parent子节点    Entry
     
       e = new Entry<>(key, value, parent);    if (cmp < 0)  //新增节点的key小于parent的key，做左子树         parent.left = e;    else  //右子树        parent.right = e;    // 插入完成，执行红黑树的性质恢复操作，以维持红黑树的平衡    fixAfterInsertion(e);    size++;    modCount++;    return null;}
     
    
   

####put辅助方法之fixAfterInsertion方法

private void fixAfterInsertion(Entry
   
     x) {
           x.color = RED;//新增节点的颜色为红色        //循环直到x不是根节点且x的父节点不是红色        while (x != null && x != root && x.parent.color == RED) {
               //x的父节点，位于其祖父节点的左节点            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                   //获取x的叔叔节点 y                Entry
    
      y = rightOf(parentOf(parentOf(x)));                //x的叔叔y是红色                if (colorOf(y) == RED) {
                       setColor(parentOf(x), BLACK);//把x的父节点设置成黑色                    setColor(y, BLACK);//把x的叔叔设置成黑色                    setColor(parentOf(parentOf(x)), RED);//把x的祖父设置成红色                    x = parentOf(parentOf(x));//祖父变人了                } else {
   //x的叔叔是黑色                    //x位于父节点的右子树                    if (x == rightOf(parentOf(x))) {
                           x = parentOf(x);//x父节点作为x                        rotateLeft(x);//左旋                    }                    setColor(parentOf(x), BLACK);//x父亲变黑                    setColor(parentOf(parentOf(x)), RED);//x祖父变红                    rotateRight(parentOf(parentOf(x)));//以x祖父为中心右旋                }            } else {
   //x的父节点位于祖父的右子树位置                //获取x的叔叔                Entry
     
       y = leftOf(parentOf(parentOf(x)));                if (colorOf(y) == RED) {
   //x的叔叔节点为红色                    setColor(parentOf(x), BLACK);//x的父亲变黑                    setColor(y, BLACK);//x的叔叔变黑                    setColor(parentOf(parentOf(x)), RED);//x祖父变红                    x = parentOf(parentOf(x));//又变人了                } else {
   //x的叔叔是黑色                    if (x == leftOf(parentOf(x))) {
   //x在左子树                        x = parentOf(x);//x父节点作为x                        rotateRight(x);//右旋                    }                    setColor(parentOf(x), BLACK);//父节点变黑                    setColor(parentOf(parentOf(x)), RED);//祖父变红                    rotateLeft(parentOf(parentOf(x)));//左旋                }            }        }        root.color = BLACK;//强制根节点变黑，为了保险起见    }
     
    
   

put辅助方法之rotateLeft左旋

将新增节点N当做其父节点P，将其父节点P当做新增节点N的左子节点。即：G.left ——> N ,N.left ——> P

private void rotateLeft(Entry
   
     p) {
             if (p != null) {
                 //获取P的右子节点，相当于新增节点N            Entry
    
      r = p.right;              //将R的左子树设置为P的右子树              p.right = r.left;              //若R的左子树不为空，将P设置为R左子树的父亲              if (r.left != null)                  r.left.parent = p;              //将P的父亲设置R的父亲              r.parent = p.parent;              //如果P的父亲为空，则将R设置为根节点              if (p.parent == null)                  root = r;              //如果P为其父节点G的左子树，则将R设置为P父节点G左子树              else if (p.parent.left == p)                  p.parent.left = r;              //否则R设置为P的父节点G的右子树              else                  p.parent.right = r;              //将P设置为R的左子树              r.left = p;              //将R设置为P的父节点              p.parent = r;          }      }
    
   

put辅助方法之rotateRight右旋

P.right ——> G、G.parent ——> P

private void rotateRight(Entry
   
     p) {
             if (p != null) {
                 //将L设置为P的左子树              Entry
    
      l = p.left;              //将L的右子树设置为P的左子树              p.left = l.right;              //若L的右子树不为空，则将P设置L的右子树的父节点              if (l.right != null)                   l.right.parent = p;              //将P的父节点设置为L的父节点              l.parent = p.parent;              //如果P的父节点为空，则将L设置根节点              if (p.parent == null)                  root = l;              //若P为其父节点的右子树，则将L设置为P的父节点的右子树              else if (p.parent.right == p)                  p.parent.right = l;              //否则将L设置为P的父节点的左子树              else                   p.parent.left = l;              //将P设置为L的右子树              l.right = p;              //将L设置为P的父节点              p.parent = l;          }      }
    
   

get方法

实际是调用了getEntry方法，简单的二叉查找过程…

1、判断是否指定比较器，指定就调用getEntryUsingComparator；2、校验key；3、遍历，return

public V get(Object key) {
       Entry
   
     p = getEntry(key);    return (p==null ? null : p.value);//为空就return null，否则就返回p.value}final Entry
    
      getEntry(Object key) {
       // Offload comparator-based version for sake of performance    if (comparator != null)        // 如果外部比较器，就采用外部比较器比对查找元素        return getEntryUsingComparator(key);    if (key == null)        // 为空就抛异常，所以Treemap是不允许null的        throw new NullPointerException();                // 采用key的默认比较器    @SuppressWarnings("unchecked")        Comparable
      k = (Comparable
     ) key;    Entry
     
       p = root;    while (p != null) {
           int cmp = k.compareTo(p.key);//比较key        if (cmp < 0)            p = p.left;        else if (cmp > 0)            p = p.right;        else            return p;    }    return null;}
     
    
   

删除方法

删除操作调用的是deleteEntry方法

private void deleteEntry(Entry
   
     p) {
       modCount++;    size--;    // case1：待删除的节点有两个孩子，找到P的中序后继结点来代替p    if (p.left != null && p.right != null) {
           Entry
    
      s = successor(p);//寻找P的替代节点        p.key = s.key;        p.value = s.value;        p = s;    } // p has 2 children    //replacement为替代节点，如果P的左子树存在就用左子树替代，否则就用右子树    Entry
     
       replacement = (p.left != null ? p.left : p.right);    // case2：待删除节点只有一个孩子    if (replacement != null) {
           // replacement来替代p        replacement.parent = p.parent;        if (p.parent == null) //p没有父节点，就直接吧replacement变成根节点            root = replacement;        else if (p == p.parent.left) //p为左节点，就用replacement替代左节点            p.parent.left  = replacement;        else //p为右节点，用replacement替代为右节点            p.parent.right = replacement;        // 把P从树中踢出去        p.left = p.right = p.parent = null;        // p是黑色，需要调整红黑树平衡        if (p.color == BLACK)            fixAfterDeletion(replacement);    } else if (p.parent == null) {
    // case3：p没有父节点，表示p是根节点，直接删        root = null;    } else {
    //case4：p没有子节点，直接删就行        if (p.color == BLACK) //p是黑色，还需要平衡            fixAfterDeletion(p);                //删除p节点        if (p.parent != null) {
               if (p == p.parent.left)                p.parent.left = null;            else if (p == p.parent.right)                p.parent.right = null;            p.parent = null;        }    }}
     
    
   

删除辅助方法之successor

寻找替代节点replacement

static 
   
     TreeMap.Entry
    
      successor(Entry
     
       t) {
       if (t == null)        return null;    else if (t.right != null) {
   // 找右子树中最小元素节点，也就是最左子树        Entry
      
        p = t.right;        while (p.left != null)            p = p.left;        return p;    } else {
   // 找左子树中的最大元素节点，也就是最右子树        Entry
       
         p = t.parent;        Entry
        
          ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; }}
        
       
      
     
    
   

删除辅助方法之fixAfterDeletion

fixAfterDeletion方法用来维持平衡

private void fixAfterDeletion(Entry
   
     x) {
             // 只有当x不是根节点并且是黑色，否则就得一直去迭代        while (x != root && colorOf(x) == BLACK) {
                 if (x == leftOf(parentOf(x))) {
   //若X节点为左节点                  //获取兄弟节点                  Entry
    
      sib = rightOf(parentOf(x));                    //如果兄弟节点为红色，变色、左旋                if (colorOf(sib) == RED) {
                              setColor(sib, BLACK);                           setColor(parentOf(x), RED);                        rotateLeft(parentOf(x));                      sib = rightOf(parentOf(x));                  }                    //若兄弟节点的两个子节点都为黑色，兄弟节点变红                 if (colorOf(leftOf(sib))  == BLACK &&                      colorOf(rightOf(sib)) == BLACK) {
                         setColor(sib, RED);                      x = parentOf(x);                  }                   else {
                         // 如果兄弟节点只有右子树为黑色，兄弟节点和左子树变色、右旋                    if (colorOf(rightOf(sib)) == BLACK) {
                             setColor(leftOf(sib), BLACK);                          setColor(sib, RED);                          rotateRight(sib);                          sib = rightOf(parentOf(x));                      }                      //策略：交换兄弟节点和父节点的颜色，兄弟节点右子树变黑，左旋                    setColor(sib, colorOf(parentOf(x)));                      setColor(parentOf(x), BLACK);                      setColor(rightOf(sib), BLACK);                      rotateLeft(parentOf(x));                      x = root;                  }              }                             //x为右节点，处理方式跟上面差不多              else {
                     Entry
     
       sib = leftOf(parentOf(x));                    if (colorOf(sib) == RED) {
                         setColor(sib, BLACK);                      setColor(parentOf(x), RED);                      rotateRight(parentOf(x));                      sib = leftOf(parentOf(x));                  }                    if (colorOf(rightOf(sib)) == BLACK &&                      colorOf(leftOf(sib)) == BLACK) {
                         setColor(sib, RED);                      x = parentOf(x);                  } else {
                         if (colorOf(leftOf(sib)) == BLACK) {
                             setColor(rightOf(sib), BLACK);                          setColor(sib, RED);                          rotateLeft(sib);                          sib = leftOf(parentOf(x));                      }                      setColor(sib, colorOf(parentOf(x)));                      setColor(parentOf(x), BLACK);                      setColor(leftOf(sib), BLACK);                      rotateRight(parentOf(x));                      x = root;                  }              }          }            setColor(x, BLACK);      }
     
    
   

遍历

顺、逆序遍历之顺序遍历

返回顺序的KEY的集合

Iterator
   
     keyIterator() {
       return new KeyIterator(getFirstEntry());//第一节点}
   

KeyIterator方法

final class KeyIterator extends PrivateEntryIterator
   
     {
       KeyIterator(Entry
    
      first) {
           super(first);    }    //执行next就是顺序遍历，不断地拿到下一个元素    public K next() {
           return nextEntry().key;    }}
    
   

顺、逆序遍历之逆序遍历

返回逆序的KEY的集合

Iterator
   
     descendingKeyIterator() {
       return new DescendingKeyIterator(getLastEntry());//最后一个结点}
   

DescendingKeyIterator方法

final class DescendingKeyIterator extends PrivateEntryIterator
   
     {
       DescendingKeyIterator(Entry
    
      first) {
           super(first);    }    //逆序遍历，获取上一个结点    public K next() {
           return prevEntry().key;    }}
    
   

3种遍历方式

1.遍历键值对

Iterator iter = map.entrySet().iterator();while(iter.hasNext()) {
       Map.Entry entry = (Map.Entry)iter.next();    // 获取key    key = entry.getKey();   // 获取value    value =entry.getValue();}

2.遍历key

Iterator iter = map.keySet().iterator();while (iter.hasNext()) {
       // 获取key    key = (String)iter.next();    // 根据key，获取value    integ = (Integer)map.get(key);}

3.遍历value

Collection c = map.values();Iterator iter= c.iterator();while (iter.hasNext()) {
       value = iter.next();}

最后说一句

最后提一下曾经看到过的面试题：为什么不用平衡二叉树为底层实现？

先说一下平衡二叉树的特点：高度平衡，每次修改都要rebalance，这个代价有点大。在插入新节点上，他俩都最多两次旋转；但是删除就不一样了，红黑树最多3次旋转，平衡二叉树需要维护当前节点到root路径上的所有平衡。一个O(1),一个O(log n)，维持平衡的动作多了，rebalance的次数就多。所有，红黑树才更适合大量的插入、删除