欢迎来到天天文库
浏览记录
ID:34551048
大小:182.45 KB
页数:9页
时间:2019-03-07
《treemap的实现就是红黑树数据结构》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、TreeMap的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,这样就可以保证当需要快速检索指定节点。TreeSet和TreeMap的关系为了让大家了解TreeMap和TreeSet之间的关系,下面先看TreeSet类的部分源代码:publicclassTreeSetextendsAbstractSetimplementsNavigableSet,Cloneable,java.io.Serializable{//使用NavigableMap的key来保存Set集合的元素priva
2、tetransientNavigableMapm;//使用一个PRESENT作为Map集合的所有value。privatestaticfinalObjectPRESENT=newObject();//包访问权限的构造器,以指定的NavigableMap对象创建Set集合TreeSet(NavigableMapm){this.m=m;}publicTreeSet()//①{//以自然排序方式创建一个新的TreeMap,//根据该TreeSet创建一个TreeSet,/
3、/使用该TreeMap的key来保存Set集合的元素this(newTreeMap());}publicTreeSet(Comparatorcomparator)//②{//以定制排序方式创建一个新的TreeMap,//根据该TreeSet创建一个TreeSet,//使用该TreeMap的key来保存Set集合的元素this(newTreeMap(comparator));}publicTreeSet(Collectionc)
4、{//调用①号构造器创建一个TreeSet,底层以TreeMap保存集合元素this();//向TreeSet中添加Collection集合c里的所有元素addAll(c);}publicTreeSet(SortedSets){//调用②号构造器创建一个TreeSet,底层以TreeMap保存集合元素this(s.comparator());//向TreeSet中添加SortedSet集合s里的所有元素addAll(s);}//TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现..
5、.publicbooleanaddAll(Collectionc){if(m.size()==0&&c.size()>0&&cinstanceofSortedSet&&minstanceofTreeMap){//把c集合强制转换为SortedSet集合SortedSetset=(SortedSet)c;//把m集合强制转换为TreeMap集合TreeMapmap=(TreeMap)m;Comparat
6、orcc=(Comparator)set.comparator();Comparatormc=map.comparator();//如果cc和mc两个Comparator相等if(cc==mc
7、
8、(cc!=null&&cc.equals(mc))){//把Collection中所有元素添加成TreeMap集合的keymap.addAllForTreeSet(set,PRESENT);returntrue;}}//直接调用父类的addAll()方法来实现
9、returnsuper.addAll(c);}...}从上面代码可以看出,TreeSet的①号、②号构造器的都是新建一个TreeMap作为实际存储Set元素的容器,而另外2个构造器则分别依赖于①号和②号构造器,由此可见,TreeSet底层实际使用的存储容器就是TreeMap。与HashSet完全类似的是,TreeSet里绝大部分方法都是直接调用TreeMap的方法来实现的,这一点读者可以自行参阅TreeSet的源代码,此处就不再给出了。对于TreeMap而言,它采用一种被称为“红黑树”的排序二叉树来保存M
10、ap中每个Entry——每个Entry都被当成“红黑树”的一个节点对待。例如对于如下程序而言:publicclassTreeMapTest{publicstaticvoidmain(String[]args){TreeMapmap=newTreeMap();map.put("ccc",89.0);map.put("aaa",80.0);map.put("zzz",80
此文档下载收益归作者所有