zy19982004--容器学习五：TreeMap源码分析

一.TreeMap成员变量

//Comparator比较器接口，接口里面只有两个方法int compare(T o1, T o2);boolean equals(Object obj);
private final Comparator<? super K> comparator;

//根节点
private transient Entry<K,V> root = null;

private transient int size = 0;
private transient int modCount = 0;

 

二.TreeMap的Entry对象

static final class Entry<K,V> implements Map.Entry<K,V> {
        //构成树的三个属性left，left，parent
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;    //该节点红色还是黑色
    }

 

三.构造函数

//默认构造函数时comparator为空，则插入到TreeMap里面的key必须实现Comparator接口
public TreeMap() {
    comparator = null;
}

//用户指定Comparator
public TreeMap(Comparator<? super K> comparator) {
    this.comparator = comparator;
}

 

四.取数据

   public V get(Object key) {
       Entry<K,V> p = getEntry(key);
       return (p==null ? null : p.value);
   }

   final Entry<K,V> getEntry(Object key) {
       //如果用户指定了Comparable，用指定的
       if (comparator != null)
           return getEntryUsingComparator(key);
       //get操作key不能为空
       if (key == null)
           throw new NullPointerException();
   //如果用户没指定Comparable，用key作为Comparable
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;
       }
       //找不到返回null
       return null;
   }

   //和上面逻辑一样
   final Entry<K,V> getEntryUsingComparator(Object key) {
    K k = (K) key;
           Comparator<? super K> cpr = comparator;
           if (cpr != null) {
               Entry<K,V> p = root;
               while (p != null) {
                   int cmp = cpr.compare(k, p.key);
                   if (cmp < 0)
                       p = p.left;
                   else if (cmp > 0)
                       p = p.right;
                   else
                       return p;
               }
           }
           return null;
       }

 

五.存数据

//返回被新节点覆盖的节点的值，不存在被覆盖的节点返回null
    public V put(K key, V value) {
        Entry<K,V> t = root;
        if (t == null) {
        // TBD:
        // 5045147: (coll) Adding null to an empty TreeSet should
        // throw NullPointerException
        //
        // compare(key, key); // type check
            //第一次插入节点
            root = new Entry<K,V>(key, value, null);
            size = 1;
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        //用指定的Comparator
        if (cpr != null) {
            //以根节点当前节点t开始搜索，拿被添加的节点的值和当前节点的值比较。
            do {
                //刚开始parent=t
                parent = t;
                cmp = cpr.compare(key, t.key);
                //如果被添加的节点的值更小，则以当前节点的左子节点作为新的当前节点，此时t=pL
                if (cmp < 0)
                    t = t.left;
                //如果被添加的节点的值更大，则以当前节点的右子节点作为新的当前节点，此时t=pR
                else if (cmp > 0)
                    t = t.right;
                //如果相等，直接覆盖
                else
                    return t.setValue(value);
            } while (t != null); //直到新的当前节点为空
        }
        else {
            //put操作key不能为空
            if (key == null)
                throw new NullPointerException();
            //用key作为Comparator，下同
            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);
        }
        //生成一个新节点，父亲为parent
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        //根据最后一次比较的cmp确定pL位置存放e还是pR存放e
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        //修复红黑树
        fixAfterInsertion(e);
        size++;
        modCount++;
        //插入一个新节点时返回null
        return null;
    }

 

六.删数据

public V remove(Object key) {
    //先找到节点，getEntry(key)key不能为空，所以remove方法key不能为空
    Entry<K,V> p = getEntry(key);
    if (p == null)
        return null;

    //保留一个节点的值
    V oldValue = p.value;
    //删除节点
    deleteEntry(p);
    return oldValue;
}

private void deleteEntry(Entry<K,V> p) {
    modCount++;
    size--;

    //若被删除节点 p 的左、右子树均非空
    if (p.left != null && p.right != null) {
        //得到p节点的中序后继s
        Entry<K,V> s = successor (p);
        //用s替代p
        p.key = s.key;
        p.value = s.value;
        p = s;
    }

    //如果p节点的左节点存在，replacement代表左节点，否则代表右节点
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);

    if (replacement != null) {
        replacement.parent = p.parent;
        //　如果　p　没有父节点，则　replacemment　变成父节点
        if (p.parent == null)
            root = replacement;
        //　如果　p　节点是其父节点的左子节点
        else if (p == p.parent.left)
            p.parent.left  = replacement;
        //　如果　p　节点是其父节点的右子节点
        else
            p.parent.right = replacement;

        p.left = p.right = p.parent = null;

        // Fix replacement
        if (p.color == BLACK)
             //　修复红黑树
            fixAfterDeletion(replacement);
     //　如果　p　节点没有父节点
    } else if (p.parent == null) { // return if we are the only node.
        root = null;
    } else { //  No children. Use self as phantom replacement and unlink.
        if (p.color == BLACK)
            //　修复红黑树
            fixAfterDeletion(p);

        if (p.parent != null) {
            //　如果　p　是其父节点的左子节点
            if (p == p.parent.left)
                p.parent.left = null;
            //　如果　p　是其父节点的右子节点
            else if (p == p.parent.right)
                p.parent.right = null;
            p.parent = null;
        }
    }
}

 

七.containsKey containsValue方法

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }

    //按中序遍历节点的顺序，把节点和指定value比较
    public boolean containsValue(Object value) {
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }


static final class Entry<K,V> implements Map.Entry<K,V> {
    //找到最小的节点
    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;
    }
}
 //找到指定节点的后继节点
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
        if (t == null)
            return null;
        //如果t有右子数
        else if (t.right != null) {
            Entry<K,V> p = t.right;
            //tRL不为空，tRL就是t的直接后继；tRLL不为空，tRLL就是t的直接后继......
            while (p.left != null)
                p = p.left;
            return p;
        //如果t只有左子数
        } else {
            //如果t=pL，直接返回p
            //如果t=pR，返回p.parent
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.right) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

//找到指定节点的前驱节点
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
        if (t == null)
            return null;
        //如果t有左子数
        else if (t.left != null) {
            Entry<K,V> p = t.left;
            //tLR不为空，tLR就是t的直接后继；tLRR不为空，tLRR就是t的直接后继......
            while (p.right != null)
                p = p.right;
            return p;
        } else {
            //如果t=pR，直接返回p
            //如果t=pL，返回p.parent
            Entry<K,V> p = t.parent;
            Entry<K,V> ch = t;
            while (p != null && ch == p.left) {
                ch = p;
                p = p.parent;
            }
            return p;
        }
}

 

八.fixAfterInsertion方法

  //　插入节点后修复红黑树
private　void　fixAfterInsertion(Entry<K,V>　x)
{
 x.color　=　RED;
 //　直到　x　节点的父节点不是根，且　x　的父节点不是红色
 while　(x　!=　null　&&　x　!=　root
　　 &&　x.parent.color　==　RED)
 {
　　 //　如果　x　的父节点是其父节点的左子节点
　　 if　(parentOf(x)　==　leftOf(parentOf(parentOf(x))))
　　 {
　　　　 //　获取　x　的父节点的兄弟节点
　　　　 Entry<K,V>　y　=　rightOf(parentOf(parentOf(x)));
　　　　 //　如果　x　的父节点的兄弟节点是红色
　　　　 if　(colorOf(y)　==　RED)
　　　　 {
　　　　　　 //　将　x　的父节点设为黑色
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　将　x　的父节点的兄弟节点设为黑色
　　　　　　 setColor(y,　BLACK);
　　　　　　 //　将　x　的父节点的父节点设为红色
　　　　　　 setColor(parentOf(parentOf(x)),　RED);
　　　　　　 x　=　parentOf(parentOf(x));
　　　　 }
　　　　 //　如果　x　的父节点的兄弟节点是黑色
　　　　 else
　　　　 {
　　　　　　 //　如果　x　是其父节点的右子节点
　　　　　　 if　(x　==　rightOf(parentOf(x)))
　　　　　　 {
　　　　　　　　 //　将　x　的父节点设为　x
　　　　　　　　 x　=　parentOf(x);
　　　　　　　　 rotateLeft(x);
　　　　　　 }
　　　　　　 //　把　x　的父节点设为黑色
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　把　x　的父节点的父节点设为红色
　　　　　　 setColor(parentOf(parentOf(x)),　RED);
　　　　　　 rotateRight(parentOf(parentOf(x)));
　　　　 }
　　 }
　　 //　如果　x　的父节点是其父节点的右子节点
　　 else
　　 {
　　　　 //　获取　x　的父节点的兄弟节点
　　　　 Entry<K,V>　y　=　leftOf(parentOf(parentOf(x)));
　　　　 //　如果　x　的父节点的兄弟节点是红色
　　　　 if　(colorOf(y)　==　RED)
　　　　 {
　　　　　　 //　将　x　的父节点设为黑色。
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　将　x　的父节点的兄弟节点设为黑色
　　　　　　 setColor(y,　BLACK);
　　　　　　 //　将　x　的父节点的父节点设为红色
　　　　　　 setColor(parentOf(parentOf(x)),　RED);
　　　　　　 //　将　x　设为　x　的父节点的节点
　　　　　　 x　=　parentOf(parentOf(x));
　　　　 }
　　　　 //　如果　x　的父节点的兄弟节点是黑色
　　　　 else
　　　　 {
　　　　　　 //　如果　x　是其父节点的左子节点
　　　　　　 if　(x　==　leftOf(parentOf(x)))
　　　　　　 {
　　　　　　　　 //　将　x　的父节点设为　x
　　　　　　　　 x　=　parentOf(x);
　　　　　　　　 rotateRight(x);
　　　　　　 }
　　　　　　 //　把　x　的父节点设为黑色
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　把　x　的父节点的父节点设为红色
　　　　　　 setColor(parentOf(parentOf(x)),　RED);
　　　　　　 rotateLeft(parentOf(parentOf(x)));
　　　　 }
　　 }
 }
 //　将根节点设为黑色
 root.color　=　BLACK;
}

 

 

九.fixAfterDeletion方法

  //　删除节点后修复红黑树
private　void　fixAfterDeletion(Entry<K,V>　x)
{
 //　直到　x　不是根节点，且　x　的颜色是黑色
 while　(x　!=　root　&&　colorOf(x)　==　BLACK)
 {
　　 //　如果　x　是其父节点的左子节点
　　 if　(x　==　leftOf(parentOf(x)))
　　 {
　　　　 //　获取　x　节点的兄弟节点
　　　　 Entry<K,V>　sib　=　rightOf(parentOf(x));
　　　　 //　如果　sib　节点是红色
　　　　 if　(colorOf(sib)　==　RED)
　　　　 {
　　　　　　 //　将　sib　节点设为黑色
　　　　　　 setColor(sib,　BLACK);
　　　　　　 //　将　x　的父节点设为红色
　　　　　　 setColor(parentOf(x),　RED);
　　　　　　 rotateLeft(parentOf(x));
　　　　　　 //　再次将　sib　设为　x　的父节点的右子节点
　　　　　　 sib　=　rightOf(parentOf(x));
　　　　 }
　　　　 //　如果　sib　的两个子节点都是黑色
　　　　 if　(colorOf(leftOf(sib))　==　BLACK
　　　　　　 &&　colorOf(rightOf(sib))　==　BLACK)
　　　　 {
　　　　　　 //　将　sib　设为红色
　　　　　　 setColor(sib,　RED);
　　　　　　 //　让　x　等于　x　的父节点
　　　　　　 x　=　parentOf(x);
　　　　 }
　　　　 else
　　　　 {
　　　　　　 //　如果　sib　的只有右子节点是黑色
　　　　　　 if　(colorOf(rightOf(sib))　==　BLACK)
　　　　　　 {
　　　　　　　　 //　将　sib　的左子节点也设为黑色
　　　　　　　　 setColor(leftOf(sib),　BLACK);
　　　　　　　　 //　将　sib　设为红色
　　　　　　　　 setColor(sib,　RED);
　　　　　　　　 rotateRight(sib);
　　　　　　　　 sib　=　rightOf(parentOf(x));
　　　　　　 }
　　　　　　 //　设置　sib　的颜色与　x　的父节点的颜色相同
　　　　　　 setColor(sib,　colorOf(parentOf(x)));
　　　　　　 //　将　x　的父节点设为黑色
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　将　sib　的右子节点设为黑色
　　　　　　 setColor(rightOf(sib),　BLACK);
　　　　　　 rotateLeft(parentOf(x));
　　　　　　 x　=　root;
　　　　 }
　　 }
　　 //　如果　x　是其父节点的右子节点
　　 else
　　 {
　　　　 //　获取　x　节点的兄弟节点
　　　　 Entry<K,V>　sib　=　leftOf(parentOf(x));
　　　　 //　如果　sib　的颜色是红色
　　　　 if　(colorOf(sib)　==　RED)
　　　　 {
　　　　　　 //　将　sib　的颜色设为黑色
　　　　　　 setColor(sib,　BLACK);
　　　　　　 //　将　sib　的父节点设为红色
　　　　　　 setColor(parentOf(x),　RED);
　　　　　　 rotateRight(parentOf(x));
　　　　　　 sib　=　leftOf(parentOf(x));
　　　　 }
　　　　 //　如果　sib　的两个子节点都是黑色
　　　　 if　(colorOf(rightOf(sib))　==　BLACK
　　　　　　 &&　colorOf(leftOf(sib))　==　BLACK)
　　　　 {
　　　　　　 //　将　sib　设为红色
　　　　　　 setColor(sib,　RED);
　　　　　　 //　让　x　等于　x　的父节点
　　　　　　 x　=　parentOf(x);
　　　　 }
　　　　 else
　　　　 {
　　　　　　 //　如果　sib　只有左子节点是黑色
　　　　　　 if　(colorOf(leftOf(sib))　==　BLACK)
　　　　　　 {
　　　　　　　　 //　将　sib　的右子节点也设为黑色
　　　　　　　　 setColor(rightOf(sib),　BLACK);
　　　　　　　　 //　将　sib　设为红色
　　　　　　　　 setColor(sib,　RED);
　　　　　　　　 rotateLeft(sib);
　　　　　　　　 sib　=　leftOf(parentOf(x));
　　　　　　 }
　　　　　　 //　将　sib　的颜色设为与　x　的父节点颜色相同
　　　　　　 setColor(sib,　colorOf(parentOf(x)));
　　　　　　 //　将　x　的父节点设为黑色
　　　　　　 setColor(parentOf(x),　BLACK);
　　　　　　 //　将　sib　的左子节点设为黑色
　　　　　　 setColor(leftOf(sib),　BLACK);
　　　　　　 rotateRight(parentOf(x));
　　　　　　 x　=　root;
　　　　 }
　　 }
 }
 setColor(x,　BLACK);
}

 

十.迭代

/**
     * Base class for TreeMap Iterators
     */
    abstract class PrivateEntryIterator<T> implements Iterator<T> {
        Entry<K,V> next;
        Entry<K,V> lastReturned;
        int expectedModCount;

        PrivateEntryIterator(Entry<K,V> first) {
            expectedModCount = modCount;
            lastReturned = null;
            next = first;
        }
        //后继迭代
    final Entry<K,V> nextEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            next = successor(e);
            lastReturned = e;
            return e;
        }

        //前驱迭代
        final Entry<K,V> prevEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            next = predecessor(e);
            lastReturned = e;
            return e;
        }
    }