Java源码解析TreeMap简介
TreeMap是常用的排序树,本文主要介绍TreeMap中,类的注释中对TreeMap的介绍。代码如下。
/** *ARed-Blacktreebased{@linkNavigableMap}implementation. *Themapissortedaccordingtothe{@linkplainComparablenatural *ordering}ofitskeys,orbya{@linkComparator}providedatmap *creationtime,dependingonwhichconstructorisused. *Thisimplementationprovidesguaranteedlog(n)timecostforthe *{@codecontainsKey},{@codeget},{@codeput}and{@coderemove} *operations.AlgorithmsareadaptationsofthoseinCormen,Leiserson,and *Rivest'sIntroductiontoAlgorithms. *
Notethattheorderingmaintainedbyatreemap,likeanysortedmap,and *whetherornotanexplicitcomparatorisprovided,mustbeconsistent *with{@codeequals}ifthissortedmapistocorrectlyimplementthe *{@codeMap}interface.(See{@codeComparable}or{@codeComparator}fora *precisedefinitionofconsistentwithequals.)Thisissobecause *the{@codeMap}interfaceisdefinedintermsofthe{@codeequals} *operation,butasortedmapperformsallkeycomparisonsusingits{@code *compareTo}(or{@codecompare})method,sotwokeysthataredeemedequalby *thismethodare,fromthestandpointofthesortedmap,equal.Thebehavior *ofasortedmapiswell-definedevenifitsorderingis *inconsistentwith{@codeequals};itjustfailstoobeythegeneralcontract *ofthe{@codeMap}interface. *
Notethatthisimplementationisnotsynchronized. *Ifmultiplethreadsaccessamapconcurrently,andatleastoneofthe *threadsmodifiesthemapstructurally,itmustbesynchronized *externally.(Astructuralmodificationisanyoperationthataddsor *deletesoneormoremappings;merelychangingthevalueassociated *withanexistingkeyisnotastructuralmodification.)Thisis *typicallyaccomplishedbysynchronizingonsomeobjectthatnaturally *encapsulatesthemap. *Ifnosuchobjectexists,themapshouldbe"wrapped"usingthe *{@linkCollections#synchronizedSortedMapCollections.synchronizedSortedMap} *method.Thisisbestdoneatcreationtime,topreventaccidental *unsynchronizedaccesstothemap:
*SortedMapm=Collections.synchronizedSortedMap(newTreeMap(...));*Theiteratorsreturnedbythe{@codeiterator}methodofthecollections *returnedbyallofthisclass's"collectionviewmethods"are *fail-fast:ifthemapisstructurallymodifiedatanytimeafter *theiteratoriscreated,inanywayexceptthroughtheiterator'sown *{@coderemove}method,theiteratorwillthrowa{@link *ConcurrentModificationException}.Thus,inthefaceofconcurrent *modification,theiteratorfailsquicklyandcleanly,ratherthanrisking *arbitrary,non-deterministicbehavioratanundeterminedtimeinthefuture. *
Notethatthefail-fastbehaviorofaniteratorcannotbeguaranteed *asitis,generallyspeaking,impossibletomakeanyhardguaranteesinthe *presenceofunsynchronizedconcurrentmodification.Fail-fastiterators *throw{@codeConcurrentModificationException}onabest-effortbasis. *Therefore,itwouldbewrongtowriteaprogramthatdependedonthis *exceptionforitscorrectness:thefail-fastbehaviorofiterators *shouldbeusedonlytodetectbugs. *
All{@codeMap.Entry}pairsreturnedbymethodsinthisclass *anditsviewsrepresentsnapshotsofmappingsatthetimetheywere *produced.Theydonotsupportthe{@codeEntry.setValue} *method.(Notehoweverthatitispossibletochangemappingsinthe *associatedmapusing{@codeput}.) *
Thisclassisamemberofthe *
*JavaCollectionsFramework. *@param thetypeofkeysmaintainedbythismap *@param thetypeofmappedvalues *@authorJoshBlochandDougLea *@seeMap *@seeHashMap *@seeHashtable *@seeComparable *@seeComparator *@seeCollection *@since1.2 **/
这是一个基于红黑树的可导航的实现。这个map基于key的可比较的自然顺序,或者基于在map创建时提供的Comparator的顺序来存储元素。
这个实现提供可保证的log(n)的时间复杂度来完成containsKey,get,put和remove操作。
需要注意到这一点,不管是否显式提供了排序器,如果这个排序map想要正确实现Map接口,treemap维护的顺序必须和equals保持一致,就像任何排序map那样。之所以会这样,是因为Map接口是根据equals操作来定义的,但是排序map进行所有key的比较时使用的是他们的compareTo方法,所以,从排序map的观点来看,被这个方法认为相等的两个key,才是相等的。尽管如果它的顺序和equals不一致,排序map的行为也是正常的,它只是没有遵守Map接口的通常约定。
请注意这个实现是非同步的。如果多个线程并发访问一个treemap,并且至少有一个线程修改结构,必须进行外部同步。这个通常是通过在包含这个map的对象上进行同步来实现的。如果没有这样的对象,那么这个map需要用Collections.synchronizedSortedMap方法包装一下。最好是在创建map时就这样做,以防止意外非同步访问这个map。代码如下SortedMapm=Collections.synchronizedSortedMap(newTreeMap(...));
所有这个类的集合视角方法返回的集合的iterator方法返回的迭代器都是fast-fail的:如果迭代器创建后的任何时间map发生了结构性改变,除了通过迭代器的删除方法外,迭代器都会抛出同步修改异常。于是,面对同步修改时,迭代器会迅速干净的失败,而不是冒着在未来的不确定的时间发生不一致或无法确定的行为的风险。
这个类和它的视图的方法返回的Map.Entry对代表了他们被创建时的快照。他们不支持Entry.setValue方法。
这个类是Java集合框架的一个成员。
总结
以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接