精华内容
下载资源
问答
  • java的TreeMap

    2017-01-22 09:16:06
    知识点java中的TreeMap和C++中的Map类似,利用红黑树实现,所以插入和查找时间复杂度都是O(nlogn)。

    知识点

    java中的TreeMap和C++中的Map类似,利用红黑树实现,所以插入和查找的时间复杂度都是O(nlogn)。

    展开全文
  • TreeMap(JDK1.8)源码解析

    千次阅读 2019-10-15 17:57:39
    TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很高。另一方面,由于 TreeMap 基于红黑树实现,这为 TreeMap 保持键的有序性打下了基础。总的来说,Tree....

    简介

    TreeMap最早出现在JDK 1.2中,是 Java 集合框架中比较重要一个的实现。TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很高。另一方面,由于 TreeMap 基于红黑树实现,这为 TreeMap 保持键的有序性打下了基础。总的来说,TreeMap 的核心是红黑树,其很多方法也是对红黑树增删查基础操作的一个包装。所以只要弄懂了红黑树,TreeMap 就没什么秘密了。

    概览

    TreeMap继承自AbstractMap,并实现了 NavigableMap接口。NavigableMap 接口继承了SortedMap接口,SortedMap 最终继承自Map接口,同时 AbstractMap 类也实现了 Map 接口。以上就是 TreeMap 的继承体系,描述起来有点乱,不如看图了:
    在这里插入图片描述

    上图就是 TreeMap 的继承体系图,比较直观。这里来简单说一下继承体系中不常见的接口NavigableMapSortedMap,这两个接口见名知意。先说 NavigableMap 接口,NavigableMap 接口声明了一些列具有导航功能的方法,比如:

    /**
     * 返回红黑树中最小键所对应的 Entry
     */
    Map.Entry<K,V> firstEntry();
    
    /**
     * 返回最大的键 maxKey,且 maxKey 仅小于参数 key
     */
    K lowerKey(K key);
    
    /**
     * 返回最小的键 minKey,且 minKey 仅大于参数 key
     */
    K higherKey(K key);
    
    // 其他略
    

    通过这些导航方法,我们可以快速定位到目标的 key 或 Entry。至于 SortedMap 接口,这个接口提供了一些基于有序键的操作,比如

    /**
     * 返回包含键值在 [minKey, toKey) 范围内的 Map
     */
    SortedMap<K,V> headMap(K toKey);();
    
    /**
     * 返回包含键值在 [fromKey, toKey) 范围内的 Map
     */
    SortedMap<K,V> subMap(K fromKey, K toKey);
    
    // 其他略
    

    以上就是两个接口的介绍,很简单。至于 AbstractMap 和 Map 这里就不说了,大家有兴趣自己去看看 Javadoc 吧。关于 TreeMap 的继承体系就这里就说到这,接下来我们进入细节部分分析。

    源码分析

    JDK 1.8中的TreeMap源码有两千多行,还是比较多的。本文并不打算逐句分析所有的源码,而是挑选几个常用的方法进行分析。这些方法实现的功能分别是查找、遍历、插入、删除等,其他的方法小伙伴们有兴趣可以自己分析。TreeMap实现的核心部分是关于红黑树的实现,其绝大部分的方法基本都是对底层红黑树增、删、查操作的一个封装。如简介所说,只要弄懂了红黑树原理,TreeMap 就没什么秘密了。关于红黑树的原理,红黑树详细分析,本篇文章不会对此展开讨论。

    查找

    TreeMap基于红黑树实现,而红黑树是一种自平衡二叉查找树,所以 TreeMap 的查找操作流程和二叉查找树一致。二叉树的查找流程是这样的,先将目标值和根节点的值进行比较,如果目标值小于根节点的值,则再和根节点的左孩子进行比较。如果目标值大于根节点的值,则继续和根节点的右孩子比较。在查找过程中,如果目标值和二叉树中的某个节点值相等,则返回 true,否则返回 false。TreeMap 查找和此类似,只不过在 TreeMap 中,节点(Entry)存储的是键值对<k,v>。在查找过程中,比较的是键的大小,返回的是值,如果没找到,则返回null。TreeMap 中的查找方法是get,具体实现在getEntry方法中,相关源码如下:

    public V get(Object key) {
        Entry<K,V> p = getEntry(key);
        return (p==null ? null : p.value);
    }
    
    final 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;
        Entry<K,V> p = root;
        
        // 查找操作的核心逻辑就在这个 while 循环里
        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;
    }
    

    查找操作的核心逻辑就是getEntry方法中的while循环,大家对照上面的说的流程,自己看一下吧,比较简单,就不多说了。

    遍历

    遍历操作也是大家使用频率较高的一个操作,对于TreeMap,使用方式一般如下:

    for(Object key : map.keySet()) {
        // do something
    }
    

    for(Map.Entry entry : map.entrySet()) {
        // do something
    }
    

    从上面代码片段中可以看出,大家一般都是对 TreeMap 的 key 集合或 Entry 集合进行遍历。上面代码片段中用 foreach 遍历keySet 方法产生的集合,在编译时会转换成用迭代器遍历,等价于:

    Set keys = map.keySet();
    Iterator ite = keys.iterator();
    while (ite.hasNext()) {
        Object key = ite.next();
        // do something
    }
    

    另一方面,TreeMap 有一个特性,即可以保证键的有序性,默认是正序。所以在遍历过程中,大家会发现 TreeMap 会从小到大输出键的值。那么,接下来就来分析一下keySet方法,以及在遍历 keySet 方法产生的集合时,TreeMap 是如何保证键的有序性的。相关代码如下:

    public Set<K> keySet() {
        return navigableKeySet();
    }
    
    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }
    
    static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
        private final NavigableMap<E, ?> m;
        KeySet(NavigableMap<E,?> map) { m = map; }
    
        public Iterator<E> iterator() {
            if (m instanceof TreeMap)
                return ((TreeMap<E,?>)m).keyIterator();
            else
                return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
        }
    
        // 省略非关键代码
    }
    
    Iterator<K> keyIterator() {
        return new KeyIterator(getFirstEntry());
    }
    
    final class KeyIterator extends PrivateEntryIterator<K> {
        KeyIterator(Entry<K,V> first) {
            super(first);
        }
        public K next() {
            return nextEntry().key;
        }
    }
    
    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;
        }
    
        public final boolean hasNext() {
            return next != null;
        }
    
        final Entry<K,V> nextEntry() {
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            // 寻找节点 e 的后继节点
            next = successor(e);
            lastReturned = e;
            return e;
        }
    
        // 其他方法省略
    }
    

    上面的代码比较多,keySet 涉及的代码还是比较多的,大家可以从上往下看。从上面源码可以看出 keySet 方法返回的是KeySet类的对象。这个类实现了Iterable接口,可以返回一个迭代器。该迭代器的具体实现是KeyIterator,而 KeyIterator 类的核心逻辑是在PrivateEntryIterator中实现的。上面的代码虽多,但核心代码还是 KeySet 类和 PrivateEntryIterator 类的 nextEntry方法。KeySet 类就是一个集合,这里不分析了。而 nextEntry 方法比较重要,下面简单分析一下。

    在初始化 KeyIterator 时,会将 TreeMap 中包含最小键的 Entry 传给 PrivateEntryIterator。当调用 nextEntry 方法时,通过调用 successor 方法找到当前 entry 的后继,并让 next 指向后继,最后返回当前的 entry。通过这种方式即可实现按正序返回键值的的逻辑。

    好了,TreeMap 的遍历操作就讲到这。遍历操作本身不难,但讲的有点多,略显啰嗦,大家见怪。

    插入

    相对于前两个操作,插入操作明显要复杂一些。当往 TreeMap 中放入新的键值对后,可能会破坏红黑树的性质。这里为了描述方便,把 Entry 称为节点。并把新插入的节点称为N,N 的父节点为P。P 的父节点为G,且 P 是 G 的左孩子。P 的兄弟节点为U。在往红黑树中插入新的节点 N 后(新节点为红色),会产生下面5种情况:

    1. N 是根节点
    2. N 的父节点是黑色
    3. N 的父节点是红色,叔叔节点也是红色
    4. N 的父节点是红色,叔叔节点是黑色,且 N 是 P 的右孩子
    5. N 的父节点是红色,叔叔节点是黑色,且 N 是 P 的左孩子

    上面5种情况中,情况2不会破坏红黑树性质,所以无需处理。情况1 会破坏红黑树性质2(根是黑色),情况3、4、和5会破坏红黑树性质4(每个红色节点必须有两个黑色的子节点)。这个时候就需要进行调整,以使红黑树重新恢复平衡。至于怎么调整,可以参考红黑树详细分析,这里不再重复说明。接下来分析一下插入操作相关源码:

    public V put(K key, V value) {
        Entry<K,V> t = root;
        // 1.如果根节点为 null,将新节点设为根节点
        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;
        if (cpr != null) {
            // 2.为 key 在红黑树找到合适的位置
            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 {
            // 与上面代码逻辑类似,省略
        }
        Entry<K,V> e = new Entry<>(key, value, parent);
        // 3.将新节点链入红黑树中
        if (cmp < 0)
            parent.left = e;
        else
            parent.right = e;
        // 4.插入新节点可能会破坏红黑树性质,这里修正一下
        fixAfterInsertion(e);
        size++;
        modCount++;
        return null;
    }
    

    put 方法代码如上,逻辑和二叉查找树插入节点逻辑一致。重要的步骤我已经写了注释,并不难理解。插入逻辑的复杂之处在于插入后的修复操作,对应的方法fixAfterInsertion,该方法的源码和说明如下:

    在这里插入图片描述

    到这里,插入操作就讲完了。接下来,来说说 TreeMap 中最复杂的部分,也就是删除操作了。

    删除

    删除操作是红黑树最复杂的部分,原因是该操作可能会破坏红黑树性质5(从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点),修复性质5要比修复其他性质(性质2和4需修复,性质1和3不用修复)复杂的多。当删除操作导致性质5被破坏时,会出现8种情况。为了方便表述,这里还是先做一些假设。我们把最终被删除的节点称为 X,X 的替换节点称为 N。N 的父节点为P,且 N 是 P 的左孩子。N 的兄弟节点为S,S 的左孩子为 SL,右孩子为 SR。这里特地强调 X 是 最终被删除 的节点,是原因二叉查找树会把要删除有两个孩子的节点的情况转化为删除只有一个孩子的节点的情况,该节点是欲被删除节点的前驱和后继。

    接下来,简单列举一下删除节点时可能会出现的情况,先列举较为简单的情况:

    1. 最终被删除的节点 X 是红色节点
    2. X 是黑色节点,但该节点的孩子节点是红色

    比较复杂的情况:

    1. 替换节点 N 是新的根
    2. N 为黑色,N 的兄弟节点 S 为红色,其他节点为黑色。
    3. N 为黑色,N 的父节点 P,兄弟节点 S 和 S 的孩子节点均为黑色。
    4. N 为黑色,P 是红色,S 和 S 孩子均为黑色。
    5. N 为黑色,P 可红可黑,S 为黑色,S 的左孩子 SL 为红色,右孩子 SR 为黑色
    6. N 为黑色,P 可红可黑,S 为黑色,SR 为红色,SL 可红可黑

    上面列举的8种情况中,前两种处理起来比较简单,后6种情况中情况26较为复杂。接下来我将会对情况26展开分析,删除相关的源码如下:

    public V remove(Object 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--;
    
        /* 
         * 1. 如果 p 有两个孩子节点,则找到后继节点,
         * 并把后继节点的值复制到节点 P 中,并让 p 指向其后继节点
         */
        if (p.left != null && p.right != null) {
            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.
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
        if (replacement != null) {
            /*
             * 2. 将 replacement parent 引用指向新的父节点,
             * 同时让新的父节点指向 replacement。
             */ 
            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;
    
            // 3. 如果删除的节点 p 是黑色节点,则需要进行调整
            if (p.color == BLACK)
                fixAfterDeletion(replacement);
        } else if (p.parent == null) { // 删除的是根节点,且树中当前只有一个节点
            root = null;
        } else { // 删除的节点没有孩子节点
            // p 是黑色,则需要进行调整
            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;
            }
        }
    }
    

    从源码中可以看出,remove方法只是一个简单的保证,核心实现在deleteEntry方法中。deleteEntry 主要做了这么几件事:

    1. 如果待删除节点 P 有两个孩子,则先找到 P 的后继 S,然后将 S 中的值拷贝到 P 中,并让 P 指向 S
    2. 如果最终被删除节点 P(P 现在指向最终被删除节点)的孩子不为空,则用其孩子节点替换掉
    3. 如果最终被删除的节点是黑色的话,调用 fixAfterDeletion 方法进行修复

    上面说了 replacement 不为空时,deleteEntry 的执行逻辑。上面说的略微啰嗦,如果简单说的话,7个字即可总结:找后继 -> 替换 -> 修复。这三步中,最复杂的是修复操作。修复操作要重新使红黑树恢复平衡,修复操作的源码分析如下:

    fixAfterDeletion 方法分析如下:
    在这里插入图片描述

    上面对 fixAfterDeletion 部分代码逻辑就行了分析,通过配图的形式解析了每段代码逻辑所处理的情况。通过图解,应该还是比较好理解的。好了,TreeMap 源码先分析到这里。

    总结

    红黑树详细分析从理论层面上详细分析了红黑树插入和删除操作可能会导致的问题,以及如何修复。本文则从实践层面是分析了插入和删除操作在具体的实现中时怎样做的。另外,本文选择了从集合框架常用方法这一角度进行分析,详细分析了查找、遍历、插入和删除等方法。总体来说,分析的还是比较详细的。当然限于本人的水平,文中可能会存在一些错误的论述。如果大家发现了,欢迎指出来。如果这些错误的论述对你造成了困扰,我这里先说声抱歉。如果你也在学习 TreeMap 源码,希望这篇文章能够帮到你。

    最后感谢大家花时间的阅读我的文章,顺祝大家写代码无BUG,下篇文章见。

    展开全文
  • TreeMap类源码解析

    2016-07-18 15:51:13
    2.插入、删除、查找时间复杂度都是O(logn) 3.没有实现同步方法线程不安全 ,效率较高 4.结点可以按照排序输出,默认排序是key值,可以自定义排序方法包package java.util;继承AbstractMap 实现NavigableMap、...

    TreeMap特点
    1.利用红黑树存储结点
    2.插入、删除、查找时间复杂度都是O(logn)
    3.没有实现同步方法线程不安全 ,效率较高
    4.结点可以按照排序输出,默认排序是key值,可以自定义排序方法

    package java.util;

    继承AbstractMap
    实现NavigableMap、Cloneable、 java.io.Serializable

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

    成员变量

     /**
         * 自定义比较器,默认null,表示用key自然排序
         * @serial
         */
        private final Comparator<? super K> comparator;
    
        /**
         * 根结点
         */
        private transient Entry<K,V> root = null;
    
        /**
         * 结点个数
         */
        private transient int size = 0;
    
        /**
         * 修改次数
         */
        private transient int modCount = 0;

    构造函数

    
        /**
         * 创建一个空的构造函数
         */
        public TreeMap() {
            comparator = null;
        }
    
        /**
         * 创建一个比较器是 Comparator的构造函数
         */
        public TreeMap(Comparator<? super K> comparator) {
            this.comparator = comparator;
        }
        /**
         * map m中元素加入到当前map中
         *  This method runs in n*log(n) time.
         *
         * @param  m the map whose mappings are to be placed in this map
         * @throws ClassCastException if the keys in m are not {@link Comparable},
         *         or are not mutually comparable
         * @throws NullPointerException if the specified map is null
         */
        public TreeMap(Map<? extends K, ? extends V> m) {
            comparator = null;
            putAll(m);
        }
    
        /**
         * SortedMap m中元素加入到当前map中
         *
         * @param  m the sorted map whose mappings are to be placed in this map,
         *         and whose comparator is to be used to sort this map
         * @throws NullPointerException if the specified map is null
         */
        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 int size() {
            return size;
        }
    
        /**
         * 判断是否包含 key 的结点
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        public boolean containsKey(Object key) {
            return getEntry(key) != null;
        }
    
        /**
         * 判断是否包含value的结点
         *
         * @param value value whose presence in this map is to be tested
         * @return {@code true} if a mapping to {@code value} exists;
         *         {@code false} otherwise
         * @since 1.2
         */
        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;
        }
    
        /**
         * 获取key对应的value
         *
         * @throws ClassCastException if the specified key cannot be compared
         *         with the keys currently in the map
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        public V get(Object key) {
            Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }
    
        public Comparator<? super K> comparator() {
            return comparator;
        }
    
        /**
         * 获取第一个结点的 key
         * @throws NoSuchElementException {@inheritDoc}
         */
        public K firstKey() {
            return key(getFirstEntry());
        }
    
        /**
         * 获取最后一个结点的key
         * @throws NoSuchElementException {@inheritDoc}
         */
        public K lastKey() {
            return key(getLastEntry());
        }
    
    
        /**
         * 获取key对应的结点 
         * 查找时间复杂度:O(log(n))
         * @return this map's entry for the given key, or {@code null} if the map
         *         does not contain an entry for the key
         * @throws ClassCastException if the specified key cannot be compared
         *         with the keys currently in the map
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        final 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();
            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;
            }
            return null;
        }
    
        /**
         * 根据比较器 获取key对应的结点
         */
        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;
        }
    
        /**
         * 寻找大于等于 key
         * 若都大于 key,返回最小的结点
         * 若都小于key, 返回最大的结点
         * Gets the entry corresponding to the specified key; if no such entry
         * exists, returns the entry for the least key greater than the specified
         * key; if no such entry exists (i.e., the greatest key in the Tree is less
         * than the specified key), returns {@code null}.
         */
        final Entry<K,V> getCeilingEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp < 0) {
                    if (p.left != null)
                        p = p.left;
                    else
                        return p;
                } else if (cmp > 0) {
                    if (p.right != null) {
                        p = p.right;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.right) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                } else
                    return p;
            }
            return null;
        }
    
        /**
         * 获取小于等于key的结点
         * 若都小于key,返回最大的结点
         * 若都大于key,返回最小的结点
         * Gets the entry corresponding to the specified key; if no such entry
         * exists, returns the entry for the greatest key less than the specified
         * key; if no such entry exists, returns {@code null}.
         */
        final Entry<K,V> getFloorEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp > 0) {
                    if (p.right != null)
                        p = p.right;
                    else
                        return p;
                } else if (cmp < 0) {
                    if (p.left != null) {
                        p = p.left;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.left) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                } else
                    return p;
    
            }
            return null;
        }
    
        /**
         * 获取大于key的结点
         * 若都大于key,返回最小值
         * 若都小于key,返回最大值
         * Gets the entry for the least key greater than the specified
         * key; if no such entry exists, returns the entry for the least
         * key greater than the specified key; if no such entry exists
         * returns {@code null}.
         */
        final Entry<K,V> getHigherEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp < 0) {
                    if (p.left != null)
                        p = p.left;
                    else
                        return p;
                } else {
                    if (p.right != null) {
                        p = p.right;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.right) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                }
            }
            return null;
        }
    
        /**
         * 获取小于key的结点
         * 若都小于key,返回最大结点
         * 若都大于key,返回最小结点
         */
        final Entry<K,V> getLowerEntry(K key) {
            Entry<K,V> p = root;
            while (p != null) {
                int cmp = compare(key, p.key);
                if (cmp > 0) {
                    if (p.right != null)
                        p = p.right;
                    else
                        return p;
                } else {
                    if (p.left != null) {
                        p = p.left;
                    } else {
                        Entry<K,V> parent = p.parent;
                        Entry<K,V> ch = p;
                        while (parent != null && ch == parent.left) {
                            ch = parent;
                            parent = parent.parent;
                        }
                        return parent;
                    }
                }
            }
            return null;
        }

    put方法

    
        /**
         * 加入结点
         *
         * @param key key with which the specified value is to be associated
         * @param value value to be associated with the specified key
         *
         * @return the previous value associated with {@code key}, or
         *         {@code null} if there was no mapping for {@code key}.
         *         (A {@code null} return can also indicate that the map
         *         previously associated {@code null} with {@code key}.)
         * @throws ClassCastException if the specified key cannot be compared
         *         with the keys currently in the map
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        public V put(K key, V value) {
            Entry<K,V> t = root;
            if (t == null) { // null的时候 
                compare(key, key); // 一个结点的时候,自己和自己比较
    
                root = new Entry<>(key, value, null); // 创建根结点
                size = 1;
                modCount++;
                return null;
            }
            int cmp;
            Entry<K,V> parent;
            // 下面的过程是找到插入结点的父结点 
            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); // key 已经存在,更新 value值 
                } while (t != null);
            }
            else {
                if (key == null)
                    throw new NullPointerException();
                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); // key 已经存在,更新 value值 
                } while (t != null);
            }
            Entry<K,V> e = new Entry<>(key, value, parent);
            if (cmp < 0)
                parent.left = e;
            else
                parent.right = e;
            fixAfterInsertion(e); // e 结点插入
            size++;
            modCount++;
            return null;
        }
    

    putAll

        /**
         * map中元素加入到当前map中
         *
         * @param  map mappings to be stored in this map
         * @throws ClassCastException if the class of a key or value in
         *         the specified map prevents it from being stored in this map
         * @throws NullPointerException if the specified map is null or
         *         the specified map contains a null key and this map does not
         *         permit null keys
         */
        public void putAll(Map<? extends K, ? extends V> map) {
            int mapSize = map.size();
            if (size==0 && mapSize!=0 && map instanceof SortedMap) {
                Comparator c = ((SortedMap)map).comparator();
                if (c == comparator || (c != null && c.equals(comparator))) {
                    ++modCount;
                    try {
                        buildFromSorted(mapSize, map.entrySet().iterator(),
                                        null, null);
                    } catch (java.io.IOException cannotHappen) {
                    } catch (ClassNotFoundException cannotHappen) {
                    }
                    return;
                }
            }
            super.putAll(map);
        }

    删除、clone

    
        /**
         * 删除key对应结点
         *
         * @param  key key for which mapping should be removed
         * @return the previous value associated with {@code key}, or
         *         {@code null} if there was no mapping for {@code key}.
         *         (A {@code null} return can also indicate that the map
         *         previously associated {@code null} with {@code key}.)
         * @throws ClassCastException if the specified key cannot be compared
         *         with the keys currently in the map
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         */
        public V remove(Object key) {
            Entry<K,V> p = getEntry(key); // 找到key所在结点 
            if (p == null)
                return null;
    
            V oldValue = p.value;
            deleteEntry(p); // 红黑树删除结点的操作
            return oldValue;
        }
    
        /**
         * 清空 
         */
        public void clear() {
            modCount++;
            size = 0;
            root = null;
        }
    
      /**
         * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
         * values themselves are not cloned.)
         *
         * @return a shallow copy of this map
         */
        public Object clone() {
            TreeMap<K,V> clone = null;
            try {
                clone = (TreeMap<K,V>) super.clone();
            } catch (CloneNotSupportedException e) {
                throw new InternalError();
            }
    
            // Put clone into "virgin" state (except for comparator)
            clone.root = null;
            clone.size = 0;
            clone.modCount = 0;
            clone.entrySet = null;
            clone.navigableKeySet = null;
            clone.descendingMap = null;
    
            // Initialize clone with our mappings
            try {
                clone.buildFromSorted(size, entrySet().iterator(), null, null);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
    
            return clone;
        }
    

    NavigableMap API methods

    
        /**
         * @since 1.6
         */
        public Map.Entry<K,V> firstEntry() {
            return exportEntry(getFirstEntry());
        }
    
        /**
         * @since 1.6
         */
        public Map.Entry<K,V> lastEntry() {
            return exportEntry(getLastEntry());
        }
    
        /**
         * @since 1.6
         */
        public Map.Entry<K,V> pollFirstEntry() {
            Entry<K,V> p = getFirstEntry();
            Map.Entry<K,V> result = exportEntry(p);
            if (p != null)
                deleteEntry(p);
            return result;
        }
    
        /**
         * @since 1.6
         */
        public Map.Entry<K,V> pollLastEntry() {
            Entry<K,V> p = getLastEntry();
            Map.Entry<K,V> result = exportEntry(p);
            if (p != null)
                deleteEntry(p);
            return result;
        }
        /**
         * 获取小于key的结点 若都小于key,返回最大结点 若都大于key,返回最小结点
         * @throws ClassCastException {@inheritDoc}
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @since 1.6
         */
        public K lowerKey(K key) {
            return keyOrNull(getLowerEntry(key));
        }
    
    
        /**
         * 获取小于等于key的结点 若都小于key,返回最大的结点 若都大于key,返回最小的结点 
         * @throws ClassCastException {@inheritDoc}
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @since 1.6
         */
        public K floorKey(K key) {
            return keyOrNull(getFloorEntry(key));
        }
    
        /**
         * 获取大于key的结点 若都大于key,返回最小值 若都小于key,返回最大值 
         * @throws ClassCastException {@inheritDoc}
         * @throws NullPointerException if the specified key is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @since 1.6
         */
        public K higherKey(K key) {
            return keyOrNull(getHigherEntry(key));
        }

    迭代器相关

        private transient EntrySet entrySet = null;
        private transient KeySet<K> navigableKeySet = null;
        private transient NavigableMap<K,V> descendingMap = null;
    
        /**
         * keySet
         */
        public Set<K> keySet() {
            return navigableKeySet();
        }
    
        /**
         * navigableKeySet
         * @since 1.6
         */
        public NavigableSet<K> navigableKeySet() {
            KeySet<K> nks = navigableKeySet;
            return (nks != null) ? nks : (navigableKeySet = new KeySet(this));
        }
    
        /**
         * @since 1.6
         */
        public NavigableSet<K> descendingKeySet() {
            return descendingMap().navigableKeySet();
        }
    
        /**
         * values
         */
        public Collection<V> values() {
            Collection<V> vs = values;
            return (vs != null) ? vs : (values = new Values());
        }
    
        /**
         * entrySet
         */
        public Set<Map.Entry<K,V>> entrySet() {
            EntrySet es = entrySet;
            return (es != null) ? es : (entrySet = new EntrySet());
        }
    
        /**
         * @since 1.6
         */
        public NavigableMap<K, V> descendingMap() {
            NavigableMap<K, V> km = descendingMap;
            return (km != null) ? km :
                (descendingMap = new DescendingSubMap(this,
                                                      true, null, true,
                                                      true, null, true));
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code fromKey} or {@code toKey} is
         *         null and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         * @since 1.6
         */
        public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                        K toKey,   boolean toInclusive) {
            return new AscendingSubMap(this,
                                       false, fromKey, fromInclusive,
                                       false, toKey,   toInclusive);
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code toKey} is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         * @since 1.6
         */
        public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
            return new AscendingSubMap(this,
                                       true,  null,  true,
                                       false, toKey, inclusive);
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code fromKey} is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         * @since 1.6
         */
        public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
            return new AscendingSubMap(this,
                                       false, fromKey, inclusive,
                                       true,  null,    true);
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code fromKey} or {@code toKey} is
         *         null and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         */
        public SortedMap<K,V> subMap(K fromKey, K toKey) {
            return subMap(fromKey, true, toKey, false);
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code toKey} is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         */
        public SortedMap<K,V> headMap(K toKey) {
            return headMap(toKey, false);
        }
    
        /**
         * @throws ClassCastException       {@inheritDoc}
         * @throws NullPointerException if {@code fromKey} is null
         *         and this map uses natural ordering, or its comparator
         *         does not permit null keys
         * @throws IllegalArgumentException {@inheritDoc}
         */
        public SortedMap<K,V> tailMap(K fromKey) {
            return tailMap(fromKey, true);
        }
    
        // View class support
    
        class Values extends AbstractCollection<V> {
            public Iterator<V> iterator() {
                return new ValueIterator(getFirstEntry());
            }
    
            public int size() {
                return TreeMap.this.size();
            }
    
            public boolean contains(Object o) {
                return TreeMap.this.containsValue(o);
            }
    
            public boolean remove(Object o) {
                for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
                    if (valEquals(e.getValue(), o)) {
                        deleteEntry(e);
                        return true;
                    }
                }
                return false;
            }
    
            public void clear() {
                TreeMap.this.clear();
            }
        }
    
        class EntrySet extends AbstractSet<Map.Entry<K,V>> {
            public Iterator<Map.Entry<K,V>> iterator() {
                return new EntryIterator(getFirstEntry());
            }
    
            public boolean contains(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                V value = entry.getValue();
                Entry<K,V> p = getEntry(entry.getKey());
                return p != null && valEquals(p.getValue(), value);
            }
    
            public boolean remove(Object o) {
                if (!(o instanceof Map.Entry))
                    return false;
                Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
                V value = entry.getValue();
                Entry<K,V> p = getEntry(entry.getKey());
                if (p != null && valEquals(p.getValue(), value)) {
                    deleteEntry(p);
                    return true;
                }
                return false;
            }
    
            public int size() {
                return TreeMap.this.size();
            }
    
            public void clear() {
                TreeMap.this.clear();
            }
        }
    
        /*
         * keyIterator
         */
    
        Iterator<K> keyIterator() {
            return new KeyIterator(getFirstEntry());
        }
    
        Iterator<K> descendingKeyIterator() {
            return new DescendingKeyIterator(getLastEntry());
        }
    
        static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
            private final NavigableMap<E, Object> m;
            KeySet(NavigableMap<E,Object> map) { m = map; }
    
            public Iterator<E> iterator() {
                if (m instanceof TreeMap)
                    return ((TreeMap<E,Object>)m).keyIterator();
                else
                    return (Iterator<E>)(((TreeMap.NavigableSubMap)m).keyIterator());
            }
    
            public Iterator<E> descendingIterator() {
                if (m instanceof TreeMap)
                    return ((TreeMap<E,Object>)m).descendingKeyIterator();
                else
                    return (Iterator<E>)(((TreeMap.NavigableSubMap)m).descendingKeyIterator());
            }
    
            public int size() { return m.size(); }
            public boolean isEmpty() { return m.isEmpty(); }
            public boolean contains(Object o) { return m.containsKey(o); }
            public void clear() { m.clear(); }
            public E lower(E e) { return m.lowerKey(e); }
            public E floor(E e) { return m.floorKey(e); }
            public E ceiling(E e) { return m.ceilingKey(e); }
            public E higher(E e) { return m.higherKey(e); }
            public E first() { return m.firstKey(); }
            public E last() { return m.lastKey(); }
            public Comparator<? super E> comparator() { return m.comparator(); }
            public E pollFirst() {
                Map.Entry<E,Object> e = m.pollFirstEntry();
                return (e == null) ? null : e.getKey();
            }
            public E pollLast() {
                Map.Entry<E,Object> e = m.pollLastEntry();
                return (e == null) ? null : e.getKey();
            }
            public boolean remove(Object o) {
                int oldSize = size();
                m.remove(o);
                return size() != oldSize;
            }
            public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                          E toElement,   boolean toInclusive) {
                return new KeySet<>(m.subMap(fromElement, fromInclusive,
                                              toElement,   toInclusive));
            }
            public NavigableSet<E> headSet(E toElement, boolean inclusive) {
                return new KeySet<>(m.headMap(toElement, inclusive));
            }
            public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
                return new KeySet<>(m.tailMap(fromElement, inclusive));
            }
            public SortedSet<E> subSet(E fromElement, E toElement) {
                return subSet(fromElement, true, toElement, false);
            }
            public SortedSet<E> headSet(E toElement) {
                return headSet(toElement, false);
            }
            public SortedSet<E> tailSet(E fromElement) {
                return tailSet(fromElement, true);
            }
            public NavigableSet<E> descendingSet() {
                return new KeySet(m.descendingMap());
            }
        }
    
        /**
         * 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;
            }
    
            public final boolean hasNext() {
                return next != null;
            }
    
            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;
            }
    
            public void remove() {
                if (lastReturned == null)
                    throw new IllegalStateException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                // deleted entries are replaced by their successors
                if (lastReturned.left != null && lastReturned.right != null)
                    next = lastReturned;
                deleteEntry(lastReturned);
                expectedModCount = modCount;
                lastReturned = null;
            }
        }
    
        final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
            EntryIterator(Entry<K,V> first) {
                super(first);
            }
            public Map.Entry<K,V> next() {
                return nextEntry();
            }
        }
    
        final class ValueIterator extends PrivateEntryIterator<V> {
            ValueIterator(Entry<K,V> first) {
                super(first);
            }
            public V next() {
                return nextEntry().value;
            }
        }
    
        final class KeyIterator extends PrivateEntryIterator<K> {
            KeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return nextEntry().key;
            }
        }
    
        final class DescendingKeyIterator extends PrivateEntryIterator<K> {
            DescendingKeyIterator(Entry<K,V> first) {
                super(first);
            }
            public K next() {
                return prevEntry().key;
            }
        }
    

    比较方法

       /**
         * Compares two keys using the correct comparison method for this TreeMap.
         */
        final int compare(Object k1, Object k2) {
            return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
                : comparator.compare((K)k1, (K)k2);
        }
    
        /**
         * Test two values for equality.  Differs from o1.equals(o2) only in
         * that it copes with {@code null} o1 properly.
         */
        static final boolean valEquals(Object o1, Object o2) {
            return (o1==null ? o2==null : o1.equals(o2));
        }
    
        /**
         * Return SimpleImmutableEntry for entry, or null if null
         */
        static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
            return (e == null) ? null :
                new AbstractMap.SimpleImmutableEntry<>(e);
        }
    
        /**
         * Return key for entry, or null if null
         */
        static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
            return (e == null) ? null : e.key;
        }
    
        /**
         * Returns the key corresponding to the specified Entry.
         * @throws NoSuchElementException if the Entry is null
         */
        static <K> K key(Entry<K,?> e) {
            if (e==null)
                throw new NoSuchElementException();
            return e.key;
        }
    

    SubMaps相关类、相关方法

    --和上面很类似

    其实上面说的写的很没意思,都是复制的代码,自己也懒得很详细的写了

    红黑树相关操作才是重点
    红黑结点

        private static final boolean RED   = false;
        private static final boolean BLACK = true;

    结点定义
    默认是黑结点

       static final class Entry<K,V>  {
            K key;
            V value;
            Entry<K,V> left = null;
            Entry<K,V> right = null;
            Entry<K,V> parent;
            boolean color = BLACK; // 默认是黑色  BLACK = true 
    
            /**
             * Make a new cell with given key, value, and parent, and with
             * {@code null} child links, and BLACK color.
             */
            Entry(K key, V value, Entry<K,V> parent) {
                this.key = key;
                this.value = value;
                this.parent = parent;
            }
    
            /**
             * Returns the key.
             *
             * @return the key
             */
            public K getKey() {
                return key;
            }
    
            /**
             * Returns the value associated with the key.
             *
             * @return the value associated with the key
             */
            public V getValue() {
                return value;
            }
    
            /**
             * Replaces the value currently associated with the key with the given
             * value.
             *
             * @return the value associated with the key before this method was
             *         called
             */
            public V setValue(V value) {
                V oldValue = this.value;
                this.value = value;
                return oldValue;
            }
    
            public boolean equals(Object o) {
                if (!(o instanceof Entry))
                    return false;
                Entry<?,?> e = (Entry<?,?>)o;
    
                return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
            }
    
            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;
            }
        }
    

    找最小key结点,找最大key结点

        /**
         *排序的第一个结点
         */
        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;
        }

    左右结点,父结点,设置颜色操作

       /**
         * 查看p结点的颜色,null 是BLACk
         * @param p
         * @return
         */
        private static <K,V> boolean colorOf(Entry<K,V> p) {
            return (p == null ? BLACK : p.color);
        }
        /**
         * 查看p结点的父结点
         * @param p
         * @return
         */
        private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
            return (p == null ? null: p.parent);
        }
        /**
         * 设置p结点的颜色为 c 
         * @param p
         * @param c
         */
        private static <K,V> void setColor(Entry<K,V> p, boolean c) {
            if (p != null)
                p.color = c;
        }
        /**
         * 查看p结点的left结点
         * @param p
         * @return
         */
        private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
            return (p == null) ? null: p.left;
        }
        /**
         * 查看p结点的right结点
         * @param p
         * @return
         */
        private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
            return (p == null) ? null: p.right;
        }
    

    前驱和后继结点

    
        /**
         * t 结点的继承者 
         */
        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;
            }
        }
    
        /**
         * t 结点的前驱
         */
        static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
            if (t == null)
                return null;
            else if (t.left != null) {
                Entry<K,V> p = t.left;
                while (p.right != null)
                    p = p.right;
                return p;
            } else {
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.left) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

    左旋和右旋
    详细讲解参考《算法导论》

    
        /** From CLR 
         * 左旋转
         * */
        private void rotateLeft(Entry<K,V> p) {
            if (p != null) {
                Entry<K,V> r = p.right;
                p.right = r.left;
                if (r.left != null)
                    r.left.parent = p;
                r.parent = p.parent;
                if (p.parent == null)
                    root = r;
                else if (p.parent.left == p)
                    p.parent.left = r;
                else
                    p.parent.right = r;
                r.left = p;
                p.parent = r;
            }
        }
    
        /** From CLR 
         * 右旋转
         * */
        private void rotateRight(Entry<K,V> p) {
            if (p != null) {
                Entry<K,V> l = p.left;
                p.left = l.right;
                if (l.right != null) l.right.parent = p;
                l.parent = p.parent;
                if (p.parent == null)
                    root = l;
                else if (p.parent.right == p)
                    p.parent.right = l;
                else p.parent.left = l;
                l.right = p;
                p.parent = l;
            }
        }

    找到插入位置后,插入结点x,并调整为红黑树
    详细讲解参考《算法导论》

    
        /** From CLR 
         * 插入结点 x 
         * */
        private void fixAfterInsertion(Entry<K,V> x) {
            x.color = RED; // 默认插入的结点是红结点 
    
            while (x != null && x != root && x.parent.color == RED) {
                if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                    Entry<K,V> 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<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; // 更新为黑结点
        }

    删除结点操作
    详细讲解参考《算法导论》

      /**
         * 删除结点 p ,删除结点p的原理:将p所在子树的叶子结点替代该结点值,删除 该叶子结点,
         */
        private void deleteEntry(Entry<K,V> p) {
            modCount++;
            size--;
    
            // If strictly internal, copy successor's element to p and then make p
            // point to successor.
            if (p.left != null && p.right != null) {
                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.
            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 { //  No children. Use self as phantom replacement and unlink.
                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;
                }
            }
        }
    
        /** From CLR 
         * 删除结点后,调整为红黑树
         * */
        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的key树 
         * @param level
         */
        public void outputTreeKey(int level){
            outputTreeKey(root,level,"root");
        }
        public void outputTreeKey(Entry<K,V> node,int level,String target) {
            if(node.left!=null || node.right!=null){
                for(int i=0;i<level;i++)
                    System.out.print("\t");
                System.out.println(target+" ["+node.key+" : "+node.color+"]");
    
                Entry<K,V> left = node.left;
                Entry<K,V> right = node.right;
                if(node.left!=null)
                    outputTreeKey(left,level+1,"left");
                if(node.right!=null)
                    outputTreeKey(right,level+1,"right");
            }else{
                for(int i=0;i<level;i++){
                    System.out.print("\t");
                }
                System.out.println(target+" ["+node.key+" : "+node.color+"]");
            }
    
        }
        public void outputTree(int level){
            outputTree(root,level,"root");
        }
        /**
         * 输出map
         */
        public void outputTree(Entry<K,V> node,int level,String target) {
            if(node.left!=null || node.right!=null){
                for(int i=0;i<level;i++)
                    System.out.print("\t");
                System.out.println(target+" [ "+node.key+" : "+node.value+" , "+node.color+" ]");
    
                Entry<K,V> left = node.left;
                Entry<K,V> right = node.right;
                if(node.left!=null)
                    outputTree(left,level+1,"left");
                if(node.right!=null)
                    outputTree(right,level+1,"right");
            }else{
                for(int i=0;i<level;i++){
                    System.out.print("\t");
                }
                System.out.println(target+" [ "+node.key+" : "+node.value+" , "+node.color+" ]");
            }
    
        }

    测试输出

    public class TreeMapTest {
    
        /**
         * @param args
         */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            TreeMap<Integer,Integer> treeMap = new TreeMap<Integer,Integer>();
            treeMap.put(1, 1);
            treeMap.put(2, 2);
            treeMap.put(3, 3);
            treeMap.put(4, 4);
            treeMap.put(5, 4);
            treeMap.put(14, 4);
            treeMap.put(43, 4);
            treeMap.outputTreeKey(0);
        }
    
    }

    默认的是按照key进行自然排序
    我只输出其中的key值

    root [2 : true]
        left [1 : true]
        right [4 : false]
            left [3 : true]
            right [14 : true]
                left [5 : false]
                right [43 : false]

    画出二叉树形式的图
    这里写图片描述
    完全满足红黑树的特点
    关于红黑树,我也没有过多的研究,有时间《算法导论》上面的讲解要自己研究下
    其他方法

    
        private static final long serialVersionUID = 919286545866124006L;
    
        /**
         * Save the state of the {@code TreeMap} instance to a stream (i.e.,
         * serialize it).
         *
         * @serialData The <em>size</em> of the TreeMap (the number of key-value
         *             mappings) is emitted (int), followed by the key (Object)
         *             and value (Object) for each key-value mapping represented
         *             by the TreeMap. The key-value mappings are emitted in
         *             key-order (as determined by the TreeMap's Comparator,
         *             or by the keys' natural ordering if the TreeMap has no
         *             Comparator).
         */
        private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
            // Write out the Comparator and any hidden stuff
            s.defaultWriteObject();
    
            // Write out size (number of Mappings)
            s.writeInt(size);
    
            // Write out keys and values (alternating)
            for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
                Map.Entry<K,V> e = i.next();
                s.writeObject(e.getKey());
                s.writeObject(e.getValue());
            }
        }
    
        /**
         * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
         * deserialize it).
         */
        private void readObject(final java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
            // Read in the Comparator and any hidden stuff
            s.defaultReadObject();
    
            // Read in size
            int size = s.readInt();
    
            buildFromSorted(size, null, s, null);
        }
    
        /** Intended to be called only from TreeSet.readObject */
        void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
            throws java.io.IOException, ClassNotFoundException {
            buildFromSorted(size, null, s, defaultVal);
        }
    
        /** Intended to be called only from TreeSet.addAll */
        void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
            try {
                buildFromSorted(set.size(), set.iterator(), null, defaultVal);
            } catch (java.io.IOException cannotHappen) {
            } catch (ClassNotFoundException cannotHappen) {
            }
        }
    
    
        /**
         * Linear time tree building algorithm from sorted data.  Can accept keys
         * and/or values from iterator or stream. This leads to too many
         * parameters, but seems better than alternatives.  The four formats
         * that this method accepts are:
         *
         *    1) An iterator of Map.Entries.  (it != null, defaultVal == null).
         *    2) An iterator of keys.         (it != null, defaultVal != null).
         *    3) A stream of alternating serialized keys and values.
         *                                   (it == null, defaultVal == null).
         *    4) A stream of serialized keys. (it == null, defaultVal != null).
         *
         * It is assumed that the comparator of the TreeMap is already set prior
         * to calling this method.
         *
         * @param size the number of keys (or key-value pairs) to be read from
         *        the iterator or stream
         * @param it If non-null, new entries are created from entries
         *        or keys read from this iterator.
         * @param str If non-null, new entries are created from keys and
         *        possibly values read from this stream in serialized form.
         *        Exactly one of it and str should be non-null.
         * @param defaultVal if non-null, this default value is used for
         *        each value in the map.  If null, each value is read from
         *        iterator or stream, as described above.
         * @throws IOException propagated from stream reads. This cannot
         *         occur if str is null.
         * @throws ClassNotFoundException propagated from readObject.
         *         This cannot occur if str is null.
         */
        private void buildFromSorted(int size, Iterator it,
                                     java.io.ObjectInputStream str,
                                     V defaultVal)
            throws  java.io.IOException, ClassNotFoundException {
            this.size = size;
            root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
                                   it, str, defaultVal);
        }
    
        /**
         * Recursive "helper method" that does the real work of the
         * previous method.  Identically named parameters have
         * identical definitions.  Additional parameters are documented below.
         * It is assumed that the comparator and size fields of the TreeMap are
         * already set prior to calling this method.  (It ignores both fields.)
         *
         * @param level the current level of tree. Initial call should be 0.
         * @param lo the first element index of this subtree. Initial should be 0.
         * @param hi the last element index of this subtree.  Initial should be
         *        size-1.
         * @param redLevel the level at which nodes should be red.
         *        Must be equal to computeRedLevel for tree of this size.
         */
        private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
                                                 int redLevel,
                                                 Iterator it,
                                                 java.io.ObjectInputStream str,
                                                 V defaultVal)
            throws  java.io.IOException, ClassNotFoundException {
            /*
             * Strategy: The root is the middlemost element. To get to it, we
             * have to first recursively construct the entire left subtree,
             * so as to grab all of its elements. We can then proceed with right
             * subtree.
             *
             * The lo and hi arguments are the minimum and maximum
             * indices to pull out of the iterator or stream for current subtree.
             * They are not actually indexed, we just proceed sequentially,
             * ensuring that items are extracted in corresponding order.
             */
    
            if (hi < lo) return null;
    
            int mid = (lo + hi) >>> 1;
    
            Entry<K,V> left  = null;
            if (lo < mid)
                left = buildFromSorted(level+1, lo, mid - 1, redLevel,
                                       it, str, defaultVal);
    
            // extract key and/or value from iterator or stream
            K key;
            V value;
            if (it != null) {
                if (defaultVal==null) {
                    Map.Entry<K,V> entry = (Map.Entry<K,V>)it.next();
                    key = entry.getKey();
                    value = entry.getValue();
                } else {
                    key = (K)it.next();
                    value = defaultVal;
                }
            } else { // use stream
                key = (K) str.readObject();
                value = (defaultVal != null ? defaultVal : (V) str.readObject());
            }
    
            Entry<K,V> middle =  new Entry<>(key, value, null);
    
            // color nodes in non-full bottommost level red
            if (level == redLevel)
                middle.color = RED;
    
            if (left != null) {
                middle.left = left;
                left.parent = middle;
            }
    
            if (mid < hi) {
                Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
                                                   it, str, defaultVal);
                middle.right = right;
                right.parent = middle;
            }
    
            return middle;
        }
    
        /**
         * Find the level down to which to assign all nodes BLACK.  This is the
         * last `full' level of the complete binary tree produced by
         * buildTree. The remaining nodes are colored RED. (This makes a `nice'
         * set of color assignments wrt future insertions.) This level number is
         * computed by finding the number of splits needed to reach the zeroeth
         * nod e.  (The answer is ~lg(N), but in any case must be computed by same
         * quick O(lg(N)) loop.)
         */
        private static int computeRedLevel(int sz) {
            int level = 0;
            for (int m = sz - 1; m >= 0; m = m / 2 - 1)
                level++;
            return level;
        }
    展开全文
  • Java HashMap与TreeMap

    2020-12-15 23:37:57
    HashMap和TreeMap有何区别?如何正确使用他们? 1. HashMap 1.1 数据结构 ...哈希查找时间复杂度为 O(1) 如果哈希冲突较多,链表的时间复杂度为O(n) 当链表长度大于阈值(默认为 8)时,将链表转化为红黑树

    HashMap和TreeMap有何区别?如何正确使用他们?

    1. HashMap

    1.1 数据结构

    1. HashMap 主要用来存放键值对( K - V ),数据是无序的
    2. JDK8 开始,底层由 数组+链表+红黑树 的数据结构来实现
    3. 当发生哈希冲突的时候,通过拉链法进行处理,当链表长度大于阈值(默认为 8 )的时候,将链表转化为红黑树,以减少搜索时间。

    1.2 时间复杂度

    1. 哈希查找的时间复杂度为 O(1)
    2. 如果哈希冲突较多,链表的时间复杂度为O(n)
    3. 当链表长度大于阈值(默认为 8)时,将链表转化为红黑树,以减少搜索时间,红黑树查找的时间复杂度是 O(log n)
    4. 所以查询一个HashMap数据的时间复杂度为 O(1) + O(n) 或者 O(1) + O(log n) ,平均时间复杂度为 O(1) 因为哈希冲突还是少部分情况的。

    1.3 其他:HashMap的初始容量为什么要是 2 的整数幂

    看到寻址算法: https://blog.csdn.net/weixin_43093006/article/details/111243211

    1. 公式:( n - 1 ) & hash
    2. 当 n 为 2 的指数次幂时,减 1 后换算成 2 进制,则每一位都为 1 , 与 hash 进行与运算, 就可以得到 ( 0 ~ n-1 )范围内的每一个 index
    3. 当 n 不为 2 的指数次幂时,减 1 后换算成 2 进制,会出现 0,与 hash 进行与运算,会导致 ( 0 ~ n-1 ) 范围内的某些 index 永远得不到

    1.4 其他:HashMap默认的加载因子为什么是 0.75 ?转化阈值为什么是 8 ?

    加载因子/负载因子:

    1. 加载因子代表哈希表在其容量到达一定程度后,需要进行扩容,衡量的是一个散列表的空间的使用程度。
    2. 负载因子越大表示散列表的装填程度越高,反之越小。

    如果负载因子越大,对空间的利用更充分,但是哈希碰撞的机会也变大了,红果是查找效率的降低

    如果负载因子太小,对空间造成严重浪费,但数据稀疏也使得碰撞机会变小,查询效率提高

    为什么折中的选择加载因子为 0.75 ,而不是 0.8 或者 0.6 ?为什么转化阈值为 8 ?

    在源码中有一段分析:在理想情况下,使用随机哈希码,节点出现的频率在 hash 桶中遵循泊松分布,从表中(jdk源码中有给出)可以发现,当用 0.75 作为加载因子的时候,桶中元素到达 8 个的时候,概率已经变得非常小了。 所以每个碰撞位置的链表长度超过 8 个是几乎不可能的,因此在链表节点到达 8 时(发生的概率大概为千万分之一)才开始转化为红黑树。

    2. TreeMap

    2.1 数据结构

    1. TreeMap 是基于红黑树实现的一个保证有序性的 Map
    2. TreeMap 中的元素默认按照 key 的自然顺序( alpha-beta )排列。也可以指定传入的 comparator 自定义排序规则

    2.2 时间复杂度

    1. 由于基于红黑树,所以TreeMap的时间复杂度是 O(log n) (二分查找),如果需要有排序的数据,直接存放进TreeMap中就行,TreeMap自己会给排序,不需要再写排序代码。

    3. HashMap VS TreeMap

    1. HashMap 通过 hashcode 对其内容进行快速查找,而 TreeMap 中所有的元素都保持着某种固定的顺序,如果你需要得到一个有序的结果就应该使用 TreeMap
    2. HashMap 比 TreeMap 效率要高一些,查询速度比 TreeMap 要快
    展开全文
  • java TreeMap和TreeSet

    2016-11-30 16:43:15
    和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优,但是它内部的元素都是排序的,当需要查找某些元素...
  • HashMap、HashSet查找元素是 O(1)的时间复杂度(乱序),TreeMap、TreeSet是log2 N的时间复杂度(顺序)
  • TreeMap内部实现简介

    千次阅读 2014-04-26 17:06:57
    另外,HashMap存取元素的时间复杂度是O(1)的常量级,而TreeMap对元素的操作复杂度为O(log n)。虽然在操作性能方面,TreeMap不占优势,但是因为它使用红黑树(平衡二叉查找树)实现,所以它内部的元素都是排好序的。...
  • 二叉搜索树的弊端二叉搜索树的查找,插入,删除的复杂度等于树的高度,时间复杂度是O(log(n)).但是,对于同一组数据,插入顺序的不同,可能会导致二叉搜索树的高度不同。如果是有序插入,二叉搜索树退化成链表,其查找...
  • TreeMap的深入剖析

    2018-06-26 21:06:56
    TreeMap的深入剖析 TreeMap的深入剖析 一、简介 二、概览 2.1、属性 三、源码分析 ...3.2 查找 ...TreeMap最早出现在JDK 1.2中,是 Java 集合...TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 conta...
  • HashMap 概述 HashMap是基于哈希表(散列表),实现Map接口的双列...数组:通过索引,时间复杂度O(1),通过给定值查找,需要遍历数组,自已对比复杂度为O(1) 二分查找插值查找,复杂度为O(logn) 线性链表:增 删除仅处...
  • TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 2、HashMap、TreeMap都继承AbstractMap抽象类;TreeMap实现SortedMap接口,所以TreeMap是有序的!HashMap是无序的 3、...
  • 本文概要 二叉查找树的用处 二叉查找树,以及二叉树带来的问题 平衡二叉树的好处 红黑树的定义以及构造 ...时间复杂度O(1) 劣势:删除和插入元素比较麻烦,需要移动的元素比较多。时间复杂度O(n) 链表 ...
  • java TreeMap TreeSet 用法 原理 详解

    千次阅读 2014-12-21 00:10:16
    和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优,但是它内部的元素都是排序的,当需要查找某些元素...
  • 一、HashMap和TreeMap区别 ...TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 2、HashMap、TreeMap都继承AbstractMap抽象类;TreeMap实现SortedMap接口,所以TreeMap是有序的...
  • 和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优,但是它内部的元素都是排序的,当需要查找某些元素...
  • TreeMap和TreeSetTreeMap概念特点构造方法内部组成方法执行保存键值对 put根据键获取值查看是否...查找、插入、删除时间复杂度O(logn) 线程不安全(线程安全问题使用ConcurrentSkipListMap) 构造方法 四个构造方法:
  • 目录 一 简介 二 概览 三 源码分析  3.1 查找  3.2 遍历 ...TreeMap 底层基于红黑树实现,可保证在log(n)时间复杂度内完成 containsKey、get、put 和 remove 操作,效率很高。另一方面,由于 Tr...
  • 转自:http://blog.csdn.net/paincupid/article/details/47746341 一、HashMap和... TreeMap基于红黑树(一种自平衡二叉查找树)实现的,时间复杂度平均能达到O(log n)。 2、HashMap、TreeMap都继承AbstractM...
  • JDK源码分析-TreeMap(1)

    2019-04-08 08:00:00
    概述前面数据结构与算法笔记对红黑树进行了分析,而TreeMap 内部就是基于红黑树实现的。示意图:它的查找、插入、删除操作的时间复杂度均为O(logn)。TreeMa...
  • TreeMap有序性和唯一性

    2021-01-20 10:54:18
    但是查找效率不如 HashSet,HashSet 查找时间复杂度为 O(1),TreeSet 则为 O(logN)。 public static void main(String[] args) { TreeSet<Integer> set = new TreeSet<>(); set.add(15); set.add...
  • 和普通的HashMap不一样,普通的HashMap元素存取的时间复杂度一般是O(1)的范围。而TreeMap内部对元素的操作复杂度为O(logn)。虽然在元素的存取方面TreeMap并不占优,但是它内部的元素都是排序的,当需要查找某些元素...
  • 红黑树TreeMap总结

    2018-12-30 16:07:16
    它可以在O(logN)时间复杂度内完成查找、增加、删除操作。红黑树是在二叉查找树基础上增加了着色和左右旋转使得红黑树相对平衡, 与AVL树相比,红黑树并不追求所有子树的高度差不超过1,而是保证从根节点到叶子节点...
  • 1.简介 JDK1.8中TreeMap底层实现采用了红黑树,具有比较好的查询、添加、删除效率,TreeSet底层实现其实也是TreeMap。...红黑树的查找、添加、删除操作的时间复杂度都是O(lgn),能很大程度解决一般二
  • 概述 前面数据结构与算法笔记...它的查找、插入、删除操作的时间复杂度均为O(logn)。 TreeMap 类的继承结构如下: 类签名: public class TreeMap<K,V> extends AbstractMap<K,V> im...
  • TreeMap使用红黑树来存储数据,红黑树是一种平衡二叉查找树,它是一种高效的搜索算法,它的算法时间复杂度是O(lgn),本文不涉及红黑树的定义及操作细节,只涉及部分有助于理解TreeMap的内容。本文旨在从整体上理解...

空空如也

空空如也

1 2 3 4 5
收藏数 94
精华内容 37
关键字:

treemap查找时间复杂度