Java Collection FAQ

範圍 — 集合框架：整個階層、ArrayList 與 LinkedList 的差別、HashMap 與 ConcurrentHashMap 的內部結構，以及每個操作的 Big-O。 另見：java_generics.md — 這些 API 用到的型別參數；java_functional.md — 用 stream 處理它們；java_multi_thread.md — 並發版本。

1) Collection 階層

Iterable
 └─ Collection
     ├─ List      → ordered, indexed, allows duplicates
     │    ├─ ArrayList        (resizable array)
     │    ├─ LinkedList       (doubly linked list; also a Deque)
     │    └─ Vector           (legacy, synchronized)
     ├─ Set       → no duplicates
     │    ├─ HashSet          (unordered, backed by HashMap)
     │    ├─ LinkedHashSet    (insertion order)
     │    └─ TreeSet          (sorted, backed by TreeMap)
     └─ Queue / Deque → FIFO / double-ended
          ├─ ArrayDeque       (fast stack/queue)
          ├─ LinkedList
          └─ PriorityQueue    (heap-ordered)

Map (NOT a Collection)
 ├─ HashMap            (unordered)
 ├─ LinkedHashMap      (insertion / access order)
 ├─ TreeMap            (sorted by key)
 ├─ Hashtable          (legacy, synchronized)
 └─ ConcurrentHashMap  (thread-safe, high concurrency)

2) ArrayList 與 LinkedList

經驗法則：預設就用 ArrayList。LinkedList 很少是正確答案；要 stack／queue 就用 ArrayDeque。

• ArrayList 滿了會成長約 1.5 倍 —— 已知大小就用 new ArrayList<>(n) 先開好， 避免反覆複製。

3) HashMap 的內部結構

底層是一個 bucket 陣列（Node[] table）。每個 bucket 放的是 key 雜湊到該索引的 那些項目。

index = (n - 1) & hash(key)     // n = table length (always a power of 2)

• 雜湊擴散：hash = h ^ (h >>> 16) 把高位混進低位，讓雜湊值有更多位元能影響 bucket 索引。
• 碰撞用鏈結處理：
  • Java 7：鏈結串列（新節點插在最前面）。
  • Java 8 以後：先是鏈結串列，當一個 bucket 有 ≥ 8 個項目而且** table 大小 ≥ 64 時轉成紅黑樹**。該 bucket 的查找就從 O(n) 變成 O(log n)。 縮回 ≤ 6 個時再退化成串列。
• 負載因子（預設 0.75）：當 size > capacity * loadFactor 時，table 會 擴容（容量加倍）並把項目重新雜湊。0.75 是空間與碰撞率之間的平衡點。
• 預設容量：16。
• null key：允許（放在 bucket 0）；null value 也允許。
• 不是執行緒安全的 —— 並發寫入可能把結構弄壞。

equals / hashCode 的契約（非常重要）：

• 若 a.equals(b)，則 a.hashCode() == b.hashCode()。
• 不相等的物件可以有相同雜湊（碰撞），但最好不要。
• 兩個都要一起覆寫，否則以雜湊為基礎的集合就壞了。key 請用不可變的欄位。

4) HashSet、LinkedHashMap、TreeMap

• HashSet：只是 HashMap 的一層薄包裝 —— 元素當 key，value 放一個固定的虛值。 add/contains/remove 平均 O(1)；沒有順序。
• LinkedHashMap：HashMap 再加一條雙向鏈結串列，把項目依插入（或存取）順序串起來。 存取順序模式讓它直接就是一個現成的 LRU 快取（覆寫 removeEldestEntry）。
• TreeMap：紅黑樹，key 保持排序（自然順序或 Comparator）。 操作 O(log n)；支援範圍查詢（floorKey、ceilingKey、subMap）。

5) ConcurrentHashMap

高併發下的執行緒安全 map，比 Hashtable / Collections.synchronizedMap （它們鎖整個 map）好得多。

• Java 7：分段鎖（lock striping）—— map 切成多個 segment，各自獨立上鎖。
• Java 8 以後：拿掉 segment。改用 CAS + 對 bucket 頭節點 synchronized， 所以鎖是以 bucket 為單位 → 寫入併發度高。讀取則完全無鎖。
• 不允許 null key 或 value（在並發讀取下，它和「不存在」無法區分）。
• 原子輔助方法：putIfAbsent、computeIfAbsent、merge。

6) Big-O 速查

7) 常見的坑

• Fail-fast 迭代器：迭代期間修改集合（除了透過 Iterator.remove()）可能丟出 ConcurrentModificationException —— 這個檢查是盡力而為，所以永遠不要寫依賴它的 邏輯。要條件式移除就用 removeIf。
• Arrays.asList() 回傳的是以該陣列為底的固定長度 list —— add/remove 會丟例外。 List.of(...) 則完全不可變、也不接受 null；需要可變的副本時用 new ArrayList<>(List.of(...))。
• 宣告時用介面：List<T> x = new ArrayList<>()。
• 要 stack 就用 ArrayDeque，不要用 Stack（舊類別，而且有同步開銷）。
• 可變的 key 會毀掉 map：插入後才改動 hashCode() 用到的欄位，那個項目就永遠 再也找不到了。
• 集合存的是物件，所以 List<Integer> 每個元素都會裝箱 —— 熱路徑上請用 int[] 或 primitive stream。
• HashMap 的迭代順序沒有規範，而且擴容時會變；在意順序就用 LinkedHashMap， 在意排序就用 TreeMap。

8) 一張表選完

參考資料

• JavaGuide — collection questions · part 2
• JavaGuide — HashMap 原始碼導讀
• java_generics.md · java_functional.md · java_multi_thread.md