第 13 章 集合 資料結構 collection 的介面 Collection 的具體類別 Arrays 與 Collections 類別 物件的比較.

Presentation on theme: "第 13 章 集合 資料結構 collection 的介面 Collection 的具體類別 Arrays 與 Collections 類別 物件的比較."— Presentation transcript:

1

2

3 第 13 章 集合 資料結構 collection 的介面 Collection 的具體類別 Arrays 與 Collections 類別 物件的比較

4

5 Collection 中所使用的基本資料結構 陣列（ array ） 鏈結串列（ linked list ） 樹（ tree ） 雜湊表（ hash table ）

6 13-1-1 陣列 陣列的重要特性： 存取元素的速度快。 要在某位置插入或移除元素值時，並不方便。 陣列長度為固定，欲改變長度必須重新建立另一個 陣列。

7 13-1-1 陣列 在陣列中插入一個元素值

8 13-1-1 陣列 重新設定陣列大小

9 13-1-2 鏈結串列 鏈結串列的重要特性： 插入或刪除節點很方便。 變更鏈結串列的長度也很方便。 存取節點的速度較慢。 可以鏈結的類別 class LinkedObj { Object data;// 節點資料 LinkedObj next;// 下一個節點 }

10 13-1-2 鏈結串列 鏈結串列的插入、刪除和加入節點

11 13-1-3 樹 樹的優點是有「排序」的功能，缺點和鏈結串列一 樣，節點資料的存取都比較慢。 實體可以做為二元樹的節點的類別 class TreeNode { Object data; TreeNode left; TreeNode right; }

12 13-1-3 樹 二元樹

13 13-1-4 雜湊表 雜湊表的特點： 存取資料的速度快。 較浪費記憶體空間。 雜湊表（ hash table ）的資料是以「鍵值對」 （ key value paired ）的形式存在。 加入一個元素時必須同時給予一個 key 和一個 value ，透過 key 就可以取得 value 。

14 13-1-4 雜湊表 雜湊表的實作方式

15

16 Collections Framework 內的介面架構

17 13-2-1 Collection 介面 Collection 介面定義的集合，其元素可以為無順序 （ non-ordered ）和可重複（ repetition allowed ）。 Collection 兩個延伸介面 List 和 Set ，分別保有 Collection 的不同特性。 Set 的特點為，其元素不可重複。 SortedSet 介面 繼承 Set 介面，且宣告了排序的方法。 List 介面繼承 Collection 介面，然而它是有順序的， 而且是可以重複的。

18 13-2-2 Map 介面 Map 介面和 Collection 介面沒有繼承的關係。 Map 介面的元素是「鍵值對」（ key-value pairs ）。 Map 中的 key 和 value 皆為參照變數，而且 key 不能 重複，一個 key 對應（ mapping ）到一個 value 。 Map 中的元素是沒有順序的。 SortedMap 介面為 Map 的子介面，故名思義，其為 可排序的集合。

19

20 請注意 Collection 具體類別的相關特性： 類別實作的介面。 類別使用的資料結構。 元素可否重複。 無序或有序（加入的先後順序，或有排序功能）。 是否為執行緒同步（ Thread safe class ）。 有哪些常見的應用。

21 實作 Collection 延伸介面的具體類別

22 實作 Map 介面的具體類別

23 13-3-1 實作 List 介面的具體類別 ArrayList 使用 array 資料結構實作 List 。保有陣列的 特性，存取元素的效率佳，但不利於插入或移除元 素，且重定陣列長度效率差。 LinkedList 使用 linked list 實作 List 。保有 linked list 的特性，存取元素的效率較差，但利於插入元素、 移除元素和改變長度。 Vector 和 ArrayList 很像，都是以 array 實作 List 。兩 者最大的不同是在於： Vector 為「執行緒同步類 別」，而 ArrayList 則否。

24 13-3-1 實作 List 介面的具體類別 Stack 為 Vector 的延伸類別，所以同樣為有序、執行 緒同步類別。 Stack 類別是堆疊的抽象資料型別 （ Abstract Data Type ）。

25 13-3-2 實作 Set 介面的具體類別 HashSet 使用 hash table 實作 Set 。元素沒有順序， 而且元素不可重複存在 HashSet 物件內。其 key 和 value 是使用相同的物件，也就是被加入的物件。 LinkedHashSet 除了使用 hash table ，還使用 linked list 實作 Set ，使之成為有序集合。元素的順 序是依照加入的順序。 TreeSet 使用 tree 實作 SortedSet ，所以元素在加入 集合時，就會和既有的元素「比較」，以排放在適 當的位置。

26 13-3-3 實作 Map 介面的具體類別 HashMap 使用 hash table 實作 Map ，此集合中 key- value pairs 順序和放入的順序無關，而且 key 無法重 複。 LinkedHashMap 使用 hash table 和 linked list 實作 Map ，此集合中 key-value pairs 順序就是放入的順 序，而 key 同樣無法重複。 TreeMap 使用 tree 實作 Map ，此集合中 key-value pairs 順序是依照 key 在集合中的排序而定，而 key 同樣無法重複。

27 13-3-3 實作 Map 介面的具體類別 Hashtable 和 HashMap 的功能差不多，不同處在於 Hashtable 為「執行緒同步」。 Properties 為 Hashtable 的延伸類別。 Properties 的 key 和 value 應該為 String 型別，而且使用 setProperty() 和 getProperty() 取代 put() 和 get() 。

28 13-3-4 具體類別的整體比較 具體類別直接實作介面資料結構元素重複性元素順序執行緒同步 ArrayListListarray 可依加入順序否 LinkedListListlinked list 可依加入順序否 VectorListarray 可依加入順序是*是* StackListarray 可依加入順序是*是* HashSetSethash table 不可無關加入順序否 LinkedHashSetSethash table linked list 不可依加入順序否 TreeSetSortedSettree 不可排序否 HashMapMaphash table key 不可無關加入順序否 LinkedHashMapMaphash table linked list key 不可依加入順序否 TreeMapSortedMaptree key 不可依 key 排序否 HashtableMaphash table key 不可無關加入順序是*是* PropertiesMaphash table key 不可無關加入順序是*是*

29

30 13-4-1 Arrays Arrays 的靜態方法說明 List asList(Object[] a) 將 Object 陣列 a 轉換成 List 物件，然後回傳。 int binarySearch(int[] a, int key) 在已排序的 a 陣列中以二次搜尋法，找出 key 的索引值。若找不到 key 則回傳 –1 。此方法 有許多因應不同型別陣列的多載方法。 boolean equals(int[] a, int[] a2) 比較兩陣列 a 和 a2 ，若兩陣列中的元素值皆相 等則回傳 true 。此方法有許多因應不同型別 陣列的多載方法。 void fill(int[] a, int val) 將 a 陣列中的所有的元素值設定為 val 。此方 法有許多因應不同型別陣列的多載方法。 void sort(int[] a) 對陣列 a 排序。此方法有許多因應不同參數的 多載方法。

31 13-4-2 Collections Collections 中的靜態方法大都針對 List ，因為 List 不 像 Set 和 Map 有可排序的類別。 Collections 另外提供將「非執行緒同步」集合包裹 成「執行緒同步」集合的方法，這些方法在多執行 緒程式裡會顯得相當方便。

32 Collections 的常用靜態方法說明 int binarySearch(List list, Object key) 以二次搜尋法，找出 key 的索引值。 void copy(List dest, List src) 將 src 序列的所元素複製給 dest 序列。 boolean replaceAll(List list, Object oldVal, Object newVal) 將 list 序列中的 oldVal 換成 newVal 物件。 若 oldVal 不包含在 list 內則回傳 false 。 void reverse(List list) 將 list 序列的順序顛倒。 void shuffle(List list) 亂數重排 list 序列中元素的順序。 void sort(List list) 對 list 序列排序。 List synchronizedList(List list) 取得一執行緒同步的集合。 Map synchronizedMap(Map m) Set synchronizedSet(Set s) SortedMap synchronizedSortedMap(SortedMap m) SortedSet synchronizedSortedSet(SortedSet s)

33

34 13-5-1 是否相等 Object.equals() 的定義如下： 當兩個物件 obj1 和 obj2 使用 equals() 比較後認定為 相等時，他們由 hashCode() 方法所取得的雜湊碼 也必須相同。所以當兩物件相等時，以下兩個運算 式的結果都必須為 true 。 public boolean equals(Object obj){ return (this == obj); } obj1.equals(obj2)== obj2.equals(obj1)== true obj1.hashCode()== obj2.hashCode()

35 13-5-1 是否相等 hashCode() 方法在使用 hash table 的集合中顯得相 當重要，因為 hash table 是以 key.hashCode() 取得的 hash code value （雜湊值）。 當你覆蓋 equals() 方法時，也必須覆蓋 hashCode() 方法，讓兩者的行為一致。

36 13-5-1 是否相等 Integer 類別中定義的 equals() Integer 類別中定義的 hashCode() public boolean equals(Object obj){ if(obj instanceof Integer){ return value == ((Integer)obj).intValue(); } return false; } public int hashCode(){ return value; }

37 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 型別 }

38 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; } 13-5-1 是否相等 s[0]*31^(n-1)+ s[1]*31^(n-2)+... + s[n-1]

39 13-5-1 是否相等 自訂類別的 equals() 和 hashCode() 定義 equals() 時，可以一一比對各個屬性是否相等。 屬性大多為現成的類別或基本資料型別，因此，就 可以使用現成的類別的 equals() 方法。 定義 hashCode() 時，只要將屬性的雜湊碼相互做 位元互斥（ XOR ， ^ ）運算即可。

40 13-5-2 較大或較小 TreeSet 和 TreeMap 都有自動排序的功能，既然要 能排序必定有比較大小的規則。 使用 tree 實作的 collection ，其元素必須是相同型別 的物件，而且必須實作 Comparable 介面。 String 類別和基本型別的包裝器（ Boolean 除外） 實作了 Comparable 介面。

41 13-5-2 較大或較小 Comparable 介面只宣告一個抽象方法 compareTo() 實作 compareTo() 方法必須遵守 int compareTo(Object o); 不同型別的物件不能比較 若物件本身比傳入的物件小時，則回傳負值。 若物件本身比傳入的物件大時，則回傳正值。 若不大也不小時，回傳 0 。