Java 的 Collection

Java 的 Collection 在現在（指 Java 8）主要還是分成三個大類：List、Set、Map。其中每個大類幾乎都有 Thread-Safe 跟 Non-Thread Safe 的區別。有些實作因為比較少用到，會慢慢從我的記憶中消失（表示為金魚腦）….。另外因為我上一次認真看這些東西是在 Java 6 的時候，到現在有些東西有可能有變化了，所以還是需要定期複習和更新一下認知，以確保在合適的時機使用合適的結構。

Collection

Java 1.4 開始支援的 Collection，主要是位於 java.util 裡的套件，這邊大體上來說都是 Non-Thread-Safe 的，除了 Vector 和 Hashtable 這兩個舊套件以外。

在一般使用情境中，可以參考網路上常看到的 cheat sheet [1-2]：

Interface	Hash Table	Resizable Array	Balanced Tree	Linked List	Hash Table + Linked List	Historical
Set	HashSet		TreeSet		LinkedHashSet
List		ArrayList		LinkedList		Vector, Stack
Deque		ArrayDeque		LinkedList
Map	HashMap		TreeMap		LinkedHashMap	Hashtable, Properties

在上面的表中，沒有被提及的是 Queue 和 Stack (?)，其中 Queue 比較容易被拿出來跟其他結構做比較，然後 Stack…是個很微妙的玩意兒。以下會稍微整理一下比較普遍的差異。

Non-Thread-Safe

首先這篇大體上只會談及那些 Non-Thread-Safe 的 Collection 類別，也就是說，java.util.concurrent 系列、以及 Hashtable、Vector 基本上不會在這篇當中仔細地提及。不過預計會有其他文章在整理 Thread-Safe 的那些 Concurrent Collection 類別就是了。

接著，這些 Non-Thread-Safe 的 Collection 大多有 fail-fast 的特性，也就是說在某些狀況遇到 concurrent access 時，它們會直接拋出 Exception，不過這通常都是被實作在 Inner Class 而不是在 Collection 本身的操作上。舉例來說，當使用 Iterator 遍訪 ArrayList 時，如果同時對 ArrayList 的實體做增刪的動作，就會拋出 ConcurrentModificationException，代表不能在遍訪的同時對 Collection 做變更。這裡的 concurrent access 檢查是被做在 ArrayList 回傳的 Iterator 實作上，而不是 ArrayList 本身的任何操作。

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

HashSet & HashMap

Hash 系列的 Set 都是由 Map 而來的，也就是說，HashSet 的實作方式是透過包裝 HashMap（即透過 Decorator Pattern），將 HashSet 存放的值放在 HashMap 的 Key 欄位，Value 欄位則指定恆久不變的預設值來達成。所以說 HashSet 會具有跟 HashMap 完全一樣的特徵，例如使用 hashCode() 來決定存放位置、以及在 Java 8 以後 HashSet/HashMap 底下會有平衡樹（紅黑樹）的結構在支持 [3]。

對於 LinkedHash 系列來說，它們的實作都是基於對應的 Hash 系列，再額外加上處理雙向鍊結的時間，因此 LinkedHash 系列可以保證有插入順序，但效能方面則比對應的 Hash 系列略差。

至於 HashMap 在多執行緒環境中會導致的問題，可以參考 [9-11]，主要問題會發生在 resize 的階段，可能導致出現無窮迴圈。不過因為 Java 7 和 Java 8 都對 HashMap 的原始碼做了修改，尤其 Java 8 加入了紅黑樹以後，原始碼變得挺複雜的，因此比較推薦閱讀 Java 7 的原始碼。這裡可以參考 [9] 的圖解，大略來說，當兩個 thread 同時在做 resize 的時候，有可能因為一起更新下述原始碼當中 Entry 的指標，導致指標形成環，讓 do-while 迴圈永遠走不出來。

PS. 但是就我目前的感覺，無窮迴圈的主要成因應該是兩個 thread 同時在更新指標，而且在更新過程會用倒序的緣故，才會導致兩個 thread 一起更新指標會創造出環狀的指標。但 Java 8 的實作因為大體上已經改成紅黑樹而不是 List 了，擴充時順序會倒序的這個特性已經消失了，所以不太確定是不是還是會創造出無窮迴圈。雖然如此，由於依然可以想像多個 thread 同時改指標多半會出事，所以 HashMap 不能用在多執行緒環境仍然是成立的。

對於在 Java 7 以上的 resize 階段，[11] 也有提到另一個優化，就是如果 resize 時是 2 的次方（也就是擴大成原來的兩倍）時，此時 hash 會有個特性，新的位置只會是 old index 或者是 old index + old length，因此實際上不需要重新做 rehash，只需要看看往左一位的 bit 是 0 還是 1 就能知道新的位置在哪了，也就是下面這段的 indexFor(e.hash, newCapacity) 做的事情。

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable) {
  Entry[] src = table;
  int newCapacity = newTable.length;
  for (int j = 0; j < src.length; j++) {
    Entry<K,V> e = src[j];
    if (e != null) {
      src[j] = null;
      do {
        Entry<K,V> next = e.next;
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
      } while (e != null);
    }
  }
}

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
  return h & (length-1);
}

ArrayList & LinkedList

在一般狀況下，如果沒有特殊的原因的時候，通常選擇 ArrayList 會比選擇 LinkedList 來得好 [6]。

LinkedList 內部使用了雙向鍊結作為實現的方法，因此對於頭尾的操作效能很好，是常數複雜度 O(1)。例如透過 add(E element) 方法來加入新的元素時，因為元素會被加入到 LinkedList 的尾端，因此效能很好；但如果是透過 add(int index, E element) 指定加入的位置時，複雜度就是 O(n) 了。如果要更確切地計算存取的複雜度的話，LinkedList 的 javadoc 有以下的描述：

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

也就是說，最佳狀況是 1 次的尋訪（存取第一個或最後一個元素的狀況），最差的狀況則是剛好在 LinkedList 的正中央，需要 n/2 次的尋訪。因此整體來說存取所需的平均尋訪次數就大約是 n/4 次。

ArrayList 最顯著的問題在於遇到 Array 需要增長的時刻，會有 O(n) 的複雜度用在複製整個 Array，此時無論是 CPU 還是記憶體都會造成一些負擔。但這個問題不見得會是顯著的問題，例如如果當我們能夠好好地預測 ArrayList 的長度時，就可以避開這個負擔。其次另一個負擔就是在指定位置加入或刪除元素的時候，ArrayList 可能會需要把陣列中一部分的元素重新定位，這會導致 O(n) 的操作（實際的平均操作次數大約是 n/2）。但除了這兩種狀況外，在像是透過 add(E element) 循序插入元素時，只要還沒超過 ArrayList 內部的 Array 長度，插入複雜度就是 O(1)，而其他時候的隨機存取也都是 O(1)。

接著，當談到記憶體用量的時候也需要注意到，LinkedList 因為要維護雙向鍊結，因此每個元素都需要額外的記憶體空間存放指標。相對來說，ArrayList 的每個元素幾乎沒什麼額外的消耗。但 ArrayList 由於宣告了 Array，Array 會佔用對應長度的記憶體空間，如果 ArrayList 宣告的長度並沒有被善用的話，就會形成記憶體的浪費。

另外，List 判斷元素的方法是透過呼叫 equals()，也就是說無論物件是不是同一個物件，只要呼叫 equals() 時回傳是 true，在 List 當中就會被視為是同一個元素。例如在 List 當中呼叫 remove(E element)，只要在呼叫物件的 equals() 時能夠在 List 當中找到一個回傳 true 的元素，那個元素就會被當成要被刪除的對象刪掉，即使它們並不一定真的是同個物件實體。

Iterator 方面的性能來說，ArrayList 有個比較奇妙的小特性，用 get(int index) 訪問 ArrayList 中的所有內容，會比使用 Iterator 來得稍快些，這可以從它的原始碼中看出。在呼叫 get(int index) 時，ArrayList 會做的事情只有檢查 index 的合法性，然後就會回傳內容了；但在使用 Iterator 時，ArrayList 的 Iterator 會額外檢查 concurrent modification（所以在遍訪 ArrayList 的同時修改內容才會在 Iterator 這邊拋出 ConcurrentModificationException），因此導致 ArrayList 使用 get(int index) 遍訪會比使用 Iterator 遍訪來得快的現象。而這點在 LinkedList 上則不存在，依據 LinkedList 的原始碼，ListIterator 在呼叫 next() 時並沒有做任何額外的事情。

TreeSet & PriorityQueue

TreeSet 和 PriorityQueue 雖然算是完全不同的類型，但它們又有許多相似之處，在某些場景下，可能可以互相考慮一下。

首先，TreeSet 是 Set，意味著它本質上是不允許重複的，而 Queue 則不在乎是否重複，不過實際上運用的時候倒也不一定是如此。因為兩者都能透過指定 Comparator 來控制順序，同樣也表示可以透過 Comparator 阻絕「判定為重複」的這件事。也就是說，例如 TreeSet<String> 預期應該不能放重複的字串，但如果我們在建立 TreeSet 時指定了不會回傳 0 的 Comparator，則重複就變得能夠允許了。

public void test () {
  TreeSet<String> strings = new TreeSet<String>(duplicatedComparator);
  strings.add("Hello!");
  strings.add("Hello!");
  
  System.out.println("Strings: " + strings);
}

private Comparator<String> duplicatedComparator = new Comparator<String>() {
  @Override
  public int compare (String str1, String str2) {
    if (str1.equals(str2)) {
      return 1;
    }
    return str1.compareTo(str2);
  }
};

這個例子最後執行的結果是這樣：

Strings: [Hello!, Hello!]

在上述這個例子中，我們宣告 TreeSet 時給它一個 Comparator，這個 Comparator 的比較永遠不會回傳 0，也就是說永遠不會認為兩個字串是相等的，此時放入兩個完全一樣的字串，結果就是兩個字串都會出現在 TreeSet 中。

不討論元素重複的問題的話，TreeSet 和 PriorityQueue 有著類似的特性，裡面的元素都會依照 Comparator 或者 Comparable 的順序排序。不過實務上如果以 Queue 的操作模式在操作 TreeSet 和 PriorityQueue 時，兩者在取出資料的效能並不相同。對 PriorityQueue 來說，要透過 peek() 取得第一個元素，複雜度是 O(1)，但對於 TreeSet 而言卻是 O(logn)。這是因為 PriorityQueue 是以 binary heap 的結構在存放資料，因此第一個元素一直都是在放最前面的，不需要尋找；但對於 TreeSet 來說，由於裡頭用了紅黑樹，因此要找到第一個元素需要尋訪到葉節點。

另外順道提一下，TreeSet 底下使用 TreeMap 來存放，跟 HashSet 和 HashMap 的關係是相同的。而 TreeMap 在存放資料的時候是以紅黑樹來存放及保持 Key 的順序，所以連帶也使得 TreeSet 的操作具有紅黑樹的特性。而 PrioritQueue 底下是以陣列結構作為實作，因此注意點會跟 ArrayList 相似，如果能夠妥善指定長度的話，可以顯著地提昇效率。

ArrayDeque & Stack

關於 Stack，它在 Java 裡真的是個挺微妙的東西。首先所有的 Collection 都會有對應的 interface 用來描述功能性，像是 java.util.List、java.util.Set、java.util.Map、java.util.Queue 等，但是 Stack 沒有。接著 Stack 一般認為的操作應該是 push()、pop() 之類的，也就是應該會被受限在只能對堆疊的頂端做操作，但是 Stack 卻有 get() 可以用索引取得非頂端的資料，而這是因為它繼承了 Vector。然後它為什麼是繼承 Vector 就更奇妙了，還連帶帶來了效能不好的結果…。

Deque 在 Java 裡代表的意義跟唸法，可以參考它的 javadoc：

A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

因為 Deque 是個雙向 Queue，所以它實作上既可以代表 Queue、又可以代表 Stack。Stack 的 javadoc 上也很明白地表示：

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

所以其實 Stack 這個物件幾乎是可以 deprecated 了吧….。

參考資料

1. Rule of thumb for choosing an implementation of a Java Collection?
2. Choosing the right Collection
3. The Collections Framework
4. Java - Collection Interfaces and Implementations
5. Java Collections Cheat Sheet
6. When to use LinkedList over ArrayList in Java?
7. Difference between PriorityQueue and TreeSet in Java?
8. 由浅入深理解java集合 (一) (二) (三) (四) (五) (六)
9. 老生常谈，HashMap的死循环
10. Java 1.8中HashMap的resize()方法扩容部分的理解
11. Java 8系列之重新认识HashMap
12. Why should I use Deque over Stack?
13. java 中的Stack、Queue、Deque