媒介

本文不规划延续前几篇的气势气魄(对所有的源码插手注释),因为要领略透TreeMap的所有源码,对博主来说,确实需要淹灭大量的时间和经验,今朝看来不大大概有这么多时间的投入,故这里意在通过于阅读源码对TreeMap有个宏观上的掌握,并就个中一些要领的实现做较量深入的阐明。

红黑树简介

TreeMap是基于红黑树实现的,这里只对红黑树做个简朴的先容,红黑树是一种非凡的二叉排序树,关于二叉排序树,拜见:http://blog.csdn.net/ns_code/article/details/19823463,红黑树通过一些限制,使其不会呈现二叉树排序树中极度的一边倒的环境,相对二叉排序树而言,这自然提高了查询的效率。

二叉排序树的基天性质如下:

1、每个节点都只能是赤色可能玄色

2、根节点是玄色

3、每个叶节点(NIL节点,空节点)是玄色的。

4、假如一个结点是红的,则它两个子节点都是黑的。也就是说在一条路径上不能呈现相邻的两个赤色结点。

5、从任一节点到其每个叶子的所有路径都包括沟通数目标玄色节点。

正是这些性质的限制,使得红黑树中任一节点到其子孙叶子节点的最长路径不会长于最短路径的2倍,因此它是一种靠近均衡的二叉树。

本栏目

说到红黑树,自然难免要和AVL树比拟一番。对较量而言,AVL树是严格的均衡二叉树,而红黑树不算严格意义上的均衡二叉树,只是靠近均衡,不会让树的高度如BST极度环境那样便是节点的个数。其实能用到红黑树的处所,也都可以用AVL树来实现,但红黑树的应用却很是遍及,而AVL树则很少被利用。在执行插入、删除操纵时,AVL树需要调解的次数一般要比红黑树多(红黑树的旋转调解最多只需三次),效率相对较低,且红黑树的统计机能较AVL树要好,虽然AVL树在查询效率上大概更胜一筹,但实际上也高不了几多。

红黑树的插入删除操纵很简朴,就是纯真的二叉排序树的插入删除操纵。红黑树被认为较量失常的处所自然在于插入删除后对红黑树的调解操纵(旋转和着色),主要是环境分的许多,限于篇幅及博主的熟悉水平优先,这里不规划具体先容插入删除后调解红黑树的各类环境及其实现,我们有个宏观上的相识即可,如须具体相识,拜见算法导论或一些相关的资料。

TreeMap源码分解

存储布局

TreeMap的排序是基于对key的排序实现的,它的每一个Entry代表红黑树的一个节点,Entry的数据布局如下:

static final class Entryimplements Map.Entry{    
     // 键    
     K key;    
     // 值    
     V value;    
     // 左孩子    
     Entryleft = null;    
     // 右孩子    
     Entryright = null;    
     // 父节点    
     Entryparent;    
     // 当前节点颜色    
     boolean color = BLACK;    
      
     // 结构函数    
     Entry(K key, V value, Entryparent) {    
         this.key = key;    
         this.value = value;    
         this.parent = parent;    
     }    
      
。。。。。  
}

结构要领

先来看下TreeMap的结构要领。TreeMap一共有4个结构要领。

1、无参结构要领

public TreeMap() {    
    comparator = null;    
}

回收无参结构要领,不指定较量器,这时候,排序的实现要依赖key.compareTo()要领,因此key必需实现Comparable接口,并覆写个中的compareTo要领。

2、带有较量器的结构要领

public TreeMap(Comparator comparator) {    
    this.comparator = comparator;    
}

回收带较量器的结构要领,这时候,排序依赖该较量器,key可以不消实现Comparable接口。

3、带Map的结构要领

public TreeMap(Map m) {    
    comparator = null;    
    putAll(m);    
}

该结构要领同样不指定较量器,挪用putAll要领将Map中的所有元素插手到TreeMap中。putAll的源码如下:

// 将map中的全部节点添加到TreeMap中    
public void putAll(Map map) {    
    // 获取map的巨细    
    int mapSize = map.size();    
    // 假如TreeMap的巨细是0,且map的巨细不是0,且map是已排序的“key-value对”    
    if (size==0 && mapSize!=0 && map instanceof SortedMap) {    
        Comparator c = ((SortedMap)map).comparator();    
        // 假如TreeMap和map的较量器相等;    
        // 则将map的元素全部拷贝到TreeMap中,然后返回!    
        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;    
        }    
    }    
    // 挪用AbstractMap中的putAll();    
    // AbstractMap中的putAll()又会挪用到TreeMap的put()    
    super.putAll(map);    
}

JAVA 教程

2017-12-28


媒介 本文不规划延续前几篇的气势气魄(对所有的源码插手注释),因为要领略透TreeMap的所有源码,对博主来说,确实需要淹灭大量的时间和经验,今朝看来不大大概有