集合(Collections)
以往要將原生資料或物件放入陣列中，陣列的長度需先宣告，一宣告就不能變更長度。若事先不知道長度或者要隨時可以變更長度，就必需使用集合。可以把集合想成是多啦A夢的百寶袋，要裝多少物件都可以，只要記憶体足夠即可。
集合中的每個物件被稱為元素(elements)，每個元素的型態可以不一樣，因為都會被轉換成 Object (未使用泛型時)，不過原生資料不允許被在集合之中。
集合的重點在於如何新增移除元素，如何找到並取出元件，以及走訪整個集合。集合重度依靠泛型而寫成的，所以就不再限定只會轉成 Object 。
Collection Type
集合的類型如下圖所示
Map Type
Map 的類型如下圖所示
Collection 介面有三個子類別，分別是 LIst，Queue 及 Set。
Map 是另一個獨立的介面，跟 Collection 無關，它類似 Python 的字典。Collection 介面定義了add，addAll，clear，contains，wquals，remove，removeAll，size，iterator 等相關方法。
Iterator 介面
Iterator 為 Collection 的走訪器，有hasNext()，next()，remove() 等方法，只能由上往下走。若要能往上讀取就要使用ListIterator。
ListIterator 繼承 Iterator，可作新增修改刪除動作，每個元素間都有 index，可用 index 取得元素，有 add，hasNext，hasPrevious，next，nextIndex，previous，previousIndex，remove，set 等方法。
Enumeration 介面
為 Map 的走訪器，有 hasMoreElements，nextElement 等方法。
集合的四特性
了解每一個集合時, 需記住每個集合是否有如下四個特性 :
排序性 : 遞增或遞減的特性。
順序性 : 是否有依加入的順序排列。有順序就無排序, 有排序就無順序。
重複性 : 是否允許出現重複的物件。
鍵值 (Key/value) : 使用鍵值存放物件，只有 Map 使用此法。
| 集合介面 | 排序性 | 順序性 | 不允許重複 | 使用鍵值 |
| ArrayList | v | |||
| LinkedList | v | |||
| Vector | v | |||
| HashSet | v | |||
| LinkedHashSet | v | v | ||
| TreeSet | v | v | ||
| HaspMap | v | |||
| LinkedHashMap | v | v | ||
| HashTable | v | |||
| TreeMap | v | v |
Set 介面
Set 介面的特性為裏面的物件不會重複。
HastSet
HastSet 使用 HashCode 來判斷物件是否相同，如果相同則新物件會覆蓋舊物件，所以 HashSet 裏的物件不會重複，且無順序性，無排序性。
HashCode (雜湊碼) 是一種數學演算法，HashSet 使用 HashCode 決定物件要存放的位置。所以在大量的資料中要查找某個物件，使用 HashSet 是個效能非常高的方式。
Set<String> set=new HashSet<>();
set.add("one");
set.add("two");
set.add("three");
set.add("three");//會覆蓋前面的 three
Set<String>s1=new HashSet<>();
s1.add("Mercury");
s1.add("Venus");
s1.add("Earth");
s1.add("Mars");
s1.add("Jupiter");
for (String s:s1){
System.out.printf("%s\n", s);
}
Iterator it=set.iterator();
while(it.hasNext()){
System.out.prinff("%s\n", it.next());
}
結果 :
Earth
Mars
Jupiter
Venus
Mercury
LinkedHashSet
LinkedHashSet 也是使用 HashCode 決定物件存放的位置，但多了雙向連結記錄上下物件，所以具順序性，無排序，不允許重複，新增修改的效能略遜於 HashSet (因為要加雙向連結)。
Set<String>s2=new LinkedHashSet<>();
s2.add("Mercury");
s2.add("Venus");
s2.add("Earth");
s2.add("Mars");
s2.add("Jupiter");
for (String s:s2){
System.out.printf("%s\n", s);
}
結果 :
Mercury
Venus
Earth
Mars
Jupiter
若要將 HashSet 依加入的順序取出的話，可轉為 LinkedHashSet 類型，如下所示。
HashSet hs=new HashSet();
LinkedHashSet lhs=new LinkedHashSet(hs);
TreeSet
TreeSet 不是使用 HashCode 來判斷物件是否重覆，它是繼承 SortedSet，使用二元樹排序，一樣重複的物件會覆蓋舊物件，具排序性，無順序性，不可重複，新增修改的效能是最差的。
List 介面
最像陣列的集合，每個集合都有 index，除了可動態擴充長度外，其他都跟陣列一樣。
所有的 List 都是有順序性、無排序、可重複，可使用如下的方法新增、插入、刪除
add("Apple") //在最後新增資料
add(2,"Banana") //在索引2 插入新資料
get(index) //取得 index 索引的資料
remove(index) //移除 index 索引的資料
indexOf("Apple") //取得第一個 "Apple 的索引編號
ArrayList
最簡易使用的 List 就屬 ArrayList，使用 add 新增、get(index) 取出、remove(index) 刪除。ArrayList 底層其實是一個陣列，並不是雙向連結。當元素超出目前陣列容量時，ArrayList 會自動擴充容量(通常是原來容量的 1.5 倍到 2 倍)，並複制資料到新的陣列中，所以效能非常的差。
非泛型ArrayList
class OldStyleArrayList{
public void static main(String[] args){
List list=new ArrayList(3);
list.add(new Integer(1111));
list.add(new Integer(2222));
list.add(new Integer(3333));
list.add("Oops a string");
Iterator i=list.iterator();
while(i.haveNext()){
Integer o=(Integer)(i.next()); // Runtime error;
}
}
}
泛型 ArrayList
class GenericStyleArrayList{
public void static main(String[] args){
List<Integer> list=new ArrayList<>(3);
list.add(new Integer(1111));
list.add(new Integer(2222));
list.add(new Integer(3333));
list.add("Oops a string"); //Compile error
Iterator i=list.iterator();
while(i.haveNext()){
Integer o=i.next();
}
}
}
非泛型會產生 Runtime error，且必需要強制轉型。泛型會產生 Compiler error，不需強制轉型。
LinkedList
LinkedList 採用雙向鏈結，所以在新增刪除的效能比 ArrayList 快很多，但走訪的效能比 ArrayList 差。LinkedList 比 ArrayList 多了一個 addLast，其功能同 add。
教學上大都以 ArrayList 說明，但實際在撰寫專案時，盡量使用 LinkedList 以提高效能。
排序
如果要排序的資料是 Integer、String 等簡易的資料型態，可以使用 List 裏的 sort 及 Collection.sort 二種方式排序，如下代碼所示。
import java.util.*;
public class ArrayTest {
public static void main(String[] args){
List list=new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Banana");
//升冪
list.sort((a,b)->a.compareTo(b));
//或者
Collections.sort(list);
//降冪
list.sort((a,b)->b.compareTo(a));
//或者
Collections.reverse(list);
for (String i:list){
System.out.println(i);
}
System.out.println(list.indexOf("Banana"));
}
}
如果要排序的資料是自訂資料結構，也有如下二種方式。
public class ArrayTest {
public static void main(String[] args){
List datas = new LinkedList<>();
//datas.add(new Item(......)) //新增一些資料
//依日期升冪
datas.sort((a,b) -> a.date.compareTo(b.date));
//或者
datas.sort(Comparator.comparing((Item s) -> s.date));
//依日期降冪
datas.sort((a,b) -> b.date.compareTo(a.date));
//或者
datas.sort(Comparator.comparing((Item s) -> s.date).reversed());
}
}
class Item{
String date;
float open, height, low, close;
public Item(String date, float open, float height, float low, float close){
this.date=date;
this.open=open;
this.height=height;
this.low=low;
this.close=close;
}
}
Vector
Vector 是最原始的集合，特性同 ArrayList。但 Vector 是 Thread-safe，效能遠比 ArrayList 差，建議能不要用就不用。
Stack
繼承 Vector，具後進先出原則，使用 push 加入，pop 取出(並刪除)，peek取出(但不刪除)。
Queue 介面
Queue 具先進先出原則，但不要使用 add、remove 方法，因為會丟出例外。需改採 offer、poll、peek 三個方法。
LinkedList
LinkedList 除了實作 List 介面外，還實作了 Queue 介面，所以 LinkedList 除了可以當作 List 來使用，也可以當成 Queue。
Queue q=new LinkedList();
q.offer("First");
q.poll();
PriorityQueue
是一個可以自訂排序方式的類別，排序時先實作 Comparator 裏的 compare()方法，再將產生的物件放入PriorityQueue 建構子。
public class CollectionTest {
public static void main(String[] args) {
Comparator<String> c=new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2)*-1; //由大到小排序
}
};
PriorityQueue<String> queue=new PriorityQueue<>(3, c);
queue.offer("Mary");
queue.offer("Apple");
queue.offer("Thomas");
Iterator it=queue.iterator();
String s;
while((s=queue.poll())!=null){
System.out.println(s);
}
}
}
注意, String s=”abcd”;
s.compare(“defg”); 先一個字一個字比, 若前面比較小, 傳回負數, 前面比較大, 傳回正數, 二個都一樣, 傳回 0
Iterator
for-each 遍訪所有元素比較簡潔，但無法在迴圈中刪除資料，否則會發生 ConcurrentModificationException 例外。
使用 Iterator 遍訪所有元素時，可以在迴圈中安全的刪除修改元素，比較適合邊走邊修改的需求。
package net.ddns.mahaljsp;
import java.util.*;
public class ArrayTest {
public static void main(String[] args){
List list=new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Cherry");
list.add("Banana");
list.addFirst("Orange");
Iterator it=list.iterator();
while(it.hasNext()){
String item=it.next();
if(item.equals("Banana")){
it.remove();
}
else {
System.out.println(item);
}
}
}
}
Map 介面
Map在其他的語言如Python, C#中, 稱為字典, 是一個包含key及value的袋子. key必需是唯一, 值為物件. Map不繼承Collection介面. 使用put/putAll加入元素, get(key)取回元素
HashMap
無順序, 無排序, 可允許key及value都是null
LinkedHashMap
同HashMap, 但因為加了雙向鏈結, 所以走訪效能快, 新增刪除效能差
HashTable
同HashMap, 但這是thread-safe的, 鍵值不可為null
SortedMap
根據key值作自然排序, key不得重複也不可能null
TreeMap
實作SortedMap, 採二元樹排序, 裏面的鍵值必需是同一種資料型態
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
public class MapTest {
public static void main(String[] args) {
System.out.println("--------HashMap-------");
Map<String, String> m1=new HashMap<>();
m1.put("Mercury", "水星");
m1.put("Venus", "金星");
m1.put("Earth", "地球");
m1.put("Mars", "火星");
m1.put("Jupiter", "木星");
Set<String> keys1=m1.keySet();
for(String key:keys1){
System.out.printf("%s=>%s\n", key,m1.get(key));
}
System.out.println("--------LinkedHashMap-------");
Map<String, String> m2=new LinkedHashMap<>();
m2.put("Mercury", "水星");
m2.put("Venus", "金星");
m2.put("Earth", "地球");
m2.put("Mars", "火星");
m2.put("Jupiter", "木星");
m2.put("Saturn","土星");
m2.put("Uranus","天王星");
m2.put("Neptune","海王星");
m2.put("Pluto","冥王星");
Set<String> keys2=m2.keySet();
for(String key:keys2){
System.out.printf("%s=>%s\n", key,m2.get(key));
}
System.out.println("--------TreeMap-------");
Map<String, String> m3=new TreeMap<>();
m3.put("Mercury", "水星");
m3.put("Venus", "金星");
m3.put("Earth", "地球");
m3.put("Mars", "火星");
m3.put("Jupiter", "木星");
Set<String> keys3=m3.keySet();
for(String key:keys3){
System.out.printf("%s=>%s\n", key,m3.get(key));
}
}
}
結果 :
--------HashMap-------
Earth=>地球
Mars=>火星
Jupiter=>木星
Venus=>金星
Mercury=>水星
--------LinkedHashMap-------
Mercury=>水星
Venus=>金星
Earth=>地球
Mars=>火星
Jupiter=>木星
Saturn=>土星
Uranus=>天王星
Neptune=>海王星
Pluto=>冥王星
--------TreeMap-------
Earth=>地球
Jupiter=>木星
Mars=>火星
Mercury=>水星
Venus=>金星
Deque 介面
Deque是Collection的子介面, 可同時作為queue及stack
queue : FIFO, add, remove
stack : LIFO, push, pop
Deque stack=new ArrayDeque<>();
stack.push("one");
stack.push("two");
Collections集合工具
Collections.synchronizedMap(map) : 變成thread-safe
Collections.sort(list, sort); 依sort方式來排序, 見下面說明
排序集合(Ordering Collections)
Comparable 介面 : 需實作compareTo(), 僅提供一個排序的方式
返回值需包含0, 1, -1三個, 加入Collection的物件, 會依此排序取出
Comparator介面 : 需實作compare(), 可建立多個排序方式
List<Student> list=new ArrayList<>();
Compartor<Student> sortName=new StudentSortName();
Comparator<Student>sortGpa=new StudentSortGpa();
Colloections.sort(list, sortName); <==依sortName排序
Colloections.sort(list, sortGpa); <==依sortGpa序
NavigableSet/NavigableMap
此二個會根據內容作自然排序
NavigableSet 為SortedSet, 只可用在TreeSet;
NavigableSet<Integer> ns1=new TreeSet<>();
NavigableMap為SortedMap, 只可用在TreeMap;
NavigableMap<Integer, Integer> ns2=new TreeMap<>();
並行集合
常見的有
ConcurrentHashMap : 同步HashMap實作
ConcurrentSkipListMap : 同步TreeMap實作
CopyOnWriteArrayList : 同步ArrayList實作