容器学习五：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;
        }
    }