Microsoft PowerPoint - ch22

Transcription

1 Chapter 22 Collections 林偉川 1 Introduction Java collections framework Provides reusable componentry Common data structures Example of code reuse Collection Data structure (object) that can hold references to other objects Collections framework Interfaces declare operations for various collection types Belong to package java.util Collection Map Set List 2 1

2 請注意 Collections 具體類別的相關特性 : 類別實作的介面 類別使用的資料結構 元素可否重複 無序或有序 ( 加入的先後順序, 或有排序功能 ) 是否為執行緒同步 (Thread safe class) 有哪些常見的應用 3 Collections Framework 內的介面架構 <<interface>> Collection <<interface>> Map <<interface>> Set <<interface>> List <<interface>> SortedMap <<interface>> SortedSet 4 2

3 實作 Collections 延伸介面的具體類別 <<interface>> Collection <<interface>> List <<interface>> Set Vector ArrayList LinkedList HashSet <<interface>> SortedSet Stack LinkedHashSet TreeSet 5 Collection 介面 Collection 介面定義的集合, 其元素可以為無順序 (non-ordered) 和可重複 (repetition allowed) Collection 兩個延伸介面 List 和 Set, 分別保有 Collection 的不同特性 Set 的特點為, 其元素不可重複 SortedSet 介面繼承 Set 介面, 且宣告了排序的方法 List 介面繼承 Collection 介面, 然而它是有順序的, 而且是可以重複的 6 3

4 Map 介面 Map 介面和 Collection 介面沒有繼承的關係 Map 介面的元素是 鍵值對 (key-value pairs) Map 中的 key 和 value 皆為參照變數, 而且 key 不能重複, 一個 key 對應到一個 value Map 中的元素是沒有順序的 SortedMap 介面為 Map 的子介面, 故名思義, 其為可排序的集合 7 Collection 中所使用的基本資料結構 陣列 (array) 鏈結串列 (linked list) 樹 (tree) 雜湊表 (hash table) 8 4

5 陣列的重要特性 : 存取元素的速度快 要在某位置插入或移除元素值時, 並不方便 陣列長度為固定, 欲改變長度必須重新建立另一個陣列 9 Class Arrays Class Arrays Provides static methods for manipulating arrays Provides high-level methods Method binarysearch for searching sorted arrays Method equals for comparing arrays Method fill for placing values into arrays Method sort for sorting arrays 10 5

6 Arrays Arrays 的靜態方法 List aslist(object[] a) int binarysearch(int[] a, int key) boolean equals(int[] a, int[] 比較兩陣列 a 和 a2, 若兩陣列中的元素值皆相等 a2) 則回傳 true 此方法有許多因應不同型別陣列的多載方法 void fill(int[] a, int val) void sort(int[] a) 說明 將 Object 陣列 a 轉換成 List 物件, 然後回傳 在已排序的 a 陣列中以二次搜尋法, 找出 key 的索引值 若找不到 key 則回傳 1 此方法有許多因應不同型別陣列的多載方法 將 a 陣列中的所有的元素值設定為 val 此方法有許多因應不同型別陣列的多載方法 對陣列 a 排序 此方法有許多因應不同參數的多載方法 11 鏈結串列 可以鏈結的類別 class LinkedObj{ Object data; LinkedObj next; } // 節點資料 // 下一個節點 鏈結串列的重要特性 : 插入或刪除節點很方便 變更鏈結串列的長度也很方便 存取節點的速度較慢 12 6

7 Collections Collections 中的靜態方法大都針對 List, 因為 List 不像 Set 和 Map 有可排序的類別 Collections 另外提供將 非執行緒同步 集合包裹成 執行緒同步 集合的方法, 這些方法在多執行緒程式裡會顯得相當方便 13 Collections 的常用靜態方法 int binarysearch(list list, Object key) void copy(list dest, List src) boolean replaceall(list list, Object oldval, Object newval) void reverse(list list) void shuffle(list list) void sort(list list) List synchronizedlist(list list) Map synchronizedmap(map m) Set synchronizedset(set s) SortedMap synchronizedsortedmap(sortedmap m) 說明 以二次搜尋法, 找出 key 的索引值 將 src 序列的所元素複製給 dest 序列 將 list 序列中的 oldval 換成 newval 物件 若 oldval 不包含在 list 內則回傳 false 將 list 序列的順序顛倒 亂數重排 list 序列中元素的順序 對 list 序列排序 取得一執行緒同步的集合 SortedSet synchronizedsortedset(sortedset s) 14 7

8 樹 實體可以做為二元樹的節點的類別 class TreeNode{ Object data; TreeNode left; TreeNode right; } 樹的優點是有 排序 的功能, 缺點和鏈結串列一樣, 節點資料的存取都比較慢 15 雜湊表雜湊表 (hash table) 的資料是以 鍵值對 (key value paired) 的形式存在 加入一個元素時必須同時給予一個 key 和一個 value, 透過 key 就可以取得 value 雜湊表的特點 : 存取資料的速度快 較浪費記憶體空間 16 8

9 是否相等 Object.equals() 的定義如下 : public boolean equals(object obj){ return (this == obj); } 當兩個物件 obj1 和 obj2 使用 equals() 比較後認定為相等時, 他們由 hashcode() 方法所取得的雜湊碼也必須相同 所以當兩物件相等時, 以下兩個運算式的結果都必須為 true obj1.equals(obj2)== obj2.equals(obj1)== true obj1.hashcode()== obj2.hashcode() 17 是否相等 hashcode() 方法在使用 hash table 的集合中顯得相當重要, 因為 hash table 是以 key.hashcode() 取得的 hash code value 當你覆蓋 equals() 方法時, 也必須覆蓋 hashcode() 方法, 讓兩者的行為一致 18 9

10 是否相等 Integer 類別中定義的 equals() public boolean equals(object obj){ if(obj instanceof Integer){ return value == ((Integer)obj).intValue(); } return false; } Integer 類別中定義的 hashcode() public int hashcode(){ return value; } 19 String 類別的 equals() 方法 public boolean equals(object anobject){ if (this == anobject){ return true; // 參照相同 } if (anobject instanceof String){ String anotherstring = (String)anObject; int n = count; // 字串長度 if (n == anotherstring.count){ char v1[] = value; // 字元陣列 char v2[] = anotherstring.value; int i = offset; // 第一字元的位置 int j = anotherstring.offset; while (n--!= 0){ if (v1[i++]!= v2[j++]) return false; // 有任何字元不同 } return true; // 所有字元都相同 } } return false; // 不是 String 型別 } 20 10

11 是否相等 String 類別的 hashcode() 方法 public int hashcode(){ int h = hash; if(h == 0){ int off = offset; char val[] = value; int len = count; } for (int i = 0; i < len; i++){ // 計算雜湊碼的規則 h = 31*h + val[off++]; } hash = h; } return h; // 取得字串的雜湊碼 // 若雜湊碼為 0 表示倘未計算 // 第一個字元的位置 // 取得字元陣列 // 字串的長度 s[0]*31^(n-1)+ s[1]*31^(n-2) s[n-1] 21 是否相等自訂類別的 equals() 和 hashcode() 定義 equals() 時, 可以一一比對各個屬性是否相等 屬性大多為現成的類別或基本資料型別, 因此, 就可以使用現成的類別的 equals() 方法 定義 hashcode() 時, 只要將屬性的雜湊碼相互做位元互斥 (XOR,^) 運算即可 22 11

12 較大或較小 TreeSet 和 TreeMap 都有自動排序的功能, 既然要能排序必定有比較大小的規則 使用 tree 實作的 collection, 其元素必須是相同型別的物件, 而且必須實作 Comparable 介面 String 類別和基本型別的包裝器 (Boolean 除外 ) 實作了 Comparable 介面 23 較大或較小 Comparable 介面只宣告一個抽象方法 compareto() int compareto(object o); 實作 compareto() 方法必須遵守不同型別的物件不能比較若物件本身比傳入的物件小時, 則回傳負值 若物件本身比傳入的物件大時, 則回傳正值 若不大也不小時, 回傳

13 1 // Fig. 22.1: UsingArrays.java 2 // Using Java arrays. 3 import java.util.*; 4 5 public class UsingArrays { 6 private int intvalues[] = { 1, 2, 3, 4, 5, 6 }; 7 private double doublevalues[] = { 8.4, 9.3, 0.2, 7.9, 3.4 }; 8 private int filledint[], intvaluescopy[]; 9 10 // initialize arrays 11 public UsingArrays() 12 { 13 filledint = new int[ 10 ]; 14 intvaluescopy = new int[ intvalues.length ]; Arrays.fill( filledint, 7 ); // fill with 7s Arrays.sort( doublevalues ); // sort doublevalues ascending // copy array intvalues into array intvaluescopy 21 System.arraycopy( intvalues, 0, intvaluescopy, 22 0, intvalues.length ); 23 } 24 UsingArrays.java Line 16 Line 18 Lines // output values in each array 26 public void printarrays() 27 { 28 System.out.print( "doublevalues: " ); for ( int count = 0; count < doublevalues.length; count++ ) 31 System.out.print( doublevalues[ count ] + " " ); System.out.print( "\nintvalues: " ); for ( int count = 0; count < intvalues.length; count++ ) 36 System.out.print( intvalues[ count ] + " " ); System.out.print( "\nfilledint: " ); for ( int count = 0; count < filledint.length; count++ ) 41 System.out.print( filledint[ count ] + " " ); System.out.print( "\nintvaluescopy: " ); for ( int count = 0; count < intvaluescopy.length; count++ ) 46 System.out.print( intvaluescopy[ count ] + " " ); System.out.println(); } // end method printarrays 51 UsingArrays.java 13

14 52 // find value in array intvalues 53 public int searchforint( int value ) 54 { 55 return Arrays.binarySearch( intvalues, value ); 56 } // compare array contents 59 public void printequality() 60 { 61 boolean b = Arrays.equals( intvalues, intvaluescopy ); System.out.println( "intvalues " + ( b? "==" : "!=" ) + 64 " intvaluescopy" ); b = Arrays.equals( intvalues, filledint ); System.out.println( "intvalues " + ( b? "==" : "!=" ) + 69 " filledint" ); 70 } 71 UsingArrays.java Line 55 Lines 61 and public static void main( String args[] ) 73 { 74 UsingArrays usingarrays = new UsingArrays(); usingarrays.printarrays(); 77 usingarrays.printequality(); int location = usingarrays.searchforint( 5 ); 80 System.out.println( ( location >= 0? "Found 5 at element " + 81 location : "5 not found" ) + " in intvalues" ); location = usingarrays.searchforint( 8763 ); 84 System.out.println( ( location >= 0? "Found 8763 at element " + 85 location : "8763 not found" ) + " in intvalues" ); 86 } } // end class UsingArrays UsingArrays.java doublevalues: intvalues: filledint: intvaluescopy: intvalues == intvaluescopy intvalues!= filledint Found 5 at element 4 in intvalues 8763 not found in intvalues 14

15 1 // Fig. 22.2: UsingAsList.java 2 // Using method aslist. 3 import java.util.*; 4 5 public class UsingAsList { 6 private static final String values[] = { "red", "white", "blue" }; 7 private List list; 8 9 // initialize List and set value at location 1 10 public UsingAsList() 11 { 12 list = Arrays.asList( values ); // get List 13 list.set( 1, "green" ); // change a value 14 } // output List and array 17 public void printelements() 18 { 19 System.out.print( "List elements : " ); for ( int count = 0; count < list.size(); count++ ) 22 System.out.print( list.get( count ) + " " ); System.out.print( "\narray elements: " ); 25 UsingAsList.java Line 12 Line 13 Line 21 Line for ( int count = 0; count < values.length; count++ ) 27 System.out.print( values[ count ] + " " ); System.out.println(); 30 } public static void main( String args[] ) 33 { 34 new UsingAsList().printElements(); 35 } } // end class UsingAsList UsingAsList.java List elements : red green blue Array elements: red green blue 15

16 Interface Collection and Class Collections Interface Collection Contains bulk operations Adding, clearing, comparing and retaining objects Interfaces Set and List extend interface Collection Class Collections Provides static methods that manipulate collections Collections can be manipulated polymorphically 31 Lists List Ordered Collection that can contain duplicate elements Sometimes called a sequence Implemented via interface List ArrayList LinkedList Vector 32 16

17 1 // Fig. 22.3: CollectionTest.java 2 // Using the Collection interface. 3 import java.awt.color; 4 import java.util.*; 5 6 public class CollectionTest { 7 private static final String colors[] = { "red", "white", "blue" }; 8 9 // create ArrayList, add objects to it and manipulate it 10 public CollectionTest() 11 { 12 List list = new ArrayList(); // add objects to list 15 list.add( Color.MAGENTA ); // add a color object for ( int count = 0; count < colors.length; count++ ) 18 list.add( colors[ count ] ); list.add( Color.CYAN ); // add a color object // output list contents 23 System.out.println( "\narraylist: " ); for ( int count = 0; count < list.size(); count++ ) 26 System.out.print( list.get( count ) + " " ); 27 CollectionTest.java Lines Line // remove all String objects 29 removestrings( list ); // output list contents 32 System.out.println( "\n\narraylist after calling removestrings: " ); for ( int count = 0; count < list.size(); count++ ) 35 System.out.print( list.get( count ) + " " ); } // end constructor CollectionTest // remove String objects from Collection 40 private void removestrings( Collection collection ) 41 { 42 Iterator iterator = collection.iterator(); // get iterator // loop while collection has items 45 while ( iterator.hasnext() ) if ( iterator.next() instanceof String ) 48 iterator.remove(); // remove String object 49 } 50 CollectionTest.java Line 29 Line 42 Line 45 Line 47 Line 48 17

18 51 public static void main( String args[] ) 52 { 53 new CollectionTest(); 54 } } // end class CollectionTest CollectionTest.java ArrayList: java.awt.color[r=255,g=0,b=255] red white blue java.awt.color [r=0,g=255,b=255] ArrayList after calling removestrings: java.awt.color[r=255,g=0,b=255] java.awt.color[r=0,g=255,b=255] 1 // Fig. 22.4: ListTest.java 2 // Using LinkLists. 3 import java.util.*; 4 5 public class ListTest { 6 private static final String colors[] = { "black", "yellow", 7 "green", "blue", "violet", "silver" }; 8 private static final String colors2[] = { "gold", "white", 9 "brown", "blue", "gray", "silver" }; // set up and manipulate LinkedList objects 12 public ListTest() 13 { 14 List link = new LinkedList(); 15 List link2 = new LinkedList(); // add elements to each list 18 for ( int count = 0; count < colors.length; count++ ) { 19 link.add( colors[ count ] ); 20 link2.add( colors2[ count ] ); 21 } link.addall( link2 ); // concatenate lists 24 link2 = null; // release resources 25 ListTest.java Lines Line 23 Line 24 18

19 26 printlist( link ); uppercasestrings( link ); printlist( link ); System.out.print( "\ndeleting elements 4 to 6..." ); 33 removeitems( link, 4, 7 ); printlist( link ); printreversedlist( link ); } // end constructor ListTest // output List contents 42 public void printlist( List list ) 43 { 44 System.out.println( "\nlist: " ); for ( int count = 0; count < list.size(); count++ ) 47 System.out.print( list.get( count ) + " " ); System.out.println(); 50 } ListTest.java Lines // locate String objects and convert to uppercase 53 private void uppercasestrings( List list ) 54 { 55 ListIterator iterator = list.listiterator(); while ( iterator.hasnext() ) { 58 Object object = iterator.next(); // get item if ( object instanceof String ) // check for String 61 iterator.set( ( ( String ) object ).touppercase() ); 62 } 63 } // obtain sublist and use clear method to delete sublist items 66 private void removeitems( List list, int start, int end ) 67 { 68 list.sublist( start, end ).clear(); // remove items 69 } // print reversed list 72 private void printreversedlist( List list ) 73 { 74 ListIterator iterator = list.listiterator( list.size() ); 75 ListTest.java Lines Line 68 19

20 76 System.out.println( "\nreversed List:" ); // print list in reverse order 79 while( iterator.hasprevious() ) 80 System.out.print( iterator.previous() + " " ); 81 } public static void main( String args[] ) 84 { 85 new ListTest(); 86 } } // end class ListTest ListTest.java Line 79 Line 80 list: black yellow green blue violet silver gold white brown blue gray silver list: BLACK YELLOW GREEN BLUE VIOLET SILVER GOLD WHITE BROWN BLUE GRAY SILVER Deleting elements 4 to 6... list: BLACK YELLOW GREEN BLUE WHITE BROWN BLUE GRAY SILVER Reversed List: SILVER GRAY BLUE BROWN WHITE BLUE GREEN YELLOW BLACK 1 // Fig. 22.5: UsingToArray.java 2 // Using method toarray. 3 import java.util.*; 4 5 public class UsingToArray { 6 7 // create LinkedList, add elements and convert to array 8 public UsingToArray() 9 { 10 String colors[] = { "black", "blue", "yellow" }; LinkedList links = new LinkedList( Arrays.asList( colors ) ); links.addlast( "red" ); // add as last item 15 links.add( "pink" ); // add to the end 16 links.add( 3, "green" ); // add at 3rd index 17 links.addfirst( "cyan" ); // add as first item // get LinkedList elements as an array 20 colors = ( String [] ) links.toarray( new String[ links.size() ] ); System.out.println( "colors: " ); 23 UsingToArray.java Line 20 20

21 24 for ( int count = 0; count < colors.length; count++ ) 25 System.out.println( colors[ count ] ); 26 } public static void main( String args[] ) 29 { 30 new UsingToArray(); 31 } } // end class UsingToArray UsingToArray.java colors: cyan black blue yellow green red pink 請注意 Collection 具體類別的相關特性 : 類別實作的介面 類別使用的資料結構 元素可否重複 無序或有序 ( 加入的先後順序, 或有排序功能 ) 是否為執行緒同步 (Thread safe class) 有哪些常見的應用 42 21

22 實作 Collection 延伸介面的具體類別 <<interface>> Collection <<interface>> List <<interface>> Set Vector ArrayList LinkedList HashSet <<interface>> SortedSet Stack LinkedHashSet TreeSet 43 實作 List 介面的具體類別 ArrayList 使用 array 資料結構實作 List 保有陣列的特性, 存取元素的效率佳, 但不利於插入或移除元素, 且重定陣列長度效率差 LinkedList 使用 linked list 實作 List 保有 linked list 的特性, 存取元素的效率較差, 但利於插入元素 移除元素和改變長度 Vector 和 ArrayList 很像, 都是以 array 實作 List 兩者最大的不同是在於 :Vector 為 執行緒同步類別, 而 ArrayList 則否 44 22

23 實作 List 介面的具體類別 Stack 為 Vector 的延伸類別, 所以同樣為有序 執行緒同步類別 Stack 類別是堆疊的抽象資料型別 (Abstract Data Type) 推入 A 推入 B 推入 C 彈出 C C B B B A A A A 45 Algorithms Collections Framework provides set of algorithms Implemented as static methods List algorithms sort binarysearch reverse shuffle fill copy Collection algorithms min max 46 23

24 Algorithm sort sort Sorts List elements Order is determined by natural order of elements type Relatively fast 47 3 import java.util.*; 4 5 public class Sort1 { 6 private static final String suits[] = 7 { "Hearts", "Diamonds", "Clubs", "Spades" }; 8 9 // display array elements 10 public void printelements() 11 { 12 // create ArrayList 13 List list = new ArrayList( Arrays.asList( suits ) ); // output list 16 System.out.println( "Unsorted array elements:\n" + list ); Collections.sort( list ); // sort ArrayList // output list 21 System.out.println( "Sorted array elements:\n" + list ); 22 } public static void main( String args[] ) 25 { 26 new Sort1().printElements(); 27 } 28 } // end class Sort1 Unsorted array elements: [Hearts, Diamonds, Clubs, Spades] Sorted array elements: [Clubs, Diamonds, Hearts, Spades] Sort1.java Line 13 Line 18 24

25 1 // Fig. 22.7: Sort2.java 2 // Using a Comparator object with algorithm sort. 3 import java.util.*; 4 5 public class Sort2 { 6 private static final String suits[] = 7 { "Hearts", "Diamonds", "Clubs", "Spades" }; 8 9 // output List elements 10 public void printelements() 11 { 12 List list = Arrays.asList( suits ); // create List // output List elements 15 System.out.println( "Unsorted array elements:\n" + list ); // sort in descending order using a comparator 18 Collections.sort( list, Collections.reverseOrder() ); // output List elements 21 System.out.println( "Sorted list elements:\n" + list ); 22 } 23 public static void main( String args[] ) { new Sort2().printElements(); } 24 } // end class Sort2 Unsorted array elements: [Hearts, Diamonds, Clubs, Spades] Sorted list elements: [Spades, Hearts, Diamonds, Clubs] Sort2.java Line 18 Line 18 1 // Fig. 22.8: Sort3.java 2 // Creating a custom Comparator class. 3 import java.util.*; 4 5 public class Sort3 { 6 7 public void printelements() 8 { 9 List list = new ArrayList(); // create List list.add( new Time2( 6, 24, 34 ) ); 12 list.add( new Time2( 18, 14, 05 ) ); 13 list.add( new Time2( 8, 05, 00 ) ); 14 list.add( new Time2( 12, 07, 58 ) ); 15 list.add( new Time2( 6, 14, 22 ) ); // output List elements 18 System.out.println( "Unsorted array elements:\n" + list ); // sort in order using a comparator 21 Collections.sort( list, new TimeComparator() ); // output List elements 24 System.out.println( "Sorted list elements:\n" + list ); 25 } 26 Sort3.java Line 21 25

26 27 public static void main( String args[] ) 28 { 29 new Sort2().printElements(); 30 } private class TimeComparator implements Comparator { 33 int hourcompare, minutecompare, secondcompare; 34 Time2 time1, time2; public int compare(object object1, Object object2) 37 { 38 // cast the objects 39 time1 = (Time2)object1; 40 time2 = (Time2)object2; hourcompare = new Integer( time1.gethour() ).compareto( 43 new Integer( time2.gethour() ) ); // test the hour first 46 if ( hourcompare!= 0 ) 47 return hourcompare; minutecompare = new Integer( time1.getminute() ).compareto( 50 new Integer( time2.getminute() ) ); 51 Sort3.java Line 32 Line // then test the minute 53 if ( minutecompare!= 0 ) 54 return minutecompare; secondcompare = new Integer( time1.getsecond() ).compareto( 57 new Integer( time2.getsecond() ) ); return secondcompare; // return result of comparing seconds 60 } } // end class TimeComparator } // end class Sort3 Sort3.java Unsorted array elements: [06:24:34, 18:14:05, 08:05:00, 12:07:58, 06:14:22] Sorted list elements: [06:14:22, 06:24:34, 08:05:00, 12:07:58, 18:14:05] 26

27 shuffle Algorithm shuffle Randomly orders List elements 53 1 // Fig. 22.9: Cards.java 2 // Using algorithm shuffle. 3 import java.util.*; 4 5 // class to represent a Card in a deck of cards 6 class Card { 7 private String face; 8 private String suit; 9 10 // initialize a Card 11 public Card( String initialface, String initialsuit ) 12 { 13 face = initialface; 14 suit = initialsuit; 15 } // return face of Card 18 public String getface() 19 { 20 return face; 21 } // return suit of Card 24 public String getsuit() 25 { 26 return suit; 27 } Cards.java 27

28 28 29 // return String representation of Card 30 public String tostring() 31 { 32 StringBuffer buffer = new StringBuffer( face + " of " + suit ); 33 buffer.setlength( 20 ); return buffer.tostring(); 36 } } // end class Card // class Cards declaration 41 public class Cards { 42 private static final String suits[] = 43 { "Hearts", "Clubs", "Diamonds", "Spades" }; 44 private static final String faces[] = { "Ace", "Deuce", "Three", 45 "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 46 "Jack", "Queen", "King" }; 47 private List list; // set up deck of Cards and shuffle 50 public Cards() 51 { 52 Card deck[] = new Card[ 52 ]; 53 Cards.java 54 for ( int count = 0; count < deck.length; count++ ) 55 deck[ count ] = new Card( faces[ count % 13 ], 56 suits[ count / 13 ] ); list = Arrays.asList( deck ); // get List 59 Collections.shuffle( list ); // shuffle deck 60 } // output deck 63 public void printcards() 64 { 65 int half = list.size() / 2-1; for ( int i = 0, j = half + 1; i <= half; i++, j++ ) 68 System.out.println( list.get( i ).tostring() + list.get( j ) ); 69 } public static void main( String args[] ) 72 { 73 new Cards().printCards(); 74 } } // end class Cards Cards.java Line 59 28

29 King of Diamonds Jack of Spades Four of Diamonds Six of Clubs King of Hearts Nine of Diamonds Three of Spades Four of Spades Four of Hearts Seven of Spades Five of Diamonds Eight of Hearts Queen of Diamonds Five of Hearts Seven of Diamonds Seven of Hearts Nine of Hearts Three of Clubs Ten of Spades Deuce of Hearts Three of Hearts Ace of Spades Six of Hearts Eight of Diamonds Six of Diamonds Deuce of Clubs Ace of Clubs Ten of Diamonds Eight of Clubs Queen of Hearts Jack of Clubs Ten of Clubs Seven of Clubs Queen of Spades Five of Clubs Six of Spades Nine of Spades Nine of Clubs King of Spades Ace of Diamonds Ten of Hearts Ace of Hearts Queen of Clubs Deuce of Spades Three of Diamonds King of Clubs Four of Clubs Jack of Diamonds Eight of Spades Five of Spades Jack of Hearts Deuce of Diamonds Cards.java Algorithms reverse, fill, copy, max and min reverse fill Reverses the order of List elements Populates List elements with values copy Creates copy of a List max min Returns largest element in List Returns smallest element in List 58 29

30 1 // Fig : Algorithms1.java 2 // Using algorithms reverse, fill, copy, min and max. 3 import java.util.*; 4 5 public class Algorithms1 { 6 private String letters[] = { "P", "C", "M" }, letterscopy[]; 7 private List list, copylist; 8 9 // create a List and manipulate it with methods from Collections 10 public Algorithms1() 11 { 12 list = Arrays.asList( letters ); // get List 13 letterscopy = new String[ 3 ]; 14 copylist = Arrays.asList( letterscopy ); System.out.println( "Initial list: " ); 17 output( list ); Collections.reverse( list ); // reverse order 20 System.out.println( "\nafter calling reverse: " ); 21 output( list ); Collections.copy( copylist, list ); // copy List 24 System.out.println( "\nafter copying: " ); 25 output( copylist ); 26 Algorithms1.java Line 19 Line Collections.fill( list, "R" ); // fill list with Rs 28 System.out.println( "\nafter calling fill: " ); 29 output( list ); } // end constructor // output List information 34 private void output( List listref ) 35 { 36 System.out.print( "The list is: " ); for ( int k = 0; k < listref.size(); k++ ) 39 System.out.print( listref.get( k ) + " " ); System.out.print( "\nmax: " + Collections.max( listref ) ); 42 System.out.println( " Min: " + Collections.min( listref ) ); 43 } public static void main( String args[] ) 46 { 47 new Algorithms1(); 48 } } // end class Algorithms1 Initial list: The list is: P C M Max: P Min: C After calling reverse: The list is: M C P Max: P Min: C After copying: The list is: M C P Max: P Min: C After calling fill: The list is: R R R Max: R Min: R Algorithms1.java Line 27 Line 41 Line 42 30

31 binarysearch Algorithm binarysearch Locates Object in List Returns index of Object in List if Object exists Returns negative value if Object does not exist 61 1 // Fig : BinarySearchTest.java 2 // Using algorithm binarysearch. 3 import java.util.*; 4 5 public class BinarySearchTest { 6 private static final String colors[] = { "red", "white", 7 "blue", "black", "yellow", "purple", "tan", "pink" }; 8 private List list; // List reference 9 10 // create, sort and output list 11 public BinarySearchTest() 12 { 13 list = new ArrayList( Arrays.asList( colors ) ); 14 Collections.sort( list ); // sort the ArrayList 15 System.out.println( "Sorted ArrayList: " + list ); 16 } // search list for various values 19 private void printsearchresults() 20 { 21 printsearchresultshelper( colors[ 3 ] ); // first item 22 printsearchresultshelper( colors[ 0 ] ); // middle item 23 printsearchresultshelper( colors[ 7 ] ); // last item 24 printsearchresultshelper( "aardvark" ); // below lowest 25 printsearchresultshelper( "goat" ); // does not exist 26 printsearchresultshelper( "zebra" ); // does not exist 27 } 28 BinarySearchTest.java Line 14 31

32 29 // helper method to perform searches 30 private void printsearchresultshelper( String key ) 31 { 32 int result = 0; System.out.println( "\nsearching for: " + key ); 35 result = Collections.binarySearch( list, key ); 36 System.out.println( ( result >= 0? "Found at index " + result : 37 "Not Found (" + result + ")" ) ); 38 } public static void main( String args[] ) 41 { 42 new BinarySearchTest().printSearchResults(); 43 } } // end class BinarySearchTest BinarySearchTest.java Line 35 Sorted ArrayList: black blue pink purple red tan white yellow Searching for: black Found at index 0 Searching for: red Found at index 4 Searching for: pink Found at index 2 Searching for: aardvark Not Found (-1) Searching for: goat Not Found (-3) Searching for: zebra Not Found (-9) Set Sets Collection that contains unique elements HashSet Stores elements in hash table TreeSet Stores elements in tree 64 32

33 實作 Collection 延伸介面的具體類別 <<interface>> Collection <<interface>> List <<interface>> Set Vector ArrayList LinkedList HashSet <<interface>> SortedSet Stack LinkedHashSet TreeSet 65 實作 Set 介面的具體類別 HashSet 使用 hash table 實作 Set 元素沒有順序, 而且元素不可重複存在 HashSet 物件內 其 key 和 value 是使用相同的物件, 也就是被加入的物件 LinkedHashSet 除了使用 hash table, 還使用 linked list 實作 Set, 使之成為有序集合 元素的順序是依照加入的順序 TreeSet 使用 tree 實作 SortedSet, 所以元素在加入集合時, 就會和既有的元素 比較, 以排放在適當的位置 66 33

34 1 // Fig : SetTest.java 2 // Using a HashSet to remove duplicates. 3 import java.util.*; 4 5 public class SetTest { 6 private static final String colors[] = { "red", "white", "blue", 7 "green", "gray", "orange", "tan", "white", "cyan", 8 "peach", "gray", "orange" }; 9 10 // create and output ArrayList 11 public SetTest() 12 { 13 List list = new ArrayList( Arrays.asList( colors ) ); 14 System.out.println( "ArrayList: " + list ); 15 printnonduplicates( list ); 16 } // create set from array to eliminate duplicates 19 private void printnonduplicates( Collection collection ) 20 { 21 // create a HashSet and obtain its iterator 22 Set set = new HashSet( collection ); 23 Iterator iterator = set.iterator(); System.out.println( "\nnonduplicates are: " ); 26 SetTest.java Line while ( iterator.hasnext() ) 28 System.out.print( iterator.next() + " " ); System.out.println(); 31 } public static void main( String args[] ) 34 { 35 new SetTest(); 36 } } // end class SetTest SetTest.java Lines ArrayList: [red, white, blue, green, gray, orange, tan, white, cyan, peach, gray, orange] Nonduplicates are: red cyan white tan gray green orange blue peach 34

35 1 // Fig : SortedSetTest.java 2 // Using TreeSet and SortedSet. 3 import java.util.*; 4 5 public class SortedSetTest { 6 private static final String names[] = { "yellow", "green", 7 "black", "tan", "grey", "white", "orange", "red", "green" }; 8 9 // create a sorted set with TreeSet, then manipulate it 10 public SortedSetTest() 11 { 12 SortedSet tree = new TreeSet( Arrays.asList( names ) ); System.out.println( "set: " ); 15 printset( tree ); // get headset based upon "orange" 18 System.out.print( "\nheadset (\"orange\"): " ); 19 printset( tree.headset( "orange" ) ); // get tailset based upon "orange" 22 System.out.print( "tailset (\"orange\"): " ); 23 printset( tree.tailset( "orange" ) ); // get first and last elements 26 System.out.println( "first: " + tree.first() ); 27 System.out.println( "last : " + tree.last() ); 28 } 29 SortedSetTest.java Line 12 Line 19 Line 23 Lines // output set 31 private void printset( SortedSet set ) 32 { 33 Iterator iterator = set.iterator(); while ( iterator.hasnext() ) 36 System.out.print( iterator.next() + " " ); System.out.println(); 39 } public static void main( String args[] ) 42 { 43 new SortedSetTest(); 44 } } // end class SortedSetTest SortedSetTest.java Lines set: black green grey orange red tan white yellow headset ("orange"): black green grey tailset ("orange"): orange red tan white yellow first: black last : yellow 35

36 Map Maps Associates keys to values Cannot contain duplicate keys Called one-to-one mapping 71 實作 Map 介面的具體類別 <<interface>> Map Hashtable HashMap <<interface>> SortedMap Properties LinkedHashMap TreeMap 72 36

37 實作 Map 介面的具體類別 HashMap 使用 hash table 實作 Map, 此集合中 keyvalue pairs 順序和放入的順序無關, 而且 key 無法重複 LinkedHashMap 使用 hash table 和 linked list 實作 Map, 此集合中 key-value pairs 順序就是放入的順序, 而 key 同樣無法重複 TreeMap 使用 tree 實作 Map, 此集合中 key-value pairs 順序是依照 key 在集合中的排序而定, 而 key 同樣無法重複 73 實作 Map 介面的具體類別 Hashtable 和 HashMap 的功能差不多, 不同處在於 Hashtable 為 執行緒同步 Properties 為 Hashtable 的延伸類別 Properties 的 key 和 value 應該為 String 型別, 而且使用 setproperty() 和 getproperty() 取代 put() 和 get() 74 37

38 具體類別的整體比較 具體類別 ArrayList LinkedList Vector Stack HashSet LinkedHashSet TreeSet HashMap LinkedHashMap TreeMap Hashtable Properties 直接實作介面 List List List List Set Set SortedSet Map Map SortedMap Map Map 資料結構 array linked list array array hash table hash table linked list tree hash table hash table linked list tree hash table hash table 元素重複性可可可可不可不可不可 key 不可 key 不可 key 不可 key 不可 key 不可 元素順序依加入順序依加入順序依加入順序依加入順序無關加入順序依加入順序排序無關加入順序依加入順序依 key 排序無關加入順序無關加入順序 執行緒同步否否是 * 是 * 否否否否否否是 * 是 * 75 1 // Fig : WordTypeCount.java 2 // Program counts the number of occurrences of each word in a string 3 import java.awt.*; 4 import java.awt.event.*; 5 import java.util.*; 6 import javax.swing.*; 7 8 public class WordTypeCount extends JFrame { 9 private JTextArea inputfield; 10 private JLabel prompt; 11 private JTextArea display; 12 private JButton gobutton; private Map map; public WordTypeCount() 17 { 18 super( "Word Type Count" ); 19 inputfield = new JTextArea( 3, 20 ); map = new HashMap(); gobutton = new JButton( "Go" ); 24 gobutton.addactionlistener( 25 MapTest.java Line 21 38

39 26 new ActionListener() { // inner class public void actionperformed( ActionEvent event ) 29 { 30 createmap(); 31 display.settext( createoutput() ); 32 } } // end inner class ); // end call to addactionlistener prompt = new JLabel( "Enter a string:" ); 39 display = new JTextArea( 15, 20 ); 40 display.seteditable( false ); JScrollPane displayscrollpane = new JScrollPane( display ); // add components to GUI 45 Container container = getcontentpane(); 46 container.setlayout( new FlowLayout() ); 47 container.add( prompt ); 48 container.add( inputfield ); 49 container.add( gobutton ); 50 container.add( displayscrollpane ); 51 MapTest.java 52 setsize( 400, 400 ); 53 show(); } // end constructor // create map from user input 58 private void createmap() 59 { 60 String input = inputfield.gettext(); 61 StringTokenizer tokenizer = new StringTokenizer( input ); while ( tokenizer.hasmoretokens() ) { 64 String word = tokenizer.nexttoken().tolowercase(); // get word // if the map contains the word 67 if ( map.containskey( word ) ) { Integer count = (Integer) map.get( word ); // get value // increment value 72 map.put( word, new Integer( count.intvalue() + 1 ) ); 73 } 74 else // otherwise add word with a value of 1 to map 75 map.put( word, new Integer( 1 ) ); } // end while } // end method createmap MapTest.java Line 69 Lines 72 and 75 39

40 80 81 // create string containing map values 82 private String createoutput() { 83 StringBuffer output = new StringBuffer( "" ); 84 Iterator keys = map.keyset().iterator(); // iterate through the keys 87 while ( keys.hasnext() ) { 88 Object currentkey = keys.next(); // output the key-value pairs 91 output.append( currentkey + "\t" + 92 map.get( currentkey ) + "\n" ); 93 } output.append( "size: " + map.size() + "\n" ); 96 output.append( "isempty: " + map.isempty() + "\n" ); return output.tostring(); } // end method createoutput 101 MapTest.java 102 public static void main( String args[] ) 103 { 104 WordTypeCount application = new WordTypeCount(); 105 application.setdefaultcloseoperation( JFrame.EXIT_ON_CLOSE ); 106 } } // end class WordTypeCount MapTest.java 40

41 Synchronization Wrappers Built-in collections are unsynchronized Concurrent access to a Collection can cause errors Java provides synchronization wrappers to avoid this Via set of public static methods public static method header Collection synchronizedcollection( Collection c ) List synchronizedlist( List alist ) Set synchronizedset( Set s ) SortedSet synchronizedsortedset( SortedSet s ) Map synchronizedmap( Map m ) SortedMap synchronizedsortedmap( SortedMap m ) Fig Synchronization wrapper methods. 81 Unmodifiable Wrappers Unmodifiable wrappers Converting collections to unmodifiable collections Throw UnsorrtedOperationException if attempts are made to modify the collection public static method header Collection unmodifiablecollection( Collection c ) List unmodifiablelist( List alist ) Set unmodifiableset( Set s ) SortedSet unmodifiablesortedset( SortedSet s ) Map unmodifiablemap( Map m ) SortedMap unmodifiablesortedmap( SortedMap m ) Fig Unmodifiable wrapper methods

42 Abstract Implementations Abstract implementations Offer bare bones implementation of collection interfaces Programmers can flesh out customizable implementations AbstractCollection AbstractList AbstractMap AbstractSequentialList AbstractSet 83 42