外文文献-high-level programming language java collections of objects高级编程语言 java之集合与对象

毕业设计外文文献原文及译文HIGHLEVELPROGRAMMINGLANGUAGEJAVACOLLECTIONSOFOBJECTS高级编程语言JAVA之集合与对象学生姓名学号系别专业指导教师2015年5月电子与计算机科学技术系网络工程HIGHLEVELPROGRAMMINGLANGUAGEJAVACOLLECTIONSOFOBJECTSITSAFAIRLYSIMPLEPROGRAMTHATHASONLYAFIXEDQUANTITYOFOBJECTSWITHKNOWNLIFETIMESINGENERAL,YOURPROGRAMSWILLALWAYSBECREATINGNEWOBJECTSBASEDONSOMECRITERIATHATWILLBEKNOWNONLYATTHETIMETHEPROGRAMISRUNNINGYOUWONTKNOWUNTILRUNTIMETHEQUANTITYOREVENTHEEXACTTYPEOFTHEOBJECTSYOUNEEDTOSOLVETHEGENERALPROGRAMMINGPROBLEM,YOUNEEDTOBEABLETOCREATEANYNUMBEROFOBJECTS,ANYTIME,ANYWHERESOYOUCANTRELYONCREATINGANAMEDREFERENCETOHOLDEACHONEOFYOUROBJECTSMYOBJECTMYREFERENCESINCEYOULLNEVERKNOWHOWMANYOFTHESEYOULLACTUALLYNEEDMOSTLANGUAGESPROVIDESOMEWAYTOSOLVETHISRATHERESSENTIALPROBLEMJAVAHASSEVERALWAYSTOHOLDOBJECTSORRATHER,REFERENCESTOOBJECTSTHEBUILTINTYPEISTHEARRAY,WHICHHASBEENDISCUSSEDBEFOREALSO,THEJAVAUTILITIESLIBRARYHASAREASONABLYCOMPLETESETOFCONTAINERCLASSESALSOKNOWNASCOLLECTIONCLASSES,BUTBECAUSETHEJAVA2LIBRARIESUSETHENAMECOLLECTIONTOREFERTOAPARTICULARSUBSETOFTHELIBRARY,ISHALLALSOUSETHEMOREINCLUSIVETERM“CONTAINER”CONTAINERSPROVIDESOPHISTICATEDWAYSTOHOLDANDEVENMANIPULATEYOUROBJECTSARRAYSHOLDINGOBJECTSISTHEFOCUSOFTHISCHAPTER,ANDANARRAYISJUSTONEWAYTOHOLDOBJECTSBUTTHEREAREANUMBEROFOTHERWAYSTOHOLDOBJECTS,SOWHATMAKESANARRAYSPECIALTHEREARETWOISSUESTHATDISTINGUISHARRAYSFROMOTHERTYPESOFCONTAINERSEFFICIENCYANDTYPETHEARRAYISTHEMOSTEFFICIENTWAYTHATJAVAPROVIDESTOSTOREANDRANDOMLYACCESSASEQUENCEOFOBJECTREFERENCESTHEARRAYISASIMPLELINEARSEQUENCE,WHICHMAKESELEMENTACCESSFAST,BUTYOUPAYFORTHISSPEEDWHENYOUCREATEANARRAYOBJECT,ITSSIZEISFIXEDANDCANNOTBECHANGEDFORTHELIFETIMEOFTHATARRAYOBJECTYOUMIGHTSUGGESTCREATINGANARRAYOFAPARTICULARSIZEANDTHEN,IFYOURUNOUTOFSPACE,CREATINGANEWONEANDMOVINGALLTHEREFERENCESFROMTHEOLDONETOTHENEWONETHISISTHEBEHAVIOROFTHEARRAYLISTCLASS,WHICHWILLBESTUDIEDLATERINTHISCHAPTERHOWEVER,BECAUSEOFTHEOVERHEADOFTHISFLEXIBILITY,ANARRAYLISTISMEASURABLYLESSEFFICIENTTHANANARRAYINC,THEVECTORCONTAINERCLASSDOESKNOWTHETYPEOFOBJECTSITHOLDS,BUTITHASADIFFERENTDRAWBACKWHENCOMPAREDWITHARRAYSINJAVATHECVECTORSOPERATORDOESNTDOBOUNDSCHECKING,SOYOUCANRUNPASTTHEEND1INJAVA,YOUGETBOUNDSCHECKINGREGARDLESSOFWHETHERYOUREUSINGANARRAYORACONTAINERYOULLGETARUNTIMEEXCEPTIONIFYOUEXCEEDTHEBOUNDSTHISTYPEOFEXCEPTIONINDICATESAPROGRAMMERERROR,ANDTHUSYOUDONTNEEDTOCHECKFORITINYOURCODEASANASIDE,THEREASONTHECVECTORDOESNTCHECKBOUNDSWITHEVERYACCESSISSPEEDINJAVAYOUHAVETHECONSTANTPERFORMANCEOVERHEADOFBOUNDSCHECKINGALLTHETIMEFORBOTHARRAYSANDCONTAINERSTHEOTHERGENERICCONTAINERCLASSESLIST,SET,ANDMAP,ALLDEALWITHOBJECTSASIFTHEYHADNOSPECIFICTYPETHATIS,THEYTREATTHEMASTYPEOBJECT,THEROOTCLASSOFALLCLASSESINJAVATHISWORKSFINEFROMONESTANDPOINTYOUNEEDTOBUILDONLYONECONTAINER,ANDANYJAVAOBJECTWILLGOINTOTHATCONTAINEREXCEPTFORPRIMITIVESTHESECANBEPLACEDINCONTAINERSASCONSTANTSUSINGTHEJAVAPRIMITIVEWRAPPERCLASSES,ORASCHANGEABLEVALUESBYWRAPPINGINYOUROWNCLASSTHISISTHESECONDPLACEWHEREANARRAYISSUPERIORTOTHEGENERICCONTAINERSWHENYOUCREATEANARRAY,YOUCREATEITTOHOLDASPECIFICTYPETHISMEANSTHATYOUGETCOMPILETIMETYPECHECKINGTOPREVENTYOUFROMPUTTINGTHEWRONGTYPEIN,ORMISTAKINGTHETYPETHAT1ITSPOSSIBLE,HOWEVER,TOASKHOWBIGTHEVECTORIS,ANDTHEATMETHODDOESPERFORMBOUNDSCHECKINGYOUREEXTRACTINGOFCOURSE,JAVAWILLPREVENTYOUFROMSENDINGANINAPPROPRIATEMESSAGETOANOBJECT,EITHERATCOMPILETIMEORATRUNTIMESOITSNOTMUCHRISKIERONEWAYORTHEOTHER,ITSJUSTNICERIFTHECOMPILERPOINTSITOUTTOYOU,FASTERATRUNTIME,ANDTHERESLESSLIKELIHOODTHATTHEENDUSERWILLGETSURPRISEDBYANEXCEPTIONFOREFFICIENCYANDTYPECHECKINGITSALWAYSWORTHTRYINGTOUSEANARRAYHOWEVER,WHENYOURETRYINGTOSOLVEAMOREGENERALPROBLEMARRAYSCANBETOORESTRICTIVEARRAYSAREFIRSTCLASSOBJECTSREGARDLESSOFWHATTYPEOFARRAYYOUREWORKINGWITH,THEARRAYIDENTIFIERISACTUALLYAREFERENCETOATRUEOBJECTTHATSCREATEDONTHEHEAPTHISISTHEOBJECTTHATHOLDSTHEREFERENCESTOTHEOTHEROBJECTS,ANDITCANBECREATEDEITHERIMPLICITLY,ASPARTOFTHEARRAYINITIALIZATIONSYNTAX,OREXPLICITLYWITHANEWEXPRESSIONPARTOFTHEARRAYOBJECTINFACT,THEONLYFIELDORMETHODYOUCANACCESSISTHEREADONLYLENGTHMEMBERTHATTELLSYOUHOWMANYELEMENTSCANBESTOREDINTHATARRAYOBJECTTHESYNTAXISTHEONLYOTHERACCESSTHATYOUHAVETOTHEARRAYOBJECTTHEARRAYSCLASSINJAVAUTIL,YOULLFINDTHEARRAYSCLASS,WHICHHOLDSASETOFSTATICMETHODSTHATPERFORMUTILITYFUNCTIONSFORARRAYSTHEREAREFOURBASICMETHODSEQUALS,TOCOMPARETWOARRAYSFOREQUALITYFILL,TOFILLANARRAYWITHAVALUESORT,TOSORTTHEARRAYANDBINARYSEARCH,TOFINDANELEMENTINASORTEDARRAYALLOFTHESEMETHODSAREOVERLOADEDFORALLTHEPRIMITIVETYPESANDOBJECTSINADDITION,THERESASINGLEASLISTMETHODTHATTAKESANYARRAYANDTURNSITINTOALISTCONTAINERWHILEUSEFUL,THEARRAYSCLASSSTOPSSHORTOFBEINGFULLYFUNCTIONALFOREXAMPLE,ITWOULDBENICETOBEABLETOEASILYPRINTTHEELEMENTSOFANARRAYWITHOUTHAVINGTOCODEAFORLOOPBYHANDEVERYTIMEANDASYOULLSEE,THEFILLMETHODONLYTAKESASINGLEVALUEANDPLACESITINTHEARRAY,SOIFYOUWANTEDFOREXAMPLETOFILLANARRAYWITHRANDOMLYGENERATEDNUMBERS,FILLISNOHELPTHUSITMAKESSENSETOSUPPLEMENTTHEARRAYSCLASSWITHSOMEADDITIONALUTILITIES,WHICHWILLBEPLACEDINTHEPACKAGECOMBRUCEECKELUTILFORCONVENIENCETHESEWILLPRINTANARRAYOFANYTYPE,ANDFILLANARRAYWITHVALUESOROBJECTSTHATARECREATEDBYANOBJECTCALLEDAGENERATORTHATYOUCANDEFINEINTRODUCTIONTOCONTAINERSTOME,CONTAINERCLASSESAREONEOFTHEMOSTPOWERFULTOOLSFORRAWDEVELOPMENTBECAUSETHEYSIGNIFICANTLYINCREASEYOURPROGRAMMINGMUSCLETHEJAVA2CONTAINERSREPRESENTATHOROUGHREDESIGN5OFTHERATHERPOORSHOWINGSINJAVA10AND11SOMEOFTHEREDESIGNMAKESTHINGSTIGHTERANDMORESENSIBLEITALSOFILLSOUTTHEFUNCTIONALITYOFTHECONTAINERSLIBRARY,PROVIDINGTHEBEHAVIOROFLINKEDLISTS,QUEUES,ANDDEQUESDOUBLEENDEDQUEUES,PRONOUNCED“DECKS”THEDESIGNOFACONTAINERSLIBRARYISDIFFICULTTRUEOFMOSTLIBRARYDESIGNPROBLEMSINC,THECONTAINERCLASSESCOVEREDTHEBASESWITHMANYDIFFERENTCLASSESTHISWASBETTERTHANWHATWASAVAILABLEPRIORTOTHECCONTAINERCLASSESNOTHING,BUTITDIDNTTRANSLATEWELLINTOJAVAONTHEOTHEREXTREME,IVESEENACONTAINERSLIBRARYTHATCONSISTSOFASINGLECLASS,“CONTAINER,”WHICHACTSLIKEBOTHALINEARSEQUENCEANDANASSOCIATIVEARRAYATTHESAMETIMETHEJAVA2CONTAINERLIBRARYSTRIKESABALANCETHEFULLFUNCTIONALITYTHATYOUEXPECTFROMAMATURECONTAINERLIBRARY,BUTEASIERTOLEARNANDUSETHANTHECCONTAINERCLASSESANDOTHERSIMILARCONTAINERLIBRARIESTHERESULTCANSEEMABITODDINPLACESUNLIKESOMEOFTHEDECISIONSMADEINTHEEARLYJAVALIBRARIES,THESEODDITIESWERENOTACCIDENTS,BUTCAREFULLYCONSIDEREDDECISIONSBASEDONTRADEOFFSINCOMPLEXITYITMIGHTTAKEYOUALITTLEWHILETOGETCOMFORTABLEWITHSOMEASPECTSOFTHELIBRARY,BUTITHINKYOULLFINDYOURSELFRAPIDLYACQUIRINGANDUSINGTHESENEWTOOLSASMENTIONEDBEFORE,THEREARETWOBASICCATEGORIESINTHEJAVACONTAINERLIBRARYTHEDISTINCTIONISBASEDONTHENUMBEROFITEMSTHATAREHELDINEACHLOCATIONOFTHECONTAINERTHECOLLECTIONCATEGORYONLYHOLDSONEITEMINEACHLOCATIONTHENAMEISABITMISLEADINGSINCEENTIRECONTAINERLIBRARIESAREOFTENCALLED“COLLECTIONS”ITINCLUDESTHELIST,WHICHHOLDSAGROUPOFITEMSINASPECIFIEDSEQUENCE,ANDTHESET,WHICHONLYALLOWSTHEADDITIONOFONEITEMOFEACHTYPETHEARRAYLISTISATYPEOFLIST,ANDHASHSETISATYPEOFSETTOADDITEMSTOANYCOLLECTION,THERESANADDMETHODTHEMAPHOLDSKEYVALUEPAIRS,RATHERLIKEAMINIDATABASETHEABOVEPROGRAMUSESONEFLAVOROFMAP,THEHASHMAPIFYOUHAVEAMAPTHATASSOCIATESSTATESWITHTHEIRCAPITALSANDYOUWANTTOKNOWTHECAPITALOFOHIO,YOULOOKITUPALMOSTASIFYOUWEREINDEXINGINTOANARRAYMAPSAREALSOCALLEDASSOCIATIVEARRAYSTOADDELEMENTSTOAMAPTHERESAPUTMETHODTHATTAKESAKEYANDAVALUEASARGUMENTSTHEABOVEEXAMPLEONLYSHOWSADDINGELEMENTSANDDOESNOTLOOKTHEELEMENTSUPAFTERTHEYREADDEDTHATWILLBESHOWNLATERTHEOVERLOADEDFILLMETHODSFILLCOLLECTIONSANDMAPS,RESPECTIVELYIFYOULOOKATTHEOUTPUT,YOUCANSEETHATTHEDEFAULTPRINTINGBEHAVIORPROVIDEDVIATHECONTAINERSVARIOUSTOSTRINGMETHODSPRODUCESQUITEREADABLERESULTS,SONOADDITIONALPRINTINGSUPPORTISNECESSARYASITWASWITHARRAYSACOLLECTIONISPRINTEDSURROUNDEDBYSQUAREBRACES,WITHEACHELEMENTSEPARATEDBYACOMMAAMAPISSURROUNDEDBYCURLYBRACES,WITHEACHKEYANDVALUEASSOCIATEDWITHANEQUALSIGNKEYSONTHELEFT,VALUESONTHERIGHTYOUCANALSOIMMEDIATELYSEETHEBASICBEHAVIOROFTHEDIFFERENTCONTAINERSTHELISTHOLDSTHEOBJECTSEXACTLYASTHEYAREENTERED,WITHOUTANYREORDERINGOREDITINGTHESET,HOWEVER,ONLYACCEPTSONEOFEACHOBJECTANDITUSESITSOWNINTERNALORDERINGMETHODINGENERAL,YOUAREONLYCONCERNEDWITHWHETHERORNOTSOMETHINGISAMEMBEROFTHESET,NOTTHEORDERINWHICHITAPPEARSFORTHATYOUDUSEALISTANDTHEMAPALSOONLYACCEPTSONEOFEACHTYPEOFITEM,BASEDONTHEKEY,ANDITALSOHASITSOWNINTERNALORDERINGANDDOESNOTCAREABOUTTHEORDERINWHICHYOUENTERTHEITEMSIFMAINTAININGTHEINSERTIONSEQUENCEISIMPORTANT,YOUCANUSEALINKEDHASHSETORLINKEDHASHMAPSUMMARYANARRAYASSOCIATESNUMERICALINDICESTOOBJECTSITHOLDSOBJECTSOFAKNOWNTYPESOTHATYOUDONTHAVETOCASTTHERESULTWHENYOURELOOKINGUPANOBJECTITCANBEMULTIDIMENSIONAL,ANDITCANHOLDPRIMITIVESHOWEVER,ITSSIZECANNOTBECHANGEDONCEYOUCREATEITACOLLECTIONHOLDSSINGLEELEMENTS,WHILEAMAPHOLDSASSOCIATEDPAIRSLIKEANARRAY,ALISTALSOASSOCIATESNUMERICALINDICESTOOBJECTSYOUCANTHINKOFARRAYSANDLISTSASORDEREDCONTAINERSTHELISTAUTOMATICALLYRESIZESITSELFASYOUADDMOREELEMENTSBUTALISTCANHOLDONLYOBJECTREFERENCES,SOITWONTHOLDPRIMITIVESANDYOUMUSTALWAYSCASTTHERESULTWHENYOUPULLANOBJECTREFERENCEOUTOFACONTAINERUSEANARRAYLISTIFYOUREDOINGALOTOFRANDOMACCESSES,ANDALINKEDLISTIFYOUWILLBEDOINGALOTOFINSERTIONSANDREMOVALSINTHEMIDDLEOFTHELISTTHEBEHAVIOROFQUEUES,DEQUES,ANDSTACKSISPROVIDEDVIATHELINKEDLISTAMAPISAWAYTOASSOCIATENOTNUMBERS,BUTOBJECTSWITHOTHEROBJECTSTHEDESIGNOFAHASHMAPISFOCUSEDONRAPIDACCESS,WHILEATREEMAPKEEPSITSKEYSINSORTEDORDER,ANDTHUSISNOTASFASTASAHASHMAPALINKEDHASHMAPKEEPSITSELEMENTSININSERTIONORDER,BUTMAYALSOREORDERTHEMWITHITSLRUALGORITHMASETONLYACCEPTSONEOFEACHTYPEOFOBJECTHASHSETSPROVIDEMAXIMALLYFASTLOOKUPS,WHILETREESETSKEEPTHEELEMENTSINSORTEDORDERLINKEDHASHSETSKEEPELEMENTSININSERTIONORDERTHERESNONEEDTOUSETHELEGACYCLASSESVECTOR,HASHTABLEANDSTACKINNEWCODEHIGHLEVELPROGRAMMINGLANGUAGEJAVACOLLECTIONSOFOBJECTS高级编程语言JAVA之集合与对象如果程序只包含固定数量的对象，并且其生命周期都已知，那么这个程序就实在太简单了。通常，你的程序会根据运行时才知道的条件创建新对象。不到运行期，不会知道所需对象的数量，甚至不知道确切的类型。为解决这个普遍的编程问题，需要能够在任意时刻，任意位置，创建任意数量的对象。所以，你就不能指望创建具名的引用来持有每一个对象MYOBJECTMYREFERENCE；因为你不知道实际上会需要多少这样的引用。大多数语言都提供了某种方法来解决这个基本问题。JAVA有多种方式保存对象（应该说是对象的引用REFERENCE）。例如前面曾经学习过的数组，它是语言内置的类型。JAVA实用类库还提供了一套相当完整的容器类（也称为集合类，但由于JAVA2的类库中使用了COLLECTION来指代该类库的一个特殊子集，所以我使用“容器”称呼它们）。容器提供了近乎完美的方式来保存和操纵对象。数组这里的主题是持有对象，而数组正是保存对象的方式之一。不过持有对象还有许多别的方式，那么数组在其中有什么特别之处呢数组与其它种类的容器之间的区别有三方面效率、类型和持有基本类型的能力。在JAVA中，数组是一种效率最高的存储和随机访问对象引用序列的方式。数组就是个简单的线性序列，这使得元素访问非常快速，但也损失了其他一些特性。当你创建了一个数组对象（将数组本身作为对象看待），数组的大小就被固定了，并且这个数组的生命周期也是不可改变的。通常是创建一个特定大小的数组，在空间不足的时候再创建一个新的数组，然后把旧数组中所有的引用移到新数组中。这正是后面会学到的ARRAYLIST类的行为方式。然而这种弹性带来的开销，使得ARRAYLIST比数组效率低。在C中，容器类VECTOR知道自己保存的对象是何类型，不过与JAVA中的数组相比，它有一个缺点C中VECTOR的操作符不做边界检查，所以你可能会越界操作。1而在JAVA中，无论你使用数组或容器，都有边界检查。如果越界操作就会得到一个RUNTIMEEXCEPTION异常。这类异常通常说明是程序员的错误，因此你不必自己作越界检查。多说一句，为了速度，C的VECTOR存取访问不作边界检查；而JAVA的数组与容器会因为时刻存在的边界检查带来固定的性能开销。其它通用的容器类LIST,SET和MAP，它们不以具体的类型来处理对象。换句话说，它们将所有对象都按OBJECT类型处理，即JAVA中所有类的基类。从某个角度来说，这种方式很好你只需要做一个容器，任意的JAVA对象都可以放入其中。（除了基本类型，可以使用JAVA包装类将其作为常量包装后存入容器，或者用你自己的类将其作为变量包装起来存入容器）这正是数组比通用容器优越的第二点当你创建一个数组时，它只能保存特定类型的数据（这与第三点相关数组可以保存基本类型，容器则不能）。这意味着会在编译期做类型检查，以防止你将错误的类型插入数组，或取出数据时弄错类型。当然，无论在编译期还是运行期，JAVA都会阻止你向对象发送不恰当的消息。所以并不是说哪种方法更不安全，只是如果编译期就能够指出错误，那么程序可以运行得更快，也减少了程序的使用者被异常吓着的可能性。考虑到效率与类型检查，应该尽可能使用数组。然而，如果要解决更一般化的问题，数组就太受限制了。ARRAYS类在JAVAUTIL类库中可以找到ARRAYS类，它有一套STATIC方法，提供操作数组的实用功能。其中有四个基本方法EQUALS，比较两个数组是否相等；FILL，用某个值填充整个数组；SORT，对数组排序；还有BINARYSEARCH，在已经排序的数组中查找元素。所有这些方法都被各种基本类型和OBJECT类重载过。此外，方法ASLIST接受任意的数组为参数，并将其转变为LIST容器。ARRAYS类虽然很有用，但是它却仍然不具备完备的功能。例如，如果能够很容易地打印数组的所有元素，而不需要每次都需要自己去编写FOR循环的代码，那就太好了。而且你会看到，方法FILL只能以某个单一的值填充整个数组，如果你想用随机生成的若干数字填充数组，FILL就无能为力了。所以为ARRAYS类添加这样一些实用功能会很有帮助，我将它们打包放入COMBRUCEECKELUTIL包中，以便于使用。利用它们可以打印任意类型的数组，以不同的值或对象填充数组，这些对象由你定义的“生成器（GENERATOR）”对象创建。容器简介就我而言，容器类对于新的开发者是最强大的工具之一，可以大幅提高编程能力。由于JAVA10和11中容器的可怜表现，在JAVA2中，所有的容器都经过重新设计。某些容器改变不大，但多数容器完全改变了。提供了类似链表（LINKEDLIST），队列（QUEUE）和双向队列（DEQUE，发音同“DECKS”）的行为，丰富了容器类库的功能。设计容器类库是很困难的事（多数类库的设计也都如此）。在C中，容器类是用许多不同的类组成了基础，这好过C早期根本没有容器类，但是JAVA并不是这样的。我还见过的另一种极端情况是，整个容器类类库只有一个类，“CONTAINER”，其行为既像是线性序列（LINEARSEQUENCE），又像是关联数组（ASSOCIATIVEARRAY）。JAVA2的容器类类库强调平衡成熟的容器类类库应具备你所期望得到的完整功能，但比C的容器和其他类似的容器更易于学习与使用。于是其结果看起来就有点奇怪。这与早期JAVA类库的某些决策不同，这种奇怪并不是偶然的，而是权衡复杂性，经过深思熟虑做