Java數(shù)據(jù)結(jié)構(gòu)與集合類

JavacollectionsAcollectionallowsagroupofobjectstobetreatedasasingleunit.Arbitraryobjectscanbestored,retrievedandmanipulatedaselementsofthesecollections.CollectionsFrameworkpresentsasetofstandardutilityclassestomanagesuchcollections.Itcontains'coreinterfaces,whichallowcollectionstobemanipulatedindependentoftheirimplementations.Theseinterfacesdefinethecommonfunctionalityexhibitedbycollectionsandfacilitatedataexchangebetweencollections.Asmallsetofimplementationsthatareconcreteimplementationsofthecoreinterfaces,providingdatastructuresthataprogramcanuse.Anassortmentofalgorithmstoperformvariousoperationssuchas,sortingandsearching.Collectionsframeworkisinterfacebased,collectionsareimplementedaccordingtotheirinterfacetype,ratherthanbyimplementationtypes.Byusingtheinterfaceswhenevercollectionsofobjectsneedtobehandled,interoperabilityandinterchangeabilityareachieved.ByconventioneachofthecollectionimplementationclassesprovideaconstructortocreateacollectionbasedontheelementsintheCollectionobjectpassedasargument.Bythesametoken,MapimplementationsprovideaconstructorthatacceptsaMapargument.Thisallowstheimplementationofacollection(Collection/Map)tobechanged.ButCollectionsandMapsarenotinterchangeable.InterfacesandtheirimplementationsinJava1.2Collection||—Set(nodupes,nullallowedbasedonimplementation)->HashSet||| |—SortedSet(OrderedSet)->TreeSet||—List(orderedcollection,dupesOK)->Vector,ArrayList,LinkedListMap(key-valuepairs,nullallowedbasedonimplementation)->HashTable,HashMap||—SortedMap(OrderedMap)->TreeMapInterfaceDescriptionCollectionAbasicinterfacethatdefinestheoperationsthatalltheclassesthatmaintaincollectionsofobjectstypicallyimplement.SetExtendsCollection,setsthatmaintainuniqueelements.SetinterfaceisdefinedintermsoftheequalsoperationSortedSetExtendsSet,maintaintheelementsinasortedorderListExtendsCollection,maintainelementsinasequentialorder,duplicatesallowed.MapAbasicinterfacethatdefinesoperationsthatclassesthatrepresentmappingsofkeystovaluestypicallyimplementSortedMapExtendsMapformapsthatmaintaintheirmappingsinkeyorder.Classesthatimplementtheinterfacesusedifferentstoragemechanisms.ArraysIndexedaccessisfaster.Makesinsertion,deletionandgrowingthestoremoredifficult.LinkedListSupportsinsertion,deletionandgrowingthestore.Butindexedaccessisslower.TreeSupportsinsertion,deletionandgrowingthestore.Indexedaccessisslower.Butsearchingisfaster.HashingSupportsinsertion,deletionandgrowingthestore.Indexedaccessisslower.Butsearchingisfaster.However,requirestheuseofuniquekeysforstoringdataelements.DataStructuresInterfacesSetSortedSetListMapSortedMapHashTableHashSetHashMapHashTableResizableArrayArrayListVectorBalancedTreeTreeSetTreeMapLinkedListLinkedListSomeoftheoperationsinthecollectioninterfacesareoptional,meaningthattheimplementingclassmaychoosenottoprovideaproperimplementationofsuchanoperation.Insuchacase,anUnsupportedOperationExceptionisthrownwhenthatoperationisinvoked.

InterfaceMethodsDescriptionCollectionBasicOperationsintsize();booleanisEmpty();booleancontains(Objectelement);booleanadd(Objectelement);booleanremove(Objectelement);Usedtoqueryacollectionaboutitscontents,andadd/removeelements.Theadd()andremove()methodsreturntrueifthecollectionwasmodifiedasaresultoftheoperation.Thecontains()methodchecksformembership.BulkOperationsbooleancontainsAll(Collectionc);booleanaddAll(Collectionc);booleanremoveAll(Collectionc);booleanretainAll(Collectionc);voidclear();Performonacollectionasasingleunit.Operationsareequivalentofsetlogiconarbitrarycollections(notjustsets).TheaddAll(),removeAll(),clear()andretainAll()methodsaredestructive.ArrayOperationsObject[]toArray();Object[]toArray(Objecta[]);ThesemethodscombinedwithArrays.asList()methodprovidethebridgebetweenarraysandcollections.IteratorsIteratoriterator();Iteratorisaninterfacewhichhasthesemethods.booleanhasNext();Objectnext();voidremove();Returnsaniterator,toiteratethecollection.Theremove()methodistheonlyrecommendedwaytoremoveelementsfromacollectionduringtheiteration.SetNonewmethodsdefined.Theadd()methodreturnsfalse,iftheelementisalreadyintheSet.Noexceptionsarethrown.ListElementAccessbyIndexObjectget(intindex);Objectset(intindex,Objectelement);voidadd(intindex,Objectelement);Objectremove(intindex);booleanaddAll(intindex,Collectionc);Firstindexis0,lastindexissize()-1.AnillegalindexthrowsIndexOutOfBoundsException.ElementSearchintindexOf(Objecto);intlastIndexOf(Objecto);Iftheelementisnotfound,return-1.

ListIteratorsListIteratorlistIterator();ListIteratorlistIterator(intindex);ListIteratorextendsIterator.Itallowsiterationinbothdirections.ListIterator,sadditionalmethods:booleanhasPrevious();booleanprevious();intnextIndex();intprviousIndex();voidset(Objecto);voidadd(Objecto);OpenRangeViewListsubList(intfromIndex,inttoIndex);ReturnsarangeofthelistfromfromIndex(inclusive)totoIndex(exclusive).Changestoviewarereflectedinthelistandviceversa.MapBasicOperationsObjectput(Objectkey,Objectvalue);Objectget(Objectkey);Objectremove(Objectkey);booleancontainsKey(Objectkey);booleancontainsValue(Objectvalue);intsize();booleanisEmpty();Theputmethodreplacestheoldvalue,ifthemappreviouslycontainedamappingforthatkey.Thegetmethodreturnsnull,ifthespecifiedkeycouldn,tbefOundinthemap.BulkOperationsvoidputAll(Mapt);voidclear();putAll()addsalltheelementsfromthespecifiedmap.clear()removesalltheelementsfromthemap.CollectionViewsSetkeySet();Collectionvalues();SetentrySet();Notethatthevalues()method,returnsaCollection,notaset.Reasonis,multipleuniquekeyscanmaptothesamevalue.ProvidedifferentviewsonaMap.Changestoviewsarereflectedinthemapandviceversa.Each<key,value>pairisrepresentedbyanObjectimplementingMap.Entryinterface.ObjectgetKey();ObjectgetValue();ObjectsetValue(Objectvalue);SortedSetRangeViewOperationsSortedSetheadSet(ObjecttoElement);SortedSettailSet(ObjectfromElement);SortedSetsubSet(ObjectfromElement,ObjecttoElement);fromElementisinclusive,toElementisexclusive.Theviewspresenttheelementssortedinthesameorderastheunderlyingsortedset.Min-MaxPointsObjectfirst();Objectlast();Returnthefirst(lowest)andlast(highest)elements.ComparatorAccessComparatorcomparator();ReturnsthecompartorassociatedwiththisSortedSet,ornullifitusesnaturalordering.SortedMapRangeViewOperationsSortedMapheadMap(ObjecttoKey);SortedSettailMap(ObjectfromKey);SortedSetsubMap(ObjectfromKey,ObjecttoKey);SortedMapissortedwithkeys.fromKeyisinclusive,toKeyisexclusive.Theviewspresenttheelementssortedinthesameorderastheunderlyingsortedmap.Min-MaxPointsObjectfirstKey();ObjectlastKey();Returnthefirst(lowest)andlast(highest)keys.ComparatorAccessComparatorcomparator();ReturnsthecompartorassociatedwiththisSortedMap,ornullifitusesnaturalordering.?SortinginSortedSetsandSortedMapscanbeimplementedintwoways.ObjectscanspecifytheirnaturalorderbyimplementingComparableinterface.ManyifthestandardclassesinJavaAPI,suchaswrapperclasses,String,DateandFileimplementthisinterface.Thisinterfacedefinesasinglemethod:intcompareTo(Objecto) returnsnegative,zero,positiveifthecurrentobjectislessthan,equaltoorgreaterthanthespecifiedobject.InthiscaseanaturalcomparatorqueriesobjectsimplementingComparableabouttheirnaturalorder.Objectsimplementingthisinterfacecanbeused:Aselementsinasortedset.Askeysinsortedmap.InlistswhichcanbesortedautomaticallybytheCollections.sort()method.Objectscanbesortedbyspecificcomparators,whichimplementComparatorinterface.Thisinterfacedefinesthefollowingmethod:intcompare(Objecto1,Objecto2) returnsnegative,zero,positiveifthefirstobjectislessthan,equaltoorgreaterthanthesecondobject.Itisrecommendedthatitsimplementationdoesn,tcontradictthesemanticsoftheequals()method.SpecificComparatorscanbespecifiedintheconstructorsofSortedSetsandSortedMaps.Allclassesprovideaconstructortocreateanemptycollection(correspondingtotheclass).HashSet,HashMap,HashTablecanalsobespecifiedwithaninitialcapacityaswellasaloadfactor(theratioofnumberofelementsstoredtoitscurrentcapacity).Mostofthetime,defaultvaluesprovideacceptableperformance.AVector,likeanarray,containsitemsthatcanbeaccessedusinganintegerindex.However,thesizeofaVectorcangrowandshrinkasneededtoaccommodateaddingandremovingitemsaftertheVectorhasbeencreated.Vector(5,10)meansinitialcapacity5,additionalallocation(capacityincrement)by10.StackextendsVectorandimplementsaLIFOstack.Withtheusualpush()andpop()methods,thereisapeek()methodtolookattheobjectatthetopofthestackwithoutremovingitfromthestack.Dictionaryisanobsoleteclass.HashTableextendsdictionary.Elementsarestoredaskey-valuepairs.VectorandHashTablearetheonlyclassesthatarethread-safe.ArrayList(doeswhatVectordoes),HashMap(doeswhatHashTabledoes),LinkedListandTreeMaparenewclassesinJava1.2InJava1.2,IteratorduplicatesthefunctionalityofEnumeration.NewimplementationsshouldconsiderIterator.Collectionsisaclass,Collectionisaninterface.Collectionsclassconsistsexclusivelyofstaticmethodsthatoperateonorreturncollections.SortingandSearchingalgorithmsintheCollectionsclass.staticintbinarySearch(Listlist,Objectkey)staticvoidfill(Listlist,Objecto)staticvoidshuffle(Listlist,Objecto)staticvoidsort(Listlist)Factorymethodstoprovidethread-safetyanddataimmutability.Thesemethodsreturnsynchronized(thread-safe)/immutablecollectionsfromthespecifiedcollections.ListsafeList=Collections.synchronizedList(newLinkedList());SortedMapfixedMap=Collections.unmodifiableSortedMap(newSortedMap());ConstantstodenoteimmutableemptycollectionsintheCollectionsclass:EMPTY_SET,EMPTY_LISTandEMPTY_MAP.Collectionsclassalsohasthefollowingmethods:MethodDescriptionpublicstaticSetsingleton(Objecto)ReturnsanimmutablesetcontainingonlythespecifiedobjectpublicstaticListsingletonList(Objecto)ReturnsanimmutablelistcontainingonlythespecifiedobjectpublicstaticMapsingletonMap(Objectkey,Objectvalue)Returnsanimmutablemapcontainingonlythespecifiedkey,valuepair.publicstaticListnCopies(intn,Objecto)Returnsanimmutablelistconsistingofncopiesofthespecifiedobject.Thenewlyallocateddataobjectistiny(itcontainsasinglereferencetothedataobject).ThismethodisusefulincombinationwiththeList.addAllmethodtogrowlists.TheclassArrays,providesusefulalgorithmsthatoperateonarrays.ItalsoprovidesthestaticasList()method,whichcanbeusedtocreateListviewsofarrays.ChangestotheListviewaffectsthearrayandviceversa.TheListsizeisthearraysizeandcannotbemodified.TheasList()methodintheArraysclassandthetoArray()methodintheCollectioninterfaceprovidethebridgebetweenarraysandcollections.SetmySet=newHashSet(Arrays.asList(myArray));String口strArray=(String[])mySet.toArray();Allconcreteimplementationsoftheinterfacesinjava.utilpackageareinheritedfromabstractimplementationsoftheinterfaces.Forexample,HashSetextendsAbstractSet,whichextendsAbstractCollection.LinkedListextendsAbstractList,whichextendsAbstractCollection.Theseabstractimplementationsalreadyprovidemostoftheheavymachinerybyimplementingrelevantinterfaces,sothatcustomizedimplementationsofcollectionscanbeeasilyimplementedusingthem.BitSetclassimplementsavectorofbitsthatgrowsasneeded.Eachcomponentofthebitsethasabooleanvalue.ThebitsofaBitSetareindexedbynonnegativeintegers.Individualindexedbitscanbeexamined,set,orcleared.OneBitSetmaybeusedtomodifythecontentsofanotherBitSetthroughlogicalAND,logicalinclusiveOR,andlogicalexclusiveORoperations.Bydefault,allbitsinthesetinitiallyhavethevaluefalse.ABitSethasasizeof64,whencreatedwithoutspecifyinganysize.ConcurrentModificationExceptionexception(extendsRuntimeException)maybethrownbymethodsthathavedetectedconcurrentmodificationofabackingobjectwhensuchmodificationisnotpermissible.Forexample,itisnotpermssibleforonethreadtomodifyaCollectionwhileanotherthreadisiteratingoverit.Ingeneral,theresultsoftheiterationareundefinedunderthesecircumstances.SomeIteratorimplementations(includingthoseofallthecollectionimplementationsprovidedbytheJDK)maychoosetothrowthisexceptionifthisbehaviorisdetected.Iteratorsthatdothisareknownasfail-fastiterators,astheyfailquicklyandcleanly,ratherthatriskingarbitrary,non-deterministicbehavioratanund