精华内容
下载资源
问答
  • TreeMap实现有序原理

    万次阅读 2019-02-13 14:07:52
    上一篇讲了LinkedHashMap实现有序原理,这票介绍一个另一种有序的Map,TreeMap。 同样是有序,两者大不一样,LinkedHashMap是按照插入顺序排序,而TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序。在...

    上一篇讲了LinkedHashMap实现有序的原理,这票介绍一个另一种有序的Map,TreeMap。

    同样是有序,两者大不一样,LinkedHashMap是按照插入顺序排序,而TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序。在实现原理上LinkedHashMap是双向链表,TreeMap是红黑树。TreeMap还有个好兄弟叫TreeSet,实现原理是一样的。

    这是TreeMap的家谱,特别的一点是TreeMap 实现了NavigableMap接口,意味着它支持一系列的导航方法。比如返回有序的key集合。另外,它的Entry中包含了很多红黑树的概念,红黑树原理就不在这里介绍了,以后会详细讲讲。

    TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 O(log n),HashMap的时间复杂度是O(1),可见没有排序需求的情况下HashMap的性能更好。

    附一张常用数据结构的时间复杂度,为什么HashMap的时间复杂度是O(1)这么优秀,是一个可以深思的问题。

    Data Structure Add Find Delete GetByIndex
    Array (T[]) O(n) O(n) O(n) O(1)
    Linked list (LinkedList<T>) O(1) O(n) O(n) O(n)
    Resizable array list (List<T>) O(1) O(n) O(n) O(1)
    Stack (Stack<T>) O(1) - O(1) -
    Queue (Queue<T>) O(1) - O(1) -
    Hash table (Dictionary<K,T>) O(1) O(1) O(1) -
    Tree-based dictionary(SortedDictionary<K,T>) O(log n) O(log n) O(log n) -
    Hash table based set (HashSet<T>) O(1) O(1) O(1) -
    Tree based set (SortedSet<T>) O(log n) O(log n) O(log n) -

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • TreeMap底层原理

    2020-08-05 10:25:33
    1.TreeMap实现了SortedMap接口,保证了有序性。默认的排序是根据key值进行升序排序,也可以重写comparator方法来根据value进行排序具体取决于使用的构造方法。不允许有null值null键。TreeMap是线程不安全的。 2. ...

    1.TreeMap实现了SortedMap接口,保证了有序性。默认的排序是根据key值进行升序排序,也可以重写comparator方法来根据value进行排序具体取决于使用的构造方法。不允许有null值null键。TreeMap是线程不安全的。

    2. TreeMap基于红黑树(Red-Black tree)实现。TreeMap的基本操作 containsKey、get、put 和 remove 的时间复杂度是 log(n) 。

        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);
        }
    

    展开全文
  • TreeMap实现原理

    2018-09-30 11:34:03
    TreeMap实现了SotredMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。这点会在接下来的代码中做说明...

    基于JDK1.7进行分析

    TreeMap实现了SotredMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。这点会在接下来的代码中做说明,如果指定了比较器则按照比较器来进行排序。

    数据结构

    继承关系

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

    实现接口

    Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V> 

    基本属性

    private final Comparator<? super K> comparator;  //比较器,是自然排序,还是定制排序 ,使用final修饰,表明一旦赋值便不允许改变
    private transient Entry<K,V> root = null;  //红黑树的根节点
    private transient int size = 0;     //TreeMap中存放的键值对的数量
    private transient int modCount = 0;   //修改的次数
    

     

    源码解析

    由于TreeMap中源码较长,接下来将分段解析部分源码。既然是红黑树存储,肯定要有数据结构(Node)节点的。看一下TreeMap中关于节点的定义部分。

    数据结构

    static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;    //键
        V value;    //值
        Entry<K,V> left = null;     //左孩子节点
        Entry<K,V> right = null;    //右孩子节点
        Entry<K,V> parent;          //父节点
        boolean color = BLACK;      //节点的颜色,在红黑树种,只有两种颜色,红色和黑色
    
        //构造方法,用指定的key,value ,parent初始化,color默认为黑色
        Entry(K key, V value, Entry<K,V> parent) {
            this.key = key;
            this.value = value;
            this.parent = parent;
        }
    
        //返回key
        public K getKey() {
            return key;
        }
    
        //返回该节点对应的value
        public V getValue() {
            return value;
        }
    
        //替换节点的值,并返回旧值
        public V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }
        //重写equals()方法
        public boolean equals(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            //两个节点的key相等,value相等,这两个节点才相等
            return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
        }
        //重写hashCode()方法
        public int hashCode() {
            int keyHash = (key==null ? 0 : key.hashCode());
            int valueHash = (value==null ? 0 : value.hashCode());
            //key和vale hash值得异或运算,相同则为零,不同则为1 
            return keyHash ^ valueHash;
        }
        //重写toString()方法
        public String toString() {
            return key + "=" + value;
        }
    }

    构造方法

    //构造方法,comparator用键的顺序做比较
    public TreeMap() {
        comparator = null;
    }
    
    //构造方法,提供比较器,用指定比较器排序
    public TreeMap(Comparator<? super K> comparator) {
        his.comparator = comparator;
    }
    
    //将m中的元素转化daoTreeMap中,按照键的顺序做比较排序
    public TreeMap(Map<? extends K, ? extends V> m) {
        comparator = null;
        putAll(m);
    }
    
    //构造方法,指定的参数为SortedMap
    //采用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) {
        }
    }

    TreeMap提供了四个构造方法,实现了方法的重载。无参构造方法中比较器的值为null,采用自然排序的方法,如果指定了比较器则称之为定制排序.

    • 自然排序:TreeMap的所有key必须实现Comparable接口,所有的key都是同一个类的对象
    • 定制排序:创建TreeMap对象传入了一个Comparator对象,该对象负责对TreeMap中所有的key进行排序,采用定制排序不要求Map的key实现Comparable接口。等下面分析到比较方法的时候在分析这两种比较有何不同。

    对于Map来说,使用的最多的就是put()/get()/remove()等方法,下面依次进行分析

    put()

    public V put(K key, V value) {
        Entry<K,V> t = root;     //红黑树的根节点
        if (t == null) {        //红黑树是否为空
            compare(key, key); // type (and possibly null) check
            //构造根节点,因为根节点没有父节点,传入null值。 
            root = new Entry<>(key, value, null);  
            size = 1;     //size值加1
            modCount++;    //改变修改的次数
            return null;    //返回null 
        }
        int cmp;
        Entry<K,V> parent;    //定义节点
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;     //获取比较器
        if (cpr != null) {      //如果定义了比较器,采用自定义比较器进行比较
            do {
                parent = t;      //将红黑树根节点赋值给parent
                cmp = cpr.compare(key, t.key);     //比较key, 与根节点的大小
                if (cmp < 0)      //如果key < t.key , 指向左子树
                    t = t.left;   //t = t.left  , t == 它的做孩子节点
                else if (cmp > 0)
                    t = t.right;  //如果key > t.key , 指向它的右孩子节点
                else
                    return t.setValue(value);      //如果它们相等,替换key的值
            } 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)     // key < t.key 
                    t = t.left;   //左孩子
                else if (cmp > 0)   // key > t.key 
                    t = t.right;    //右孩子
                else
                    return t.setValue(value);   //t == t.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);   //新插入节点后重新调整红黑树 
        size++;
        modCount++;
        return null;
    }
    //比较方法,如果comparator==null ,采用comparable.compartTo进行比较,否则采用指定比较器比较大小
    final int compare(Object k1, Object k2) {
        return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
            : comparator.compare((K)k1, (K)k2);
    }
    
    private void fixAfterInsertion(Entry<K,V> x) {
        //插入的节点默认的颜色为红色
        x.color = RED;    //
        //情形1: 新节点x 是树的根节点,没有父节点不需要任何操作
        //情形2: 新节点x 的父节点颜色是黑色的,也不需要任何操作
    
        while (x != null && x != root && x.parent.color == RED) {
        //情形3:新节点x的父节点颜色是红色的
        //判断x的节点的父节点位置,是否属于左孩子
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
              //获取x节点的父节点的兄弟节点,上面语句已经判断出x节点的父节点为左孩子,所以直接取右孩子
             Entry<K,V> y = rightOf(parentOf(parentOf(x)));
             //判断是否x节点的父节点的兄弟节点为红色。
             if (colorOf(y) == RED) {
                  setColor(parentOf(x), BLACK); // x节点的父节点设置为黑色
                  setColor(y, BLACK);           // y节点的颜色设置为黑色
                  setColor(parentOf(parentOf(x)), RED); // x.parent.parent设置为红色
                  x = parentOf(parentOf(x)); // x == x.parent.parent ,进行遍历。
             } else {
                   //x的父节点的兄弟节点是黑色或者缺少的
                   if (x == rightOf(parentOf(x))) {   //判断x节点是否为父节点的右孩子
                        x = parentOf(x);     //x == 父节点
                        rotateLeft(x);    //左旋转操作
                   }
                   //x节点是其父的左孩子
                   setColor(parentOf(x), BLACK);
                   setColor(parentOf(parentOf(x)), RED);  //上面两句将x.parent 和x.parent.parent的颜色做调换
                   rotateRight(parentOf(parentOf(x)));   //进行右旋转
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));  //y 是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 是其父亲的左孩子
                        x = parentOf(x);
                        rotateRight(x);    //以父节点为旋转点,进行右旋操作
                    }
                    setColor(parentOf(x), BLACK);    //父节点为设置为黑色
                    setColor(parentOf(parentOf(x)), RED);  //祖父节点设置为红色
                    rotateLeft(parentOf(parentOf(x)));  //以父节点为旋转点,进行左旋操作
                }
            }
        }
        root.color = BLACK; //通过节点位置的调整,最终将红色的节点条调换到了根节点的位置,根节点重新设置为黑色
    }

    红黑树是一个更高效的检索二叉树,有如下特点:

    1. 每个节点只能是红色或者黑色
    2. 根节点永远是黑色的
    3. 所有的叶子的子节点都是空节点,并且都是黑色的
    4. 每个红色节点的两个子节点都是黑色的(不会有两个连续的红色节点)
    5. 从任一个节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点(叶子节点到根节点的黑色节点数量每条路径都相同)

    上面的代码,详细的标注了每条语句的作用,但是我相信,如果你没有一定的功力,即使注释已经很详细了,你也会是一脸懵逼 ,二脸懵逼,全脑懵逼中,下面配合图片来梳理一下代码所表示的含义:
    当一个默认为红色的节点插入树中,其实对应的是7中可能发生的情况,分别进行叙述:

    • 情形1:新插入的节点时红黑树的根节点,没有父节点,无需任何的操作,直接将颜色设置为黑色就可以了

    • 情形2:新节点的父节点颜色是黑色的,新插入的节点是红色的。也无需任何的操作。因为新节点的插入并没有影响到红黑书的特点

    • 情形3:新节点的父节点(左孩子节点)颜色是红色的,而父节点的兄弟节点颜色也是红色的。那么情况就出现了,此时插入的节点就违反了红黑树的特点4 ,需要对红黑树进行调整。 操作看下图:
      调整操作如上图,将父节点和父节点的兄弟节点,都修改为红色,然后将祖父节点修改为红色,因为修改了祖父节点的颜色,祖父节点可能会发生颜色的冲突,所以将新插入的节点修改为祖父节点,在进行调整。

    • 情形4:父节点(左孩子节点)的颜色为红色,父节点的兄弟节点的颜色为黑色或者为null,新插入的节点为父节点的右孩子节点。如下图:

      此时以父节点为旋转点,就新插入的节点进行左旋操作。便变成了情形5对应的情况,将执行情形5的操作

    • 情形5:父节点(左孩子节点)的颜色为红色,父节点的兄弟节点颜色为黑色或者null,新插入节点为父亲的左孩子节点。如下图:

    • 情形6 和情形7的操作与情形4和情形5的操作相同,它们之前的区别是父节点为有孩子节点,再次不再赘述。

    remove()

    public V remove(Object key) {
        Entry<K,V> p = getEntry(key);  //根据key查找节点,并返回该节点
        if (p == null)
            return null;
    
        V oldValue = p.value;    //获取key对应的值
        deleteEntry(p);     //删除节点
        return oldValue;   //返回key对应的值
    }
    
    final Entry<K,V> getEntry(Object key) {
        //根据键寻找节点,有非为两种方式,如果定制了比较器,采用定制排序方式,否则使用自然排序
        if (comparator != null) 
            return getEntryUsingComparator(key); //循环遍历树,寻找和key相等的节点
        if (key == null)
            throw new NullPointerException();
        Comparable<? super K> k = (Comparable<? super K>) key;
        Entry<K,V> p = root;
        while (p != null) {  //循环遍历树,寻找和key相等的节点
            int cmp = k.compareTo(p.key);
            if (cmp < 0)
                p = p.left;
            else if (cmp > 0)
                p = p.right;
            else
                return p;
        }
        return null;
    }
    //删除节点
    private void deleteEntry(Entry<K,V> p) {
        modCount++;  //记录修改的次数
        size--;   //数量减1
    
        //当前节点的两个孩子都不为空
        if (p.left != null && p.right != null) {
            //寻找继承者,继承者为当前节点的右孩子节点或者右孩子节点的最小左孩子
            Entry<K,V> s = successor(p);
            p.key = s.key;     //key - value  的替换 ,并没有替换颜色
            p.value = s.value;
            p = s;  //指向继承者
        } // p has 2 children
    
        // Start fixup at replacement node, if it exists.
        //开始修复树结构,继承者的左孩子不为空,返回左孩子,否则返回右孩子
        //不可能存在左右两个孩子都存在的情况,successor寻找的就是最小节点,它的左孩子节点为null
        Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
        if (replacement != null) {
            // Link replacement to parent
            //已经被选为继承者,当前拥有的一切放弃,所以将孩子交给爷爷抚养
            replacement.parent = p.parent;
            //p节点没有父节点,则指向根节点
            if (p.parent == null)
               root = replacement;
            //如果p为左孩子,如果p为左孩子,则将p.parent.left = p.left
            else if (p == p.parent.left)
                p.parent.left  = replacement;
            else
                p.parent.right = replacement;
    
            //删除p节点到左右分支,和父节点的引用
            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;
            }
        }
    }
    private void fixAfterDeletion(Entry<K,V> x) {
        //不是根节点,颜色为黑色,调整结构
        while (x != root && colorOf(x) == BLACK) {
    
            //判断x是否为左孩子
            if (x == leftOf(parentOf(x))) {
                //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)); //重新设置x的兄弟节点
                }
    
                if (colorOf(leftOf(sib))  == BLACK &&
                    colorOf(rightOf(sib)) == BLACK) {
                    setColor(sib, RED); //兄弟节点的两个孩子都是黑色的重新设置兄弟节点的颜色,修改为红色
                    x = parentOf(x);   //将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;  //设置x为根节点
                }
            } else { // symmetric
                //x为父节点的右节点,参考上面的操作
                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);
    }

    删除红黑树的操作比插入操作要稍微麻烦一点,分为两步:

    • 以排序二叉树的方法删除指定节点。删除的节点存在三种情况:
      • 被删除节点,没有左右孩子节点,直接删除即可
      • 被删除节点,有一个孩子节点,那么让它的孩子节点指向它的父节点即可
      • 本删除的节点,有两个非空的孩子节点,那么需要找到该节点的前驱或者后继节点,更换元素值,在将前驱或者后继节点删除(任意一个节点的前驱或者后继都必定至多有一个非空的子节点,可以按照前面的两种情形进行操作)
    • 进行颜色的调换和树的旋转,满足红黑树的特征

    下面来分情形讨论一下可能发生的情况:

    • 情形1:被删除的节点为根节点或者颜色为空色,此时删除该节点不影响红黑树的特点。无需操作
    • 情形2:被删除节点为黑色,兄弟节点为红色,如下图:

      若删除上图中的x节点,将缺少一个黑节点,与红黑树的性质冲突,所以修改sib颜色为黑色,设置p节点为红色,并进行左旋操作。在进行后续的处理。

    • 情形3:被删除节点为黑色,x节点的兄弟节点的子节点都是黑色,如下图:

      x节点是黑色的,兄弟节点(黑色的)的子节点也是黑色的,p节点的颜色无法确定,有可能是红色的,也有可能是黑色的。如果是红色的直接设置为黑色即可,如果为黑色的,则需要将x定位的p节点,在进行处理。

    • 情形4:被删除节点为黑色,x的兄弟节点的右自子节点为黑色。如下图:

      情形4的调整为了转变成情形5的情况,来进行处理。

    • 情形5:被删除节点为黑色,x的兄弟节点右子节点为红色。如下图:

      sib的左子节点的颜色不确定,可能是红色也可能是黑色,但是对它并没有什么影响,因为变换前后它的上层分支的黑色节点数并没有改变。

    上面的情形只是针对删除的节点是左孩子的情况,进行的分析,被删除的节点也可能是右分支。情况完全相同只不过左右顺序发生了颠倒,不再进行复述。

    至此TreeMap中实现的最重要已经说完了。

    下面简单说一下一些方法的作用

    • firstEntry() 返回Map中最小的key
    • higherEntry(Object key ) 返回该Map中位于key后一位的key-value
    • lowerEntry(Object key ) 返回该Map中唯一key前一位的key-value
    • tailMap(Object key , boolean inclusive) 返回该Map的子Map

    treemap中的迭代器

    abstract class SubMapIterator<T> implements Iterator<T> {
                TreeMap.Entry<K,V> lastReturned;
                TreeMap.Entry<K,V> next;
                final Object fenceKey;
                int expectedModCount;
    
                SubMapIterator(TreeMap.Entry<K,V> first,
                               TreeMap.Entry<K,V> fence) {
                    expectedModCount = m.modCount;
                    lastReturned = null;
                    next = first;
                    fenceKey = fence == null ? UNBOUNDED : fence.key;
                }
    
                public final boolean hasNext() {
                    return next != null && next.key != fenceKey;
                }
    
                final TreeMap.Entry<K,V> nextEntry() {
                    TreeMap.Entry<K,V> e = next;
                    if (e == null || e.key == fenceKey)
                        throw new NoSuchElementException();
                    if (m.modCount != expectedModCount)
                        throw new ConcurrentModificationException();
                    next = successor(e);
                    lastReturned = e;
                    return e;
                }
    ...}

    其中的successor方法实现, 实际上是个中序遍历, 对比二叉树中中序遍历的递归实现

    https://blog.csdn.net/asdfsadfasdfsa/article/details/82899840

     /**
         * Returns the successor of the specified Entry, or null if no such.
         */
        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;
            }
        }

    get()方法实现

    treemap.get()和treeset.contains()方法的实现, 是通过类nextEntry()方法一个一个比对而来的,相对于hashMap()的实现来说, 性能略差

    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 (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;
        }
    final Entry<K,V> getEntryUsingComparator(Object key) {
            @SuppressWarnings("unchecked")
                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;
        }

    总结

    • 关于红黑树的节点插入操作,首先是改变新节点,新节点的父节点,祖父节点,和新节点的颜色,能在当前分支通过节点的旋转改变的,则通过此种操作,来满足红黑书的特点。
    • 如果当前相关节点的旋转解决不了红黑树的冲突,则通过将红色的节点移动到根节点解决,最后在将根节点设置为黑色
    展开全文
  • TreeMap实现原理及源码分析

    千次阅读 2017-08-01 09:12:34
    TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建时提供的Comparator进行排序、 对于TreeMap而言,每个Entry都被当成“红黑树”的一个节点对待...

    TreeMap是一个有序的key-value集合,基于红黑树(Red-Black tree)实现。该映射根据其键的自然顺序进行排序,或者根据创建时提供的Comparator进行排序、

    对于TreeMap而言,每个Entry都被当成“红黑树”的一个节点对待,示例如下:

    public class TreeMapTest {
        public static void main(String[] args) {
            TreeMap<String, Float> map = new TreeMap<String, Float>();
            map.put("B", 88.0f);
            map.put("C", 95.0f);
            map.put("A", 90.0f);
    
            System.out.println(map);
        }
    }

    当程序执行map.put(“B”, 88.0f);时,系统将直接把 “B”-88.0f 这个Entry放入Map中,这个Entry就是该“红黑树”的根节点。接着程序执行 map.put(“C”, 95.0f); 时,会将 “C”-95.0f 作为新节点添加到已有的红黑树中。

    以后每向TreeMap中放入一个key-value对,系统都需要将该Entry当成一个新节点,添加到已有红黑树中,通过这种方式就可以保证TreeMap中所有key总是由小到大地排列。例如,输出上面程序,将看到如下结果(所有key由小到大地排列)。

    {A=90.0, B=88.0, C=95.0}

    对于TreeMap而言,由于它底层采用一颗“红黑树”来保存集合中的Entry,这意味着TreeMap添加元素、取出元素的性能都比HashMap低。当TreeMap添加元素时,需要通过循环找到新增Entry的插入位置,因此比较耗性能;当从TreeMap中取出元素时,需要通过循环才能找到合适的Entry,也比较耗性能。但TreeMap、TreeSet相比HashMap、HashSet的优势在于:TreeMap中的所有Entry总是按key根据指定排序规则保存有序状态,TreeSet中的所有元素总是根据指定排序规则保存有序状态。

    红黑树是一种自平衡二叉查找树,树中每个节点的值,都大于或等于在它的左子树中的所有节点的值,并且小于或等于在它的右子树中的所有节点的值,这确保红黑树运行时可以快速地在树中查找和定位的所需节点。

    对于TreeMap集合而言,其关键就是put(K key, V value), 该方法实现了将Entry放入TreeMap的Entry链,并保证该Entry链总是处于有序状态。下面是该方法的源代码。

    public V put(K key, V value) {
        // 先以 t 保存链表的 root 节点
        Entry<K,V> t = root;
        // 如果 t==null,表明是一个空链表,即该 TreeMap 里没有任何 Entry
        if (t == null) {
            // 将新的key-value创建一个 Entry,并将该 Entry 作为 root
            root = new Entry<K,V>(key, value, null);
        //设置该Map集合的size为1,代表包含一个Entry
            size = 1;
        //记录修改次数为1
            modCount++;
            return null;
        }
        int cmp;
        Entry<K,V> parent;
        // split comparator and comparable paths
        Comparator<? super K> cpr = comparator;
        // 如果比较器 cpr 不为 null,即表明采用定制排序
        if (cpr != null) {
            do {
                // 使用 parent 上次循环后的 t 所引用的 Entry
                parent = t;
            // 拿新插入的key和t的key进行比较
                cmp = cpr.compare(key, t.key);
            // 如果新插入的key小于t的key,t等于t的左边节点
                if (cmp < 0)
                    t = t.left;
            // 如果新插入的key大于t的key,t等于t的右边节点
                else if (cmp > 0)
                    t = t.right;
            // 如果两个key相等,新value覆盖原有的value,并返回原有的value
                else
                    return t.setValue(value);
            } while (t != null);
        }
        else {
            if (key == null)
                throw new NullPointerException();
            Comparable<? super K> k = (Comparable<? super K>) key;
            do {
            // 使用parent上次循环后的t所引用的Entry
                parent = t;
            // 拿新插入的key和t的key进行比较
                cmp = k.compareTo(t.key);
            // 如果新插入的key小于t的key,t等于t的左边节点
                if (cmp < 0)
                    t = t.left;
            // 如果新插入的key大于t的key,t等于t的右边节点
                else if (cmp > 0)
                    t = t.right;
            // 如果两个key相等,新value覆盖原有的value,并返回原有的value
                else
                    return t.setValue(value);
            } while (t != null);
        }
        // 将新插入的节点作为parent节点的子节点
        Entry<K,V> e = new Entry<K,V>(key, value, parent);
        // 如果新插入key小于parent的key,则e作为parent的左子节点
        if (cmp < 0)
            parent.left = e;
        // 如果新插入key小于parent的key,则e作为parent的右子节点
        else
            parent.right = e;
        // 修复红黑树
        fixAfterInsertion(e);          //①
        size++;
        modCount++;
        return null;
    }

    上面程序中的粗体字代码就是实现排序二叉树的关键算法。每当程序希望添加新节点时,总是从树的跟节点开始比较,即将跟节点当成当前节点。如果新增节点大于当前节点且当前节点的右子节点存在,则以右子节点作为当前节点;如果新增节点小于当前节点且当前节点的左子节点存在,则以左子节点作为当前节点;如果新增节点等于当前节点,则用新增节点覆盖当前节点,并结束循环–直到找到某个节点的左、右子节点不存在,将新节点添加为该节点的子节点。如果新节点比该节点大,则添加其为右子节点;如果新节点比该节点小,则添加其为左子节点。

    当TreeMap根据key来取出value时,TreeMap对应的方法如下。

    public V get(Object key) {
        // 根据指定key取出对应的Entry
        Entry<K,V> p = getEntry(key);
        // 返回该Entry所包含的value
        return (p==null ? null : p.value);
    }
    
    从上面程序代码可以看出,get(Object key)方法实质上是由getEntry()方法实现的。
    这个getEntry()方法的代码如下。
    
    final Entry<K,V> getEntry(Object key) {
        // 如果comparator不为null,表明程序采用定制排序
        if (comparator != null)
        // 调用getEntryUsingComparator方法取出对应的key
            return getEntryUsingComparator(key);
        // 如果key形参的值为null,抛出NullPointerException异常
        if (key == null)
            throw new NullPointerException();
    // 将key强制类型转换为Comparable实例
    Comparable<? super K> k = (Comparable<? super K>) key;
        // 从树的根节点开始
        Entry<K,V> p = root;
        while (p != null) {
            // 拿key与当前节点的key进行比较
            int cmp = k.compareTo(p.key);
        // 如果key小于当前节点的key,向左子树搜索
            if (cmp < 0)
                p = p.left;
        // 如果key大于当前节点的key,向右子树搜索
            else if (cmp > 0)
                p = p.right;
        // 如果既不大于也不小于,就是找到了目标Entry
            else
                return p;
        }
        return null;
    }

    上面的getEntry(Object obj)方法也是充分利用排序二叉树的特征来搜索目标Entry。程序依然从二叉树的根节点开始,如果被搜索节点大于当前节点,程序向“右子树”搜索;如果被搜索节点小于当前节点,程序向“左子树”搜索;如果相等,那就是找到了指定节点。

    当TreeMap里的comparator!=null,即表明该TreeMap采用了定制排序。在采用定制排序的方式下,TreeMap采用getEntryUsingComparator(key)方法来根据key获取Entry。下面是该方法的代码。

    final Entry<K,V> getEntryUsingComparator(Object key) {
        K k = (K) key;
        // 获取该TreeMap的comparator
            Comparator<? super K> cpr = comparator;
            if (cpr != null) {
            //从根节点开始
                Entry<K,V> p = root;
                while (p != null) {
                // 拿key与当前节点的key进行比较
                    int cmp = cpr.compare(k, p.key);
            // 如果key小于当前节点的key,向“左子树”搜索
                    if (cmp < 0)
                        p = p.left;
            // 如果key大于当前节点的key,向“右子树”搜索
                    else if (cmp > 0)
                        p = p.right;
            // 如果既不大于也不小于,就是找到了目标Entry
                    else
                        return p;
                }
            }
            return null;
    }

    其实getEntry,getEntryUsingComparator这2个方法的实现思路完全类似,只是前者对自然排序的TreeMap获取有效,后者对定制排序的TreeMap有效。

    通过上面源代码的分析不难看出,TreeMap这个工具类的实现其实很简单。或者说,从内部结构来看,TreeMap本质上就是一颗“红黑树”,而TreeMap的每个Entry就是该红黑树的一个节点。

    展开全文
  • 1 前言 本人使用的是jdk1.8版本。...学过数据结构的都知道二叉查找树是一种有序树,即进行中序遍历可以得到一组有序序列,所以TreeMap也是有序的Map集合。 在红黑树的加持下,TreeMap的众多方...
  • TreeMap是一个线程不安全,有序的键值对集合,因为TreeMap实现了SotredMap接口。底层是一个红黑树的数据结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行...
  • 在介绍TreeMap之前,我们来了解一种数据结构:二叉树。相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高。 二叉树结构又可再细分为二叉查找树和二叉平衡树 二叉查找树是一种有序...
  • HashMap不保证数据有序,LinkedHashMap保证数据可以保持插入顺序,而如果我们希望Map可以保持key的大小顺序的时候,我们就需要利用TreeMap了。 1 2 3 4 5 6 7 8 9 10 ...
  • TreeMap 原理

    2017-11-15 12:21:00
    TreeMap第一个想到的就是有序,当然也不是线程安全 TreeMap实现NavigableMap接口,说明支持一系列的导航方法 一、构造方法 public TreeMap() { comparator = null; } public TreeMap(Comparator<? ...
  • 先贴几篇博客: Java HashMap如何实现Key 的唯一性 Java TreeMap 红黑树介绍 HashMap,LinkedHashMap,TreeMap有序
  • 转载Java 集合系列12之 TreeMap详细介绍(源码解析)和使用示例 一、TreeMap 简单介绍 什么是Map?  在数组中我们通过数组下标来对数组内容进行索引的,而在Map... TreeMap是一个有序的key-value集合,是非线程安...
  • TreeMap原理剖析

    2019-05-25 15:38:29
    TreeMap是基于红黑树(一种自平衡的二叉查找树)实现的一个有序性的Map。注意该类并不是线程安全的,可以使用Collections.synchronizedSortedMap方法包装TreeMap使之转化成线程安全的map。要了解TreeMap必须先了红黑...
  • treeMap原理及其实现

    千次阅读 2017-11-07 14:08:48
    TreeMap是一个有序的key-value集合,他是通过红黑树实现的。 TreeMap继承于AbstractMap,所以它是一个Map,即一个key-value集合。 TreeMap实现了navigableMap接口,意味着它支持一系列的导航方法,返回有序的key...
  • TreeMap运用与原理

    2019-02-20 02:37:54
    我们提到,HashMap有一个重要局限,键值对之间没有特定的顺序,我们还提到,Map接口有另一个重要的实现类TreeMap,在TreeMap中,键值对之间按键有序TreeMap的实现基础是排序二叉树,上节我们介绍了排序二叉树的...
  • TreeMap是一种实现了有序的Map类型。 TreeMap基于红黑树原理实现。 TreeMap是线程不安全的。 TreeMap实现了 NavigableMap接口支持导航方法,TreeMap继承自AbstractMap。 put方法原理 1、判断有没有...
  • TreeMap实现了SotredMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在调用TreeMap的构造函数时没有指定比较器,则根据key执行自然排序。这点会在接下...
  • TreeMap

    2019-09-15 14:24:05
    TreeMap,原理是红黑树,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。操作是是一个entry节点,hashMap操作的是entry数组。线程不安全 put方法: 插入之后会修正颜色和节点位置,...
  • 转自 ...1、概述 文章的内容基于JDK1.7进行分析,之所以选用这个版本,是因为1.8的有些类做了改动,增加...TreeMap实现了SortedMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。...
  • 本文转载自https://my.oschina.net/90888/blog/1626065概述文章的内容基于JDK1.7进行分析,之...TreeMap实现了SotredMap接口,它是有序的集合。而且是一个红黑树结构,每个key-value都作为一个红黑树的节点。如果在...
  • 1.上一篇讲了LinkedHashMap实现有序原理,这票介绍一个另一种有序的Map,TreeMap。 同样是有序,两者大不一样,LinkedHashMap是按照插入顺序排序,而TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序。在...
  •  Map接口有三个比较重要的实现类,分别是HashMap、TreeMap和HashTable。在实际使用中,我们还经常使用LinkedHashMap、ConcurrentHashMap。 Map 有序性 线程安全性 备注 HashMap 无序 不安全 ...
  • 示例有序Map,分析他们的数据结构,简单清晰红黑树的原理
  • **Java的数据结构相关的类实现原理,比如LinkedList,ArrayList,HashMap,TreeMap HashMap是不是有序的?**
  • TreeMap源码解析(JDK1.7)

    2021-03-25 18:20:14
    TreeMap是键值对按键有序,为了实现Key有序,要求Key实现Comparable接口或者构造函数传入Comparator来保证Key的顺序。 相对于HashMap实现Map接口,TreeMap还实现了SortedMap和NavigationMap进一步提供总体顺序Map...
  • 1、 TreeMap的底层实现原理,基于红黑树的,有序。 2、默认采用升序,根据entry(key,value)中的key来确定先后顺序,假如你传入的key是int类型的,那么key越大,对应的entry越靠后。 3、存放进TreeMap的每一个元素...
  • TreeMap原理 TreeMap是一个有序的key-value集合,基于红黑树的 Navigable 实现。该映射根据其键的自然顺序进行排序,或者根据创建映射时提供的Comparator 进行排序 红黑树 根节点是黑色 每个节点都只能是红色...
  • 三个Map接口的常见实现类HashMap...有序存储,遍历之后的顺序是存储时的顺序,因为是使用链表的原理进行的存储 3.TreeMap 自动排序,按照key进行自动排序,使用二叉树储存 下面是他们的代码 1.HashMap public clas

空空如也

空空如也

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

treemap有序原理