---
# System prepended metadata

title: Collection
tags: [Java]

---

# Collection
Collection框架, 基本上裡面提供了不少容器工具, 可以快速的存放物件。

## 框架架構 - Iterable:

<font color="#00AA00">Iterable</font>, 可迭代的,
裡面有iterator(), 提供了基礎的迭代功能,並允許迭代中刪除元素。
任何可迭代的東西都可以實作Iterable

<font color="#00AA00">Collection</font>, 集合,
裡面有size(),isEmpty(),contains(),add(),remove(),addAll()...各種基礎的方法

接下來, 有三種介面, <font color="#00AA00">Set List Queue</font>
裡面一樣是加了各自的基礎方法, 並且保有Collection+Iterable的方法。

再下面有一些Abstract跟Class, 實作了上述的幾種介面供使用者直接使用
如<font color="#00AAAA">HashSet, ArrayList...</font>

可以看到這些
都是實作自某些Interface來的,並且實作的種類太多了,詳細請見Java Docs。

如果你自己想要設計一種Collection,你也可以自己實作上述的介面。

像是Concurrent系列就不是屬於Collection框架,但實作了一些框架中的介面。

![image](https://hackmd.io/_uploads/HJcItRJfR.png)
### Iterator實際用法:
```java=
//這裡先構建一個存放String的Collection
Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("c");

System.out.println(set); // [a, b, c]
Iterator<String> iterator = set.iterator();

//開始迭代
while(iterator.hasNext()) {
    String s = iterator.next(); //遍歷的值
    if(s.equals("b"))
        iterator.remove(); //迭代中刪除元素
}

System.out.println(set); // [a, c]
```
### Comparator
兩種物件的排序比較器

假設比較的是整數, 按照降序排列:
```java=
Comparator<Integer> comparator = new Comparator<Integer>() {
    @Override
    public int compare(Integer a, Integer b) {
        return b - a;
    }
}
```
裡面的int compare方法的return值,
如果是正數, 則a > b (o1放後)
如果是0, 則a = b (視為相同)
如果是負數, 則a < b (o1放前)
可以按照這個寫出想要的排序方法
### Enhanced for
```java=
for(E obj : iterable) {
    ...
}
```
## Set
<font color="#00AA00">Set</font>
這算是最簡單的Collection了, 只不允許重複物件存在。

常用方法:
```java
int size();
boolean isEmpty();
boolean contains(Object o);
void add(E e);
void remove(Object o);
void clear();
```
常用的Set實作:
- HashSet
基於HashMap, 允許null值, 不保證順序。
```java=
Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add(null);
set.add("c");
for(String s : set){
    System.out.println(s); //不保證順序
}
```
- LinkedHashSet
繼承自HashSet, 允許null值, 有序。
- TreeSet
基於TreeMap, 不允許null值, 可以自訂排序法。
```java=
Set<Integer> set = new TreeSet<>(comparator);
set.add(1);
set.add(3);
set.add(2);
set.add(4);
for(Integer s : set) {
    System.out.println(s + " "); //4 3 2 1
}
```
## List:
允許重複物件存在, 可以說是最常用

常用方法:
```java
int size();
boolean isEmpty();
boolean contains(Object o);
boolean add(E e);
boolean remove(Object o);
E get(int index); 查看某一格的元素
E set(int index, E element);
void add(int index, E element);
E remove(int index); 刪除某一格的元素
int indexOf(Object o);
int indexOf(T); 查看某物件在哪個index,如果不存在return -1
int lastIndexOf(Object o);
```

常用List實作:
- ArrayList
基於Array, 允許null, 保證順序。
預設長度10,超過會自動"grow"
```java=
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
for(String s : list) {
    System.out.println(s + " "); //a b c d
}
```
- LinkedList
每一個node存放元素&下一個node的地址, 允許null, 保證順序。
- Vector
跟ArrayList很像, 基於Array, 允許null, 保證順序。
預設長度10,超過會自動"grow"
但是他**Thread Safe**->在多線程環境中可以正常運作。

#### ArrayList, LinkedList比較:
功能都差不多,主要差異在於:
- 取值:
ArrayList O(1),  LinkedList O(n) (Array的RandomAccess確實很快, LinkedList需要逐一走訪)
- 增刪:
ArrayList O(n),  LinkedList O(1) (Array需要調整大小,還需要grow)

並且LinkedList使用更多記憶體。

## Queue:
先進先出(FIFO)的集合。
```add -> tail item2 item3 item4 ... front -> remove```

兩種增加元素(tail)的方法:
- boolean add(E e)
如果queue滿了,add會丟擲IllegalStateException
- boolean offer(E e)
如果queue滿了,offer會return false

取值(head):
- E poll()
  取得,並刪除元素, 丟擲NoSuchElementException如果Queue為空
- E remove()
  取得,並刪除元素, return null如果Queue為空
- E element()
  取得, 丟擲NoSuchElementException如果Queue為空
- E peek()
  取得, return null如果Queue為空

常用的有:
- ArrayDeque
- LinkedList
- PriorityQueue

## Map:
![image](https://hackmd.io/_uploads/BJViKC1fA.png)

<font color="#00AA00">Map</font>是Key->Value成對存放的Collection

常用方法:
```java=
int size();
boolean isEmpty();
boolean containsKey(Object key); //查看是否存在key
boolean containsValue(Object value); //查看是否存在value
V get(Object key);
V put(K key, V value); //放入K,V對 (如果K存在map中,把K對應的值改成V)
V remove(Object key); //刪除
void putAll(Map<? extends K, ? extends V> m);
void clear();
Set<K> keySet(); //return all keys as Set
Collection<V> values(); //return all values as set
Set<Map.Entry<K, V>> entrySet(); //return a set of map entries
```
常用Map實作:
- HashMap
用HashCode當作Key, 允許null
```java=

Map<String, Integer> map = new HashMap<>();
map.put("andy", 18);
map.put("kevin", 20);

System.out.println(map.get("andy")); //18
```
- TreeMap
基於紅黑樹, 不允許null, 實作NavigableMap, 可以用Comparator
- LinkedHashMap
基於Twin LinkedList 允許null, 保證順序。

### Enhanced for
```java=
for(Map.Entry<K,V> obj : map.entrySet<>()) {
    ...
}
```