Java集合-TreeMap源码解析-JDK1.8

/**     * 红黑树节点     */    static final class Entry<K,V> implements Map.Entry<K,V> {        K key;        V value;        TreeMap.Entry<K,V> left;        TreeMap.Entry<K,V> right;        TreeMap.Entry<K,V> parent;        boolean color = BLACK;                Entry(K key, V value, TreeMap.Entry<K,V> parent) {            this.key = key;            this.value = value;            this.parent = parent;        }    }

    // 比较器对象    private final Comparator<? super K> comparator;    //根节点对象    private transient TreeMap.Entry<K,V> root;    //集合的大小    private transient int size = 0;    //结构被修改的次数    private transient int modCount = 0;

 /**     * 使用默认比较器     * key的类型是什么     * 就采用该类型的compareTo方法来比较大小     * 例如key为String类型，就会用String类的compareTo方法比对大小     */    public TreeMap() {        comparator = null;    }
    /**     * 指定比较器     */    public TreeMap(Comparator<? super K> comparator) {        this.comparator = comparator;    }
    /**     * 添加集合     */    public TreeMap(Map<? extends K, ? extends V> m) {        comparator = null;        putAll(m);    }
    /**     * 将m转换为TreeMap，使用m的比较器     */    public TreeMap(SortedMap<K, ? extends V> m) {        comparator = m.comparator();        try {            buildFromSorted(m.size(), m.entrySet().iterator(), null, null);        } catch (java.io.IOException cannotHappen) {        } catch (ClassNotFoundException cannotHappen) {        }    }

/**     * 添加方法     */    public V put(K key, V value) {        TreeMap.Entry<K,V> t = root;        //如果跟节点为空，把此节点置为跟节点        if (t == null) {            compare(key, key); // type (and possibly null) check
            root = new TreeMap.Entry<>(key, value, null);            size = 1;            modCount++;            return null;        }        int cmp;        TreeMap.Entry<K,V> parent;        // split comparator and comparable paths        Comparator<? super K> 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<? 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);        }        // 根据key找到父节点后新建一个节点        TreeMap.Entry<K,V> e = new TreeMap.Entry<>(key, value, parent);        // 根据比较的结果来确定放在左子树还是右子树        if (cmp < 0)            parent.left = e;        else            parent.right = e;        // 插入完成，红黑树的结构会被破坏，执行红黑树的恢复操作        fixAfterInsertion(e);        //集合大小增加        size++;        //修改次数增加        modCount++;        return null;    }

 /**     * 根据key获取     */    public V get(Object key) {        TreeMap.Entry<K,V> p = getEntry(key);        return (p==null ? null : p.value);    }    /**     * 根据key获取Entry对象     */    final TreeMap.Entry<K,V> getEntry(Object key) {        // Offload comparator-based version for sake of performance        if (comparator != null)            return getEntryUsingComparator(key);        if (key == null)            throw new NullPointerException();        @SuppressWarnings("unchecked")        Comparable<? super K> k = (Comparable<? super K>) key;        TreeMap.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;        }        return null;    }

/**     * 删除节点     */    public V remove(Object key) {        //查找元素是否存在        TreeMap.Entry<K,V> p = getEntry(key);        if (p == null)            return null;        V oldValue = p.value;        //调用具体的删除方法        deleteEntry(p);        return oldValue;    }     /**     * 具体的删除方法     */    private void deleteEntry(TreeMap.Entry<K,V> p) {        modCount++;        size--;
        // 如果待删除节点有两个子节点        if (p.left != null && p.right != null) {            TreeMap.Entry<K,V> s = successor(p);            p.key = s.key;            p.value = s.value;            p = s;        } // p has 2 children
        // Start fixup at replacement node, if it exists.        TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right);        //待删除节点只有一个孩子        if (replacement != null) {            // Link replacement to parent            replacement.parent = p.parent;            if (p.parent == null)                root = replacement;            else if (p == p.parent.left)                p.parent.left  = replacement;            else                p.parent.right = replacement;
            // Null out links so they are OK to use by fixAfterDeletion.            p.left = p.right = p.parent = null;
            // Fix replacement            if (p.color == BLACK)                fixAfterDeletion(replacement);            //如果是根节点        } else if (p.parent == null) { // return if we are the only node.            root = null;        } else { //  没有子节点            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;            }        }    }