Kĩ thuật lập trình - Chương 19: Collections

19Collections 1 I think this is the most extraordinary collection of talent, of human knowledge, that has ever been gathered together at the White House—with the possible exception of when Thomas Jefferson dined alone. John F. KennedyThe shapes a bright container can contain!Theodore RoethkeJourney over all the universe in a map. Miguel de CervantesNot by age but by capacity is wisdom acquired. Titus Maccius PlautusIt is a riddle wrapped in a mystery inside an enigma.Winston Churchill 2OBJECTIVESIn this chapter you will learn:What collections are.To use class Arrays for array manipulations.To use the collections framework (prepackaged data structure) implementations.To use collections framework algorithms to manipulate (such as search, sort and fill) collections.To use the collections framework interfaces to program with collections polymorphically.To use iterators to “walk through” a collection.To use persistent hash tables manipulated with objects of class Properties.To use synchronization and modifiability wrappers.319.1    Introduction 19.2    Collections Overview 19.3    Class Arrays 19.4    Interface Collection and Class Collections 19.5    Lists 19.5.1 ArrayList and Iterator 19.5.2   LinkedList 19.5.3   Vector 19.6   Collections Algorithms 19.6.1   Algorithm sort 19.6.2   Algorithm shuffle 19.6.3   Algorithms reverse, fill, copy, max and min 19.6.4   Algorithm binarySearch 19.6.5   Algorithms addAll, frequency and disjoint4 19.7   Stack Class of Package java.util 19.8   Class PriorityQueue and Interface Queue 19.9    Sets 19.10   Maps 19.11   Properties Class 19.12   Synchronized Collections 19.13   Unmodifiable Collections 19.14   Abstract Implementations 19.15   Wrap-Up 519.1 IntroductionJava collections frameworkContain prepackaged data structures, interfaces, algorithmsUse generics Use existing data structuresExample of code reuseProvides reusable componentry619.2 Collections OverviewCollectionData structure (object) that can hold references to other objectsCollections frameworkInterfaces declare operations for various collection typesProvide high-performance, high-quality implementations of common data structuresEnable software reuseEnhanced with generics capabilities in J2SE 5.0Compile-time type checking7Fig. 19.1 | Some collection framework interfaces. 819.3 Class ArraysClass ArraysProvides static methods for manipulating arraysProvides “high-level” methodsMethod binarySearch for searching sorted arraysMethod equals for comparing arraysMethod fill for placing values into arraysMethod sort for sorting arrays9Use static method fill of class Arrays to populate array with 7sUse static method sort of class Arrays to sort array’s elements in ascending orderUse static method arraycopy of class System to copy array intArray into array intArrayCopy10Use static method binarySearch of class Arrays to perform binary search on array11Use static method equals of class Arrays to determine whether values of the two arrays are equivalent1213Common Programming Error 19.1Passing an unsorted array to binarySearch is a logic error—the value returned is undefined. 1419.4 Interface Collection and Class CollectionsInterface CollectionRoot interface in the collection hierarchyInterfaces Set, Queue, List extend interface CollectionSet – collection does not contain duplicatesQueue – collection represents a waiting lineList – ordered collection can contain duplicate elementsContains bulk operationsAdding, clearing, comparing and retaining objectsProvide method to return an Iterator objectWalk through collection and remove elements from collection15Software Engineering Observation 19.1 Collection is used commonly as a method parameter type to allow polymorphic processing of all objects that implement interface Collection. 16Software Engineering Observation 19.2Most collection implementations provide a constructor that takes a Collection argument, thereby allowing a new collection to be constructed containing the elements of the specified collection. 1719.4 Interface Collection and Class Collections (Cont.)Class CollectionsProvides static methods that manipulate collectionsImplement algorithms for searching, sorting and so onCollections can be manipulated polymorphicallySynchronized collection Unmodifiable collection1819.5 ListsListOrdered Collection that can contain duplicate elementsSometimes called a sequenceImplemented via interface ListArrayListLinkedListVector19Performance Tip 19.1ArrayLists behave like Vectors without synchronization and therefore execute faster than Vectors because ArrayLists do not have the overhead of thread synchronization. 20Software Engineering Observation 19.3LinkedLists can be used to create stacks, queues, trees and deques (double-ended queues, pronounced “decks”). The collections framework provides implementations of some of these data structures. 2119.5.1 ArrayList and IteratorArrayList exampleDemonstrate Collection interface capabilitiesPlace two String arrays in ArrayListsUse Iterator to remove elements in ArrayList22Create ArrayList objects and assign their references to variable list and removeList, respectively23Use List method add to add objects to list and removeList, respectivelyUse List method size to get the number of ArrayList elementsUse List method get to retrieve individual element valuesMethod removeColors takes two Collections as arguments; Line 36 passes two Lists, which extends Collection, to this method24Method removeColors allows any Collections containing strings to be passed as arguments to this methodObtain Collection iterator Iterator method hasNext determines whether the Iterator contains more elementsIterator method next returns a reference to the next elementCollection method contains determines whether collection2 contains the element returned by nextUse Iterator method remove to remove String from Iterator25Common Programming Error 19.2If a collection is modified by one of its methods after an iterator is created for that collection, the iterator immediately becomes invalid—any operations performed with the iterator after this point throw ConcurrentModificationExceptions. For this reason, iterators are said to be “fail fast.” 2619.5.2 LinkedListLinkedList exampleAdd elements of one List to the otherConvert Strings to uppercaseDelete a range of elements27Create two LinkedList objectsUse List method add to append elements from array colors to the end of list128Use List method add to append elements from array colors2 to the end of list2Use List method addAll to append all elements of list2 to the end of list1Method printList allows any Lists containing strings to be passed as arguments to this method29Method convertToUppercaseStrings allows any Lists containing strings to be passed as arguments to this methodInvoke List method listIterator to get a bidirectional iterator for the ListInvoke ListIterator method hasNext to determine whether the List contains another elementInvoke ListIterator method next to obtain the next String in the ListInvoke ListIterator method set to replace the current String to which iterator refers with the String returned by method toUpperCaseMethod removeItems allows any Lists containing strings to be passed as arguments to this methodInvoke List method subList to obtain a portion of the ListMethod printReversedList allows any Lists containing strings to be passed as arguments to this methodInvoke List method listIterator with one argument that specifies the starting position to get a bidirectional iterator for the list30The while condition calls method hasPrevious to determine whether there are more elements while traversing the list backwardInvoke ListIterator method previous to get the previous element from the list3119.5.2 Linkedlist (Cont.)static method asList of class ArraysView an array as a List collectionAllow programmer to manipulate the array as if it were a listAny modification made through the List view change the arrayAny modification made to the array change the List viewOnly operation permitted on the view returned by asList is set32Call method asList to create a List view of array colors, which is then used for creating a LinkedListCall LinkedList method addLast to add “red” to the end of linksCall LinkedList method add to add “pink” as the last element and “green” as the element at index 3Call LinkedList method addFirst to add “cyan” as the new first item in the LinkedList33Use List method toArray to obtain array representation of LinkedList34Common Programming Error 19.3Passing an array that contains data to toArray can cause logic errors. If the number of elements in the array is smaller than the number of elements in the list on which toArray is called, a new array is allocated to store the list’s elements—without preserving the array argument’s elements. If the number of elements in the array is greater than the number of elements in the list, the elements of the array (starting at index zero) are overwritten with the list’s elements. Array elements that are not overwritten retain their values. 3519.5.3 VectorClass VectorArray-like data structures that can resize themselves dynamicallyContains a capacityGrows by capacity increment if it requires additional space36Performance Tip 19.2Inserting an element into a Vector whose current size is less than its capacity is a relatively fast operation. 37Performance Tip 19.3Inserting an element into a Vector that needs to grow larger to accommodate the new element is a relatively slow operation. 38Performance Tip 19.4The default capacity increment doubles the size of the Vector. This may seem a waste of storage, but it is actually an efficient way for many Vectors to grow quickly to be “about the right size.” This operation is much more efficient than growing the Vector each time by only as much space as it takes to hold a single element. The disadvantage is that the Vector might occupy more space than it requires. This is a classic example of the space–time trade-off.39Performance Tip 19.5 If storage is at a premium, use Vector method trimToSize to trim a Vector’s capacity to the Vector’s exact size. This operation optimizes a Vector’s use of storage. However, adding another element to the Vector will force the Vector to grow dynamically (again, a relatively slow operation)—trimming leaves no room for growth. 40Create Vector of type String with initial capacity of 10 element and capacity increment of zeroCall Vector method add to add objects (Strings in this example) to the end of the Vector 41Call Vector method firstElement to return a reference to the first element in the VectorCall Vector method lastElement to return a reference to the last element in the VectorVector method contains returns boolean that indicates whether Vector contains a specific ObjectVector method indexOf returns index of first location in Vector containing the argumentVector method remove removes the first occurrence of its argument Object from Vector 42Vector methods size and capacity return number of elements in Vector and Vector capacity, respectivelyMethod printVector allows any Vectors containing strings to be passed as arguments to this methodVector method isEmpty returns true if there are no elements in the Vector4344Common Programming Error 19.4Without overriding method equals, the program performs comparisons using operator == to determine whether two references refer to the same object in memory. 45Performance Tip 19.6Vector methods contains and indexOf perform linear searches of a Vector’s contents. These searches are inefficient for large Vectors. If a program frequently searches for elements in a collection, consider using one of the Java Collection API’s Map implementations (Section 19.10), which provide high-speed searching capabilities. 4619.6 Collections AlgorithmsCollections framework provides set of algorithmsImplemented as static methodsList algorithmssortbinarySearchreverseshufflefillcopy4719.6 Collections AlgorithmsCollection algorithmsminmaxaddAllfrequencydisjoint48Fig. 19.7 | Collections algorithms. 49Software Engineering Observation 19.4The collections framework algorithms are polymorphic. That is, each algorithm can operate on objects that implement specific interfaces, regardless of the underlying implementations. 5019.6.1 Algorithm sortsortSorts List elementsOrder is determined by natural order of elements’ typeList elements must implement the Comparable interfaceOr, pass a Comparator to method sortSorting in ascending orderCollections method sortSorting in descending orderCollections static method reverseOrderSorting with a ComparatorCreate a custom Comparator class51Create List of Strings52Implicit call to the list’s toString method to output the list contentsUse algorithm sort to order the elements of list in ascending order5354Method reverseOrder of class Collections returns a Comparator object that represents the collection’s reverse orderMethod sort of class Collections can use a Comparator object to sort a List 55Custom comparator TimeComparator implements Comparator interface and compares Time2 objectImplement method compare to determine the order of two Time2 objects5657Sort in order using a custom comparator TimeComparator5819.6.2 Algorithm shuffleshuffleRandomly orders List elements596061Use enum type Suit outside of class Card, qualify the enum’s type name (Suit) with the class name Card and a dot (.) separatorUse enum type Face outside of class Card, qualify the enum’s type name (Face) with the class name Card and a dot (.) separatorUse method shuffle of class Collections to shuffle List Invoke static method asList of class Arrays to get a List view of the deck array 626319.6.3 Algorithm reverse, fill, copy, max and minreverseReverses the order of List elementsfillPopulates List elements with valuescopyCreates copy of a ListmaxReturns largest element in ListminReturns smallest element in List64Use method reverse of class Collections to obtain List in reverse order65Use method copy of class Collections to obtain copy of ListUse method fill of class Collections to populate List with the letter ‘R’Obtain maximum value in ListObtain minimum value in List666719.6.4 Algorithm binarySearchbinarySearchLocates object in ListReturns index of object in List if object existsReturns negative value if Object does not existCalculate insertion pointMake the insertion point sign negativeSubtract 1 from insertion point68Sort List in ascending order69Use method binarySearch of class Collections to search list for specified key707119.6.5 Algorithms addAll, frequency and disjointaddAllInsert all elements of an array into a collectionfrequencyCalculate the number of times a specific element appear in the collectionDisjointDetermine whether two collections have elements in common7273Invoke method addAll to add elements in array colors to vectorGet the frequency of String “red” in Collection vector using method frequency74Invoke method disjoint to test whether Collections list and vector have elements in common7519.7 Stack Class of Package java.utilStackImplements stack data structureExtends class VectorStores references to objects76Create an empty Stack of type NumberStack method push adds object to top of Stack77Stack method pop removes element from top of StackStack method isEmpty returns true if Stack is empty787980Error-Prevention Tip 19.1Because Stack extends Vector, all public Vector methods can be called on Stack objects, even if the methods do not represent conventional stack operations. For example, Vector method add can be used to insert an element anywhere in a stack—an operation that could “corrupt” the stack. When manipulating a Stack, only methods push and pop should be used to add elements to and remove elements from the Stack, respectively. 8119.8 Class PriorityQueue and Interface QueueInterface QueueNew collection interface introduced in J2SE 5.0Extends interface CollectionProvides additional operations for inserting, removing and inspecting elements in a queueClass PriorityQueueImplements the Queue interfaceOrders elements by their natural orderingSpecified by Comparable elements’ compareTo methodComparator object supplied through constructor82Create a PriorityQueue that stores Doubles with an initial capacity of 11 elements and orders the elements according to the object’s natural orderingUse method offer to add elements to the priority queueUse method size to determine whether the priority queue is emptyUse method peek to retrieve the highest-priority element in the queueUse method pool to remove the highest-priority element from the queue8319.9 SetsSetCollection that contains unique elementsHashSetStores elements in hash tableTreeSetStores elements in tree84Create a List that contains String objects85Method printNonDuplicates accepts a Collection of type StringConstruct a HashSet from the Collection argument86Create TreeSet from names array87Use TreeSet method headSet to get TreeSet subset less than "orange"Use TreeSet method tailSet to get TreeSet subset greater than "orange"Methods first and last obtain smallest and largest TreeSet elements, respectively888919.10 MapsMapAssociates keys to valuesCannot contain duplicate keysCalled one-to-one mappingImplementation classesHashtable, HashMapStore elements in hash tablesTreeMapStore elements in treesInterface SortedMapExtends MapMaintains its keys in sorted order9019.10 Maps (Cont.)Map implementation with hash tablesHash tablesData structure that use hashingAlgorithm for determining a key in tableKeys in tables have associated values (data)Each table cell is a hash “bucket”Linked list of all key-value pairs that hash to that cellMinimizes collisions91Performance Tip 19.7The load factor in a hash table is a classic example of a memory-space/execution-time trade-off: By increasing the load factor, we get better memory utilization, but the program runs slower, due to increased hashing collisions. By decreasing the load factor, we get better program speed, because of reduced hashing collisions, but we get poorer memory utilization, because a larger portion of the hash table remains empty. 92Create an empty HashMap with a default capacity 16 and a default load factor 0.75. The keys are of type String and the values are of type Integer93Map method containsKey determines whether the key specified as an argument is in the hash tableCreate a StringTokenizer to break the input string argument into its component individual wordsUse method get to obtain the key’s associated value in the mapUse StringTokenizer method hasMoreTokens to determine whether there are more tokens in the stringUse StringTokenizer method nextToken to obtain the next tokenIncrement the value and use method put to replace the key’s associated valueCreate a new entry in the map, with the word as the key and an Integer object containing 1 as the value94Use HashMap method keySet to obtain a set of the keysAccess each key and its value in the mapCall Map method size to get the number of key-value pairs in the MapCall Map method isEmpty to determine whether the Map is empty959619.11 Properties ClassPropertiesPersistent HashtableCan be written to output streamCan be read from input streamProvides methods setProperty and getPropertyStore/obtain key-value pairs of StringsPreferences APIReplace PropertiesMore robust mechanism97Create empty PropertiesProperties method setProperty stores value for the specified key98Use Properties method clear to empty the hash tableUse Properties method getProperty to locate the value associated with the specified key99Properties method store saves Properties contents to FileOutputStream100Properties method load restores Properties contents from FileInputStreamUse Properties method keySet to obtain a Set of the property namesObtain the value of a property by passing a key to method getProperty10110219.12 Synchronized CollectionsBuilt-in collections are unsynchronizedConcurrent access to a Collection can cause errorsJava provides synchronization wrappers to avoid thisVia set of public static methods103Fig. 19.22 | Synchronization wrapper methods. 10419.13 Unmodifiable CollectionsUnmodifiable wrapperConverting collections to unmodifiable collectionsThrow UnsorrtedOperationException if attempts are made to modify the collection105Software Engineering Observation 19.5You can use an unmodifiable wrapper to create a collection that offers read-only access to others, while allowing read–write access to yourself. You do this simply by giving others a reference to the unmodifiable wrapper while retaining for yourself a reference to the original collection. 106Fig. 19.23 | Unmodifiable wrapper methods. 10719.14 Abstract ImplementationsAbstract implementationsOffer “bare bones” implementation of collection interfacesProgrammers can “flesh out” customizable implementationsAbstractCollectionAbstractListAbstractMapAbstractSequentialListAbstractSetAbstractQueue108