最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

世界热点!3、TreeMap源码解析

来源:博客园
目录
  • 1 TreeMap基本介绍
  • 2 红黑树数据结构回顾
  • 3 成员变量
  • 4 内部类Entry
  • 5 构造函数
  • 6 重要方法分析
    • 6.1 get方法分析
    • 6.2 put方法分析
    • 6.3 插入调整函数fixAfterInsertion()解析
    • 6.4 删除方法remove()解析
    • 6.5 删除调整函数fixAfterDeletion()解析
    • 6.6 寻找后继函数successor()解析
  • 7 解惑:
      • 1 TreeMap支持key自定义排序,而红黑树对key的固定的排序规则,两者如何兼容的?

1 TreeMap基本介绍

  • Java TreeMap实现了SortedMap接口,也就是说会按照key的大小顺序对Map中的元素进行排序
  • key大小的评判可以通过其本身的自然顺序(natural ordering),也可以通过构造时传入的比较器(Comparator)。
  • TreeMap底层通过红黑树实现
  • TreeMap是非同步的。可以通过如下方式将TreeMap包装成同步的:SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
  • TreeMap 跟 HashMap是两种不同的结构,TreeMap没有使用hash相关概念

2 红黑树数据结构回顾

  1. 每个节点颜色不是黑色,就是红色
  2. 根节点是黑色的
  3. 红色节点不能连续
  4. 对于每个节点,从该节点到其树尾端的简单路径上,均包含相同数目的黑色节点

3 成员变量

private final Comparator comparator;  //排序器,如果空,按照key的字典顺序来排序(升序);comparator为空时用Comparable的排序接口    private transient Entry root; //根节点    private transient int size = 0; //树中entry个数 ,即红黑树大小    private transient int modCount = 0;  //数结构被修改的次数的     /**     * Fields initialized to contain an instance of the entry set view     * the first time this view is requested.  Views are stateless, so     * there"s no reason to create more than one.     */    private transient EntrySet entrySet;    private transient KeySet navigableKeySet;    private transient NavigableMap descendingMap;     /**     * Dummy value serving as unmatchable fence key for unbounded     * SubMapIterators     */    private static final Object UNBOUNDED = new Object();    private static final boolean RED   = false; //红节点 默认false    private static final boolean BLACK = true;  // 黑节点 默认true

4 内部类Entry

它是组成树的节点的类型


(资料图片仅供参考)

static final class Entry implements Map.Entry {        K key;   // key        V value;  //value        Entry left; //左孩子        Entry right;  //右孩子        Entry parent;  //父节点        boolean color = BLACK;  //默认黑色        //根据 key  value 父节点创建新节点        Entry(K key, V value, Entry parent) {            this.key = key;            this.value = value;            this.parent = parent;        }        public K getKey() {            return key;        }        public V getValue() {            return value;        }     //替换value,返回旧value        public V setValue(V value) {            V oldValue = this.value;            this.value = value;            return oldValue;        }        // 重写equals方法:key 和 value的引用都相等        public boolean equals(Object o) {            if (!(o instanceof Map.Entry))                return false;            Map.Entry e = (Map.Entry)o;            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());        }                //重写hashCode方法,返回 key 和 value的hashCode 的异或运算结构        public int hashCode() {            int keyHash = (key==null ? 0 : key.hashCode());            int valueHash = (value==null ? 0 : value.hashCode());            return keyHash ^ valueHash;        }        public String toString() {            return key + "=" + value;        }    }

5 构造函数

// 构造函数一:不指定排序器。按照key的字典顺序来排序(升序)    public TreeMap() {        comparator = null;    }    // 构造函数二:指定排序器     public TreeMap(Comparator comparator) {        this.comparator = comparator;    }    //构造函数三:构造并返回跟参数m有相同键值映射结构的treeMap(m变为红黑树)    public TreeMap(Map m) {        comparator = null;        putAll(m);    }     //构造函数四:构造并返回跟参数m(有序的)有相同键值映射结构的treeMap    public TreeMap(SortedMap m) {        comparator = m.comparator();        try {            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);        } catch (java.io.IOException cannotHappen) {        } catch (ClassNotFoundException cannotHappen) {        }    }

Comparator Integer类型倒序排序

public static void main(String[] args) {        TreeMap treeMap = new TreeMap(new ComparatorObj());        treeMap.put(2,"ss");        treeMap.put(3,"sss");        System.out.println(treeMap);    }    static class ComparatorObj implements Comparator{        @Override        public int compare(Integer o1, Integer o2) {            return o2-o1; //倒序排序        }    }

输出结果:

2022-07-11 18:02:23,871 [INFO] main: {3=sss, 2=ss}

6 重要方法分析

6.1 get方法分析

(实际调用getEntry(Object key))

  • get(Object key)方法是对接口Map的方法实现
  • get(Object key)方法转为对getEntry(Object key)方法的实现分析:算法思想是根据key的自然顺序(或者比较器顺序)对二叉查找树进行查找,直到找到满足k.compareTo(p.key) == 0的entry,再返回entry的value。

源码分析如下:

public V get(Object key) {    Entry p = getEntry(key);  //根据key找到entry,再返回其value    return (p==null ? null : p.value);}//重点分析该方法final Entry getEntry(Object key) {    if (comparator != null)        return getEntryUsingComparator(key);     if (key == null)        throw new NullPointerException();  //key非空校验    @SuppressWarnings("unchecked")    Comparable k = (Comparable) key;  //自然顺序,使用Comparable的排序接口    Entry p = root;     while (p != null) {  //从根节点开始 循环遍历        int cmp = k.compareTo(p.key);  //compareTo:左边减去右边        if (cmp < 0) //参数key值小于父节点key            p = p.left; //取左子节点        else if (cmp > 0)            p = p.right;  //参数key值大于父节点key,取右子节点        else            return p;  //key相等,则直接返回当前entry    }    return null;}

查询方法说明

  1. 在while循环外,创建动态游标节点,游标首次指向root节点,以游标!=null作为循环条件
  2. 在while循环内,根据compareTo结果,取游标的左子节点或右子节点,作为新的游标
  3. 找到满足k.compareTo(p.key) == 0的entry,退出循环

getEntryUsingComparator源码

//提供自定义排序器的查询找方法,原理类似final Entry getEntryUsingComparator(Object key) {        @SuppressWarnings("unchecked")            K k = (K) key;        Comparator cpr = comparator;        if (cpr != null) {            Entry p = root;            while (p != null) {                int cmp = cpr.compare(k, p.key); //cpr.compare 第一个参数减去第二个参数                if (cmp < 0)                    p = p.left;                else if (cmp > 0)                    p = p.right;                else                    return p;            }        }        return null;    }

6.2 put方法分析

public V put(K key, V value) {    Entry t = root;    // 情况一:根节点为空,将当前key value作为root    if (t == null) {        compare(key, key); //key为null则抛异常        root = new Entry<>(key, value, null);//初始化root        size = 1;  //叶子个数+1        modCount++; // 结构修改次数自增        return null;  //新叶子,所以old value 为空    }    // 情况二:如果找到key相同的,则更新value ,过程类似get方法    int cmp;    Entry parent;    Comparator cpr = comparator;    if (cpr != null) {        do {            parent = t;            cmp = cpr.compare(key, t.key);            if (cmp < 0)                t = t.left;            else if (cmp > 0)                t = t.right;            else                return t.setValue(value);        } while (t != null);    }    else {        if (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);    }    //情况三:没有相同的key,则添加新叶子。    //经过上面的两种遍历,完成了二分法查找,找到适合插入的地方:parent。    Entry e = new Entry<>(key, value, parent); //创建新的entry    //确定新增叶子作为parent的左孩子还是右孩子,插入的动作完成    if (cmp < 0)          parent.left = e;      else        parent.right = e;    fixAfterInsertion(e);  //插入完成后,对二叉树进行调整    size++;    modCount++;    return null;}//这个方法实际上是对key做null检查,如果是null会抛出异常(测试代码验证过)public TreeMap(Comparator comparator) {        this.comparator = comparator;  }

put方法说明

  1. 如果root为空,则新增的entry作为root
  2. 遍历搜索是否存在相同的key,存在则替换value这过程也是二叉排序树的二分查找法:找到了作为插入点的parent
  3. 插入操作:找到parent,并将其left或者right指向新的entry
  4. 如果是插入,则需要对红黑树进行结构调整。 (插入:节点默认为红色,root节点:设置为黑色,覆盖节点:颜色保持不变)
  5. 维护成员变量:size,modCount。

6.3 插入调整函数fixAfterInsertion()解析

/** From CLR */private void fixAfterInsertion(Entry x) {    x.color = RED;  //新增节点默认为红色,再进行规则判断    // 从树末端开始遍历:父节点是红色,则需要对树进行调整    while (x != null && x != root && x.parent.color == RED) {        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {            Entry y = rightOf(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 == rightOf(parentOf(x))) {                    x = parentOf(x);                    rotateLeft(x);                }                setColor(parentOf(x), BLACK);                setColor(parentOf(parentOf(x)), RED);                rotateRight(parentOf(parentOf(x)));            }        } else {            Entry 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;  //在遍历外面,确保root一定是黑色}

方法说明

  1. 新增的节点默认为红色,并从树末端往上遍历
  2. 如果新增节点的父亲是红色,则需要进行结构调整
  3. 结构调整这部分有点复杂,回头再深入理解todo

6.4 删除方法remove()解析

知识回顾:二叉排序树的删除过程:(情况一,treeMap用后继代替,其实用前驱或者后继是一样的)

源码如下:

// 调用getEntry(key)找到对应entry,调用deleteEntry 删除节点public V remove(Object key) {    Entry p = getEntry(key);    if (p == null)        return null;    V oldValue = p.value;    deleteEntry(p);    return oldValue;}//执行删除操作private void deleteEntry(Entry p) {     //先对全局变量modCount、size 进行调整    modCount++;    size--;        //情况1:左右孩子都不为空:后继节点代替    if (p.left != null && p.right != null) {        Entry s = successor(p); //寻找后继 (另外分析)        //将删除点的key、value、引用分别更新为代替节点        p.key = s.key;          p.value = s.value;        p = s;   //    }    //情况2:有1个孩子    Entry replacement = (p.left != null ? p.left : p.right);    if (replacement != null) {        replacement.parent = p.parent;  //左孩子父亲更新删除节点的父亲        //父亲为root,则后继变为新的root        if (p.parent == null)            root = replacement;          //左孩子顶上        else if (p == p.parent.left)            p.parent.left  = replacement;        //右孩子顶上        else            p.parent.right = replacement;        // 删除节点的left、right、parent置空:被移除出树        p.left = p.right = p.parent = null;        // 删除黑色节点:调整结构        if (p.color == BLACK)            fixAfterDeletion(replacement);    } else if (p.parent == null) { //删除root节点        root = null;    } else { //  情况1:没孩子        if (p.color == BLACK)            fixAfterDeletion(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. 删除过程遵从二叉排序树的删除特点(1、有一个孩子则孩子顶上;2两个孩子就用后继顶上,没有孩子则直接移除
  2. 节点删除,即left、right、parent置空;删除后,需要更新父亲节点的的左孩子或右孩子
  3. 考虑是否需要更新全局变量root节点
  4. 只有删除点是BLACK的时候,才会触发调整函数,因为删除RED节点不会破坏红黑树的任何约束,而删除BLACK节点会破坏规则4。

6.5 删除调整函数fixAfterDeletion()解析

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

说明:结构调整这部分有点复杂,回头再深入理解todo

6.6 寻找后继函数successor()解析

//寻找任意节点后继    static  TreeMap.Entry successor(Entry t) {        if (t == null)            return null;            //情况1:右孩子不为空,向后代遍历:找到右孩子中孙子最小的那个节点(不断寻找left,直至为空)        else if (t.right != null) {            Entry p = t.right;            while (p.left != null)                p = p.left;            return p;        } else {        // 情况2:右孩子为空,向祖先遍历,当任意节点是它父亲的左孩子时,则该节点的父亲为t的后继            Entry p = t.parent;            Entry ch = t;            while (p != null && ch == p.right) {                ch = p;                p = p.parent;            }            return p;        }    }

寻找后继的算法说明:对于任意k:

  1. 情况一:k的右孩子不为空,向后代遍历:找到右孩子的子孙子中辈分最低的左孩子(不断寻找left,直至为空)
  2. 情况二:key的右孩子为空,向祖先遍历:当任意节点是它父亲的左孩子时,则该节点的父亲为t的后继

右孩子不为空的后继寻找:

右孩子为空为空的后继寻找

7 解惑:

1 TreeMap支持key自定义排序,而红黑树对key的固定的排序规则,两者如何兼容的?

  1. 支持key自定义排序:指通过自定义的排序器,计算出任意key相对其它key的大小关系
  2. 红黑树对key的固定的排序:指按照红黑树的数据结构(二叉排序树+红黑节点规则),来组织key的树状结构,其中二叉排序的大小关系是根据排序器的计算出来的
  3. 两者不冲突

关键词: 构造函数 二叉排序树 成员变量