javatreemap工作原理及实现-java开发java经验技巧

《javatreemap工作原理及实现-java开发java经验技巧》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、JavaTrccMapI作原理及实现-编程开发技术JavaTreeMap工作原理及实现原文出处：Yikun1.概述A?Red-Blacktree?basedNavigab1eMapimplementation.Themapissortedaccordingtothenaturalorderingofitskeys,orbyaComparatorprovidedatmapcreationtime,dependingonwhichconstructorisused.Thisimplcmcntationprovidesguarantccd

2、?log(n)timecost?forthecontainsKey,get,putandremoveoperations.AlgorithmsareadaptationsofthoseinCormen,Leiserson,andRivestsIntroductiontoAlgorithms.之前已经学习过HashMap和LinkedHashMap了,HashMap不保证数据冇序，LinkcdllashMap保证数据可以保持插入顺序，而如果我们希望Map可以保持key的大小顺序的时候,我们就需要利用TreeMap了。〃语文〃）;〃英语

3、〃）;〃数学〃）;〃政治〃）;〃历史〃）;〃地理〃）;〃生物〃）;〃化学〃）;TreeMaptmap=newTreeMap();tmap・put(1,tmap.put(3,tmap.put(2,tmap.put(4,tmap.put(5,tmap・put(6,tmap.put(7,tmap.put(8,for(Entryentry:tmap.entrySet()){System,out.printin(entry,getKey()+":〃

4、+entry.getValue());英大致的结构如下所示:root▲0tmap点comparsdescen■keyt>▲left▲paret>▲right>▲valuiBsize▲values{"语文，2二数学使用红黑树的好处是能够使得树具冇不错的平衡性，这样操作的速度就可以达到log(n)的水平了。具体红黑树的实现不在这里赘述，可以参考数据结构Z红黑树、wikipedia-红黑树等的实现。1.put函数Associatesthespecifie

5、dvaluewiththespecifiedkeyinthismap.Ifthemappreviouslycontainedamappingforthekey,theoldvalueisreplaced.如果存在的话，oldvalue被替换；如果不存在的话，则新添一个节点，然后对做红黑树的平衡操作。publicVput(Kkey,Vvalue){Entryt=root;if(t==null){compare(key,key);//type(andpossiblynull)checkroot=newEntryO(key,va

6、lue,nul1);size二1;modCount++;returnnull;}intcmp;Entryparent;//splitcomparatorandcomparablepathsComparatorcpr=comparator;//如果该节点存在，则替换值直接返回if(cpr!=null){do{parent=t;emp=cpr.compare(key,t.key);if(emp<0)t=t.1eft;elseif(emp>0)t二t.right;elsereturnt.setValue(val

7、ue);}whi1e(t!二nul1);}else{if(key==null)thrownewNullPointerException();@SuppressWarnings("unchecked")Comparablck=(Comparablc)key;do{parent二t;emp=k.compareTo(t・key);if(emp<0)t二t.left;elseif(emp>0)t二t.right;elsereturnt.setValue(value);}while(t!=null);}//

8、如果该节点未存在，则新建Entrye二newEntry<>(key,value,parent);辻(cmp<0)parent,left=e;elseparent,right=e;//红黑树平衡调整fixAfterlnsert