IT虾米网

Java容器(七):TreeMap源码分析

mate10pro 2018年06月08日 编程语言 1222 0

  TreeMap内部是使用红黑树的数据结构来实现的,同时,TreeSet的内部各方法的原理都是通过TreeMap来操作的,所以要想弄懂TreeMap,红黑树一定要要懂,懂了红黑树,再来看TreeMap的源码,还是很容易的!
  看此篇文章前,请看我的另一篇红黑树文章:红黑树精讲

一、红黑树的要点

红黑树的4个规则:(必须牢记)

  1.每个节点不是红色就是黑色的;
  2.根节点总是黑色的;
  3.如果节点是红色的,则它的子节点必须是黑色的(反之不一定);
  4.从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)。
  (注意:有些资料说每个叶节点(NIL节点,空节点)是黑色的,这里说的叶节点其实指的是NIL节点和空节点,而对于一个Node节点来说是可以为红色的)

左旋:

这里写图片描述

右旋:

这里写图片描述

二、TreeMap的数据结构

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

  TreeMap继承了AbstractMap,实现了NavigableMap接口,而NavigableMap接口实现了SortMap接口,因此说TreeMap是有序的Map

  TreeMap的成员变量

    private final Comparator<? super K> comparator; //根节点 private transient Entry<K,V> root = null; //map的大小 private transient int size = 0; //和fast-fail机制相关 private transient int modCount = 0; //节点颜色 红色 private static final boolean RED   = false; //节点颜色 黑色 private static final boolean BLACK = true;

  Comparator接口是一个是用于对集合或数组进行排序的结构,modeCount与fast-fail机制相关。

  我们来看看TreeMap的数据结构Entry:

    static final class Entry<K,V> implements Map.Entry<K,V> { 
        K key; 
        V value; //左子节点 
        Entry<K,V> left = null; //右子节点 
        Entry<K,V> right = null; //父节点 
        Entry<K,V> parent; //节点颜色 
        boolean color = BLACK; 
 
        Entry(K key, V value, Entry<K,V> parent) { 
            this.key = key; 
            this.value = value; 
            this.parent = parent; 
        }

  跟红黑树精讲中的数据结构基本一致

  TreeMap的构造方法有4个
  TreeMap() :使用键的自然顺序构造一个新的、空的树映射。
  TreeMap(Comparator< ? super K> comparator):构造一个新的、空的树映射,该映射根据给定比较器进行排序
  TreeMap(Map< ? extends K,? extends V> m):构造一个与给定映射具有相同映射关系的新的树映射,该映射根据其键的自然顺序 进行排序
  TreeMap(SortedMap

三、TreeMap的存储实现

TreeMap存储的算法即使红黑树的插入算法,这里不再多说,给出具体注释:

    public V put(K key, V value) { //父节点 
        Entry<K,V> t = root; //如果根节点为空,把当前插入的节点当做根节点 if (t == null) { //个人不知道这一步用来干嘛的 
            compare(key, key); 
            root = new Entry<>(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 不为 null,则按照指定的排序算法comparator来插入 if (cpr != null) { do { //一开始t = root,即从root开始往下遍历找出应该插入的位置,循环把t的子节点赋给t,t表示当前遍历节点 parent = t; //比较当前遍历节点和待插入节点的key值 
                cmp = cpr.compare(key, t.key); //如果待插入节点 < 当前遍历节点,则应该把待插入节点插入到当前节点的左子树 if (cmp < 0) 
                    t = t.left; //反之,应该插入到当前节点的右子树 else if (cmp > 0) 
                    t = t.right; else//如果待插入节点 = 当前遍历节点,说明key相同,则用新值替代旧值,并把旧值返回 return t.setValue(value); 
            } while (t != null); 
        } else {//如果comparator为null,则按照默认的排序算法来排序 //如果key为空,抛出异常,可见,Map中只有HashMap系列才允许把null作为键 if (key == null) throw new NullPointerException(); //默认的排序算法 
            Comparable<? super K> k = (Comparable<? super K>) key; //这里和上面的步骤一样,只是用来比较大小的comparator 不一样 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); 
        } //到这里,说明找到了待插入的位置,用key-value创建新节点 
        Entry<K,V> e = new Entry<>(key, value, parent); 
       //如果插入结点的key < 插入位置父节点的key,则插入到父节点左边 if (cmp < 0) parent.left = e; //否则,插入到右边 else parent.right = e; 
 //红黑树插入,最关键的就是这里,插入后的平衡调整 
        fixAfterInsertion(e); //容量加1 
        size++; 
        modCount++; return null; 
    }

下面来看看最关键的平衡调整:

    //x为插入结点 private void fixAfterInsertion(Entry<K,V> x) { //插入的节点初始颜色都为红色 
        x.color = RED; 
 //当x不为null,且不为根节点,且x的父节点为红的时候,此时违反规则3:父节点为红色,其子节点为黑;如果x为root,直接跳到最后,设置root为黑色 while (x != null && x != root && x.parent.color == RED) { //这里可以分开来,parentOf(x)指x的父节点,parentOf(parentOf(x))为x的祖父节点,这句话的意思是说:如果x的父节点是x的祖父节点的左节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { //很明显,y指得是x的叔叔节点 
                Entry<K,V> y = rightOf(parentOf(parentOf(x))); 
 
           /** 
           要记得,插入调整,一共有3种情况: 
        1. 插入节点的父节点和其叔叔节点(祖父节点的另一个子节点)均为红色的; 
        2. 插入节点的父节点是红色,叔叔节点是黑色,且插入节点是其父节点的右子节点; 
        3. 插入节点的父节点是红色,叔叔节点是黑色,且插入节点是其父节点的左子节点。 
           **/ //这里是case1 if (colorOf(y) == RED) { //把插入结点x的父节点涂为黑色 
                    setColor(parentOf(x), BLACK); //把插入结点x的叔叔节点涂为黑色 
                    setColor(y, BLACK); //把x的祖父节点涂为红色 
                    setColor(parentOf(parentOf(x)), RED); //并把当前节点x指向它的祖父节点,变成第2种情况了 
                    x = parentOf(parentOf(x)); 
 
                 //注意:红黑树精讲中,在第1中情况后,使用continu终结此层,开始第2次循环,和这里的效果是一样的(个人觉得TreeMap这样写更好) 
                } else { //这里是case2 if (x == rightOf(parentOf(x))) { //把x指向x的父节点,注意第一种情况中,x指向了插入位置的祖父节点,这一步之后,x会指向插入位置的祖父节点的父节点 
                        x = parentOf(x); //以x节点为中心,左旋 
                        rotateLeft(x); 
                    } 
 //第2种情况后,必定会来到第3种情况 //这里是case3 //把x的父节点涂为黑色 
                    setColor(parentOf(x), BLACK); //把x的祖父节点涂为红色 
                    setColor(parentOf(parentOf(x)), RED); 
                    以x的祖父节点为中心,右旋 
                    rotateRight(parentOf(parentOf(x))); 
                } 
            } else {//这里和上面的情况相反,不懂可以看 红黑树精讲 
                Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { 
                    setColor(parentOf(x), BLACK); 
                    setColor(y, BLACK); 
                    setColor(parentOf(parentOf(x)), RED); 
                    x = parentOf(parentOf(x)); 
                } else { if (x == leftOf(parentOf(x))) { 
                        x = parentOf(x); 
                        rotateRight(x); 
                    } 
                    setColor(parentOf(x), BLACK); 
                    setColor(parentOf(parentOf(x)), RED); 
                    rotateLeft(parentOf(parentOf(x))); 
                } 
            } 
        } //到最后把根节点涂为黑色,就完成了整个的插入过程 
        root.color = BLACK; 
    }

四、TreeMap的删除 remove

    public V remove(Object key) { //查找对应key的节点 
        Entry<K,V> p = getEntry(key); //如果不存在,返回null if (p == null) return null; 
 
        V oldValue = p.value; //进行删除节点操作 
        deleteEntry(p); //返回旧值 return oldValue; 
    }

  删除的流程是,首先查找key对应的节点,找到了然后开始删除该节点,查找节点的方法:

    final Entry<K,V> getEntry(Object key) { // 如果有自定义的比较算法,则用自定义的comparator去查找,getEntryUsingComparator的流程和下面的一样 if (comparator != null) return getEntryUsingComparator(key); if (key == null) throw new NullPointerException(); //默认的比较算法 
        Comparable<? super K> k = (Comparable<? super K>) key; //p表示当前节点,从根节点开始,深度比较查找 
        Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); //如果传入的key 小于 当前节点的key,则往当前节点的左子树查找 if (cmp < 0) 
                p = p.left; //如果传入的key 大于 当前节点的key,则往右子树查找 else if (cmp > 0) 
                p = p.right; //如果传入的key 等于 当前节点的key,找到了返回 else return p; 
        } return null; 
    }

  查找到了节点,接下来看删除的具体实现
  删除节点时,在红黑树 精讲讲过,一共分3种情况:
  1. 如果待删除节点没有子节点,那么直接删掉即可;
  2. 如果待删除节点只有一个子节点,那么直接删掉,并用其子节点去顶替它;(如果待删除的节点是黑色的,删除该节点会影响高度,所以用子节点顶替时要把子节点颜色改为黑色;如果待删除节点时红色的,则可以直接顶替)
  3. 如果待删除节点有两个子节点,这种情况比较复杂:1)首选找出它的后继节点;2)然后处理“后继节点”和“被删除节点的父节点”之间的关系;3)最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系

    private void deleteEntry(Entry<K,V> p) { 
        modCount++;//修改次数+1 
        size--;//容量-1 
 // 如果待删除节点有左右两个孩子,是第3种情况,此时通过successor查找中继节点(待删除节点右子节点的最左 或 待删除节点左子节点的最右) if (p.left != null && p.right != null) { //第1步:找出后继结点 
            Entry<K,V> s = successor(p); //第2步:用后继结点替换待删除节点,为了不让树失去平衡,所以保留待删除节点的颜色,而用后继结点的key和value替换,这样,会影响树的平衡性的因素就是后继结点的颜色 
            p.key = s.key; 
            p.value = s.value; //把p 指向后继结点 
            p = s; 
        }  //由于待删除节点已经被后继结点覆盖了,于是我们的删除工作就转到后继节点这里了,此时p指向后继结点 
 // 这里很巧妙,因为successor查找后继结点中,分为两种情况查找,左子树和右子树,这样,在这里就不用分开两个情况来写重复的逻辑代码; //replacement是后继结点的子节点,可能为左节点,也可能为右节点(这里的replacemeng和红黑树精讲不太一样,红黑树的replace指向后继结点,注意区分) 
        Entry<K,V> replacement = (p.left != null ? p.left : p.right); //第3步:处理后继结点的子节点和后继节点的父节点的关系 if (replacement != null) { //替代节点的父引用 指向 p的父节点(p是replace的父节点) 
            replacement.parent = p.parent; //如果后继节点p的父节点为null,说明它是根节点,所以replacement为根节点 if (p.parent == null) 
                root = replacement; 
             //如果后继结点p是它父节点的左子节点,则把替换节点放在后继结点的父节点的左子位置 else if (p == p.parent.left) 
                p.parent.left  = replacement; //否则放在右子位置 else 
                p.parent.right = replacement; 
 // 把后继结点删除 
            p.left = p.right = p.parent = null; 
 // 如果后继结点是黑色的,删除必然导致失衡,所以进行修复 if (p.color == BLACK) 
                fixAfterDeletion(replacement); 
        } else if (p.parent == null) { // 如果后继结点是根节点,则直接删除 
            root = null; 
        } else { // 如果后继结点没有没有孩子的情况 //没有孩子的情况,如果后继节点为黑色时,删除必定导致失衡,所以要修复 if (p.color == BLACK) 
                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; 
            } 
        } 
    }

  (1)查找后继结点的方法:successor(p)

    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; 
         /*  
         * 寻找右子树的最左子树  
         */  else if (t.right != null) { 
            Entry<K,V> p = t.right; while (p.left != null) 
                p = p.left; return p; 
        } else { /*  
         * 选择左子树的最右子树  
         */  
            Entry<K,V> p = t.parent; 
            Entry<K,V> ch = t; while (p != null && ch == p.right) { 
                ch = p; 
                p = p.parent; 
            } return p; 
        } 
    }

(2)平衡修复:fixAfterDeletion,这里的修复和红黑树精讲的一样,不懂的看红黑树精讲

    private void fixAfterDeletion(Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { 
                Entry<K,V> 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; 
                } 
            } else { // symmetric 
                Entry<K,V> 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); 
    }

五、总结

TreeMap可以说是Map当中最重要的map之一,同时TreeSet内部就是通过TreeMap来实现的,所以弄懂了TreeMap,再来看TreeSet也只是分分钟的事情,不过红黑树确实是数据结构算最难的一部分了,需要细心分析

评论关闭
IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!