Microsoft PowerPoint - chap13.ppt

Transcription

1 第 13 章集合 資訊科技系 林偉川 集合 了解 Collection 具體類別所使用的基本資料結構熟悉 Collection Framework 介面的繼承架構熟悉各個 Collection 具體類別的特性及應用熟悉 Generic 了解 Arrays 與 Collections 類別的常用方法了解覆蓋 equals() 方法的規則了解 equals() 和 hashcode() 之間的關係了解 Comparable 介面的功能 2 1

2 Collection 中所使用的基本資料結構 陣列 (array) 鏈結串列 (linked list) 樹 (tree) 雜湊表 (hash table) 陣列 陣列的重要特性 : 存取元素的速度快 要在某位置插入或移除元素值時, 並不方便 陣列長度為固定, 欲改變長度必須重新建立另一個陣列 4 2

3 陣列 在陣列中插入一個元素值 陣列 重新設定陣列大小 a step step step 3 a

4 鏈結串列 可以鏈結的類別 class LinkedObj { Object data; LinkedObj next; // 節點資料 // 下一個節點 鏈結串列的重要特性 : 插入或刪除節點很方便 變更鏈結串列的長度也很方便 存取節點的速度較慢速度較慢 鏈結串列鏈結串列的插入 刪除和串接串接節點 原串列 插入 刪除 串接 8 4

5 樹 實體可以做為二元樹的節點可以做為二元樹的節點的類別的類別 class TreeNode { Object data; TreeNode left; TreeNode Mid; TreeNode right; 樹的優點是有排序排序的功能, 缺點和鏈結串列一樣, 節點資料的存取比較慢 樹 二元樹 10 5

6 雜湊表 雜湊表 (hash table) 的資料是以鍵值對 (key value paired) 的形式存在 加入一個元素時必須同時給予一個 key 和一個 value, 透過 key 就可以取得 value 雜湊表的特點 : 存取資料的速度快 較浪費記憶體空間浪費記憶體空間 雜湊表 雜湊表的實作方式 key 1 key 2 演算法則 value 1 value

7 Collection Framework 內的介面架構 Collection 介面 Collection 介面定義的集合, 其元素可以為無順序 (non-ordered) ordered) 和可重複 (repetition allowed) Collection 兩個延伸介面 List 和 Set,, 分別保有 Collection 的不同特性 Set 的特點為, 其元素不可重複其元素不可重複 SortedSet 介面繼承 Set 介面, 且宣告了排序排序的方法的方法 List 介面繼承 Collection 介面, 然而它是有順序有順序的的, 而且是可以重複可以重複的 14 7

8 Map 介面 Map 介面和 Collection 介面沒有繼承的關係 Map 介面的元素是 鍵值對鍵值對 (key-value pairs) Map 中的 key 和 value 皆為參照變數, 而且 key 不能重複, 一個 key 對應到一個 value Map 中的元素是沒有順序的 SortedMap 介面為 Map 的子介面, 其為可排序其可排序的集合 15 請注意 Collection 具體類別的相關特性 : 類別實作的介面 類別使用的資料結構資料結構 元素可否重複 無序或有序 ( 加入的先後順序, 或有排序功能 ) 是否為執行緒同步 (Thread safe class) 有哪些常見的應用 16 8

9 實作 Collection 延伸介面的具體類別 17 實作 Map 介面的具體類別 18 9

10 實作 List 介面的具體類別 ArrayList 使用 array 資料結構實作 List 保有陣列的特性, 存取元素的效率佳, 但不利於插入或移除元但素, 且重定陣列長度效率差且重定陣列長度效率差 LinkedList 使用 linked list 實作 List 保有 linked list 的特性, 存取元素的效率較差, 但利於插入元素 移除元素和改變長度 Vector 和 ArrayList 很像, 都是以 array 實作 List 兩者最大的不同是在於 :Vector: 為 執行緒同步類別, 而 ArrayList 則否 實作 List 介面的具體類別 Stack 為 Vector 的延伸類別, 所以同樣為有序有序 執行緒同步類別 Stack 類別是堆疊的抽象資料型別 (Abstract Data Type) 推入 A 推入 B 推入 C 彈出 C C B B B A A A A 20 10

11 泛型 (Generic) Generic 提供了限定 Collection 物件的元素型別之功能, 也去除感覺累贅的感覺累贅的型別轉換型別轉換敘述敘述 Generic 使用尖括號 ( 和小於 大於使用的小於 大於使用的符號相同 ), 尖括號內放的是元素限定的型別名稱元素限定的型別名稱 整個尖括號放在 Collection 型別名稱之後, 包含使用建構子時 泛型 (Generic) Generic 的例子 LinkedList <Integer> list; list = new LinkedList <Integer>(); LinkedList <Integer> list = new LinkedList <Integer>(); 22 11

12 java.util.collection 介面的原始碼定義 : package java.util; public interface Collection<E> extends Iterable<E> { int size(); boolean isempty(); boolean contains(object o); Iterator<E> iterator(); Object[] toarray(); <T> T[] toarray(t[] a); boolean add(e o); boolean remove(object o); boolean containsall(collection<?> c); boolean addall(collection<? extends E> c); boolean removeall(collection<?> c); boolean retainall(collection<?> c); void clear(); boolean equals(object o); int hashcode(); 實作 Set 介面的具體類別 HashSet 使用 hash table 實作 Set 元素沒有順序, 而且元素不可重複存在 HashSet 物件內 其 key 和 value 是使用相同的物件, 也就是被加入的物件, 存取效率佳 LinkedHashSet 除了使用 hash table,, 還使用 linked list 實作 Set,, 使之成為有序集合有序集合 元素的順序是依照加入的順序, 而且元素不可重複存在 TreeSet 使用 tree 實作 SortedSet,, 所以元素在加入集合時, 就會和既有的元素比較, 以放在適當適當的位置, 不同型別不能互相比較, 加入不同型別產生例外 24 12

13 實作 Map 介面的具體類別 HashMap 使用 hash table 實作 Map,, 此集合中 key-value pairs 順序和放入的順序無關, 而且 key 無法重複, Map 沒有 add() 方法, 而改用 put() 和 get() 方法 LinkedHashMap 使用 hash table 和 linked list 實作 Map, 此集合中 key-value pairs 順序就是放入的順序, 而 key 同樣無法重複 TreeMap 使用 tree 實作 Map,, 此集合中 key-value pairs 順序是依照 key 在集合中的排序而定, 而 key 同樣無法重複 實作 Map 介面的具體類別 HashMap LinkedHashMap TreeMap 類別沒有 iterator() 方法可以取得 Iterator 物件, 但可透過 keyset() 取得包含 key 的 Set 型別物件, 再利用 Set 物件取得 Iterator 物件, 或使用 value() 取得 Collection 型別物件, 再利用 Collection 物件取得 Iterator 物件 Hashtable 和 HashMap 的功能差不多, 不同處在於 Hashtable 為執行緒同步, HashMap 則不是 Properties 為 Hashtable 的延伸類別 Properties 的 key 和 value 應該為 String 型別, 而且使用 setproperty() 和 getproperty() 取代 put() 和 get() 26 13

14 具體類別的整體比較 具體類別 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 排序無關加入順序無關加入順序 執行緒同步 否否是 * 是 * 否否否否否否是 * 是 * Arrays Arrays 的靜態方法 List aslist(object[] a) int binarysearch(int[] a, int key) boolean equals(int[] a, int[] a2) void fill(int[] a, int val) void sort(int[] a) 說明 將 Object 陣列 a 轉換成 List 物件, 然後回傳 在已排序的 a 陣列中以二次搜尋法, 找出 key 的索引值 若找不到 key 則回傳 1 此方法有許多因應不同型別陣列的多載方法 比較兩陣列 a 和 a2, 若兩陣列中的元素值皆相等則回傳 true 此方法有許多因應不同型別陣列的多載方法 將 a 陣列中的所有的元素值設定為 val 此方法有許多因應不同型別陣列的多載方法 對陣列 a 排序 此方法有許多因應不同參數的多載方法 28 14

15 Collections Collections 中的靜態方法靜態方法大都針對 List,, 因為 List 不像 Set 和 Map 有可排序的類別 Collections 另外提供將 非執行緒同步非執行緒同步 集合包裹成 執行緒同步執行緒同步 集合的方法, 這些方法在多執行緒程式裡會顯得相當方便 29 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) SortedSet synchronizedsortedset(sortedset s) 說明 以二次搜尋法, 找出 key 的索引值 將 src 序列的所元素複製給 dest 序列 將 list 序列中的 oldval 換成 newval 物件 若 oldval 不包含在 list 內則回傳 false 將 list 序列的順序顛倒 亂數重排 list 序列中元素的順序 對 list 序列排序 取得一執行緒同步的集合 30 15

16 是否相等 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() 是否相等 hashcode() 方法在使用 hash table 的集合中顯得相當重要, 因為 hash table 是以 key.hashcode() 取得的 hash code value( 雜湊值 ) 當你覆蓋 equals() 方法時, 也必須覆蓋 hashcode() 方法, 讓兩者的行為一致 32 16

17 是否相等 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; 33 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; return false; int i = offset; int j = anotherstring.offset; while (n--!= 0){ if (v1[i++]!= v2[j++]) return false; return true; // 參照相同 // 字串長度 // 字元陣列 // 第一字元的位置 // 有任何字元不同 // 所有字元都相同 // 不是 String 型別 34 17

18 是否相等 String 類別的 hashcode() 方法 public int hashcode(){ int h = hash; // 取得字串的雜湊碼 if(h == 0){ // 若雜湊碼為 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; s[0]*31^(n-1)+ s[1]*31^(n-2) s[n-1] 是否相等 自訂類別的 equals() 和 hashcode() 定義 equals() 時, 可以一一比對各個屬性是否相等 屬性大多為現成的類別或基本資料型別, 因此, 就可以使用現成的類別的 equals() 方法 定義 hashcode() 時, 只要將屬性的雜湊碼相互做位元互斥 (XOR,^) 運算即可 36 18

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