X集合

集合

集合是什麼 ? 與其優勢 ?

集合(Collection)

解釋 集合的層次( Collections hierarchy )架構 ?

Set、List、Queue 繼承 Collection 介面，Map 則沒有，因為不兼容。

為什麼集合不繼承 Cloneable 介面 或 Serializable 介面 ? 而是大部分的集合類都有自己繼承 ?

沒有必要，只是作為擴展當前的功能，並非每個物件都需要，更不需要耗費效能去繼承。

為什麼 Map 介面沒有繼承 Collection 介面？

因為他們不相容，Collection 具有 add 方法，Map 則需要 key-value 對應。

Iterator 和 ListIterator 之間的區別？

迭代器 Iterator

什麼是 fail-fast 安全機制 ? 是如何避開 ConcurrentModificationException ? 原理是什麼 ?

• 透過 Iterator，因為刪除完會執行 expectedModCount = modCount，保證了計數的同步。

• (建議) 用 ConcurrentHashMap 和 CopyOnWriteArrayList 類別。

• 將集合轉換為陣列，透過陣列進行迭代。

• 透過 synchronized block ，將集合鎖住的方式迭代。

迭代器 Iterator

如何建立只能讀的集合 ? 如何使集合執行緒安全 ?

//只讀集合
Collections.unmodifiableList(List);
Collections.unmodifiableSet(Set);
Collections.unmodifiableMap(Map);
//不支持集合的修改屬性，否則會報 UnsupportedOperationException

//執行緒集合
Collections.synchronizedList(List); 
Collections.synchronizedSet(Set);
Collections.synchronizedMap(Map);

Comparable 和 Comparator 介面 之間的區別 ?

比較器

List

什麼原因要使用 List 介面 ? 用過哪些 ?

• List 具有順序性，可重複，可根據索引來操作集合，速度較快。

• ArrayList、LinkedList、Stack、Vector。

Set

什麼原因要使用 Set 介面 ? 用過哪些 ?

• Set 沒有順序性，具有不重複唯一性，順序可能永遠不一致。

• HashSet、TreeSet、LinkedHashSet，EnumSet。

HashSet 如何確保其中的唯一性與其如何儲存元素 ?

透過 HashMap 集合，並在 Value 放置一個 static final 的 Object 物件。

可以在 HashSet 和 TreeSet 集合放入 null 嗎 ?

• HashSet 可以，內部是 HashMap 實作，且維持不重複性，就只有一個。

• TreeSet 不可以，內部是 NavigableMap 實作，不允許有 null。

兩者比較區別

HashMap	HashSet
實作 Map 介面	實作 Set 介面
儲存鍵值(key-value)	儲存對象
使用 put() 新增	使用 add 新增
使用 key 鍵做 hashCode 計算	使用成員對象做 hashCode 計算

Map

什麼原因要使用 Map 介面 ? 用過哪些 ? 與其中的差異 ?

是一種特殊的集合，用來儲存鍵值 (key-value) 關係。

• HashMap：一般場景。

  • 1.8以前： HashMap由陣列 + 鍊表組成的，陣列是 HashMap 的主體， 鍊表則是主要為了解決哈希衝突而存在的 ( "拉鍊法" 解決衝突)。

  • 1.8以後： 當鍊表長度大於閾值(默認為8)，會將鍊表轉換成紅黑樹前會判斷，以減少搜索時間。 (若當前陣列長度小於 64，那麼會選擇先進行陣列擴容，而不是直接轉換為紅黑樹)。

• TreeMap：可以自定義排序。

• LinkedHashMap：可以記錄插入順序和訪問順序。

• ConcurrentHashMap：執行緒安全。

• HashTable：執行緒安全。

• Properties ：繼承 HashTable，常用在環境變量設置，或系統訊息等等。

HashMap 的原理 ? 如何儲存 Key / Value 一對 ?

• 原理就是 基於 Hash (哈希碼)。

• 什麼是 Hash ? java 物件的 hashCode() 默認實現將記憶體位址轉為整數作為 hash， 因此每次將兩個對象應用於相同或相等的比較時，都應返回相同的哈希碼。

透過靜態類 Entry<K , V> 儲存鍵值。

static class Entry<K ,V> implements Map.Entry<K, V> {
    final K key;
    V value;
    Entry<K ,V> next;
    final int hash;
    ...//More code goes here
}

如何透過 equal() 和 hashCode() 解決衝突 ?

透過 LinkedList，透過靜態類的 next 值，指向下一個參數。

當一個 Entry 對象需要儲存在特定的索引中時，HashMap檢查是否已經有一個 Entry？ 如果還沒有已存在的 Entry，則將 Entry 對象儲存在此位置。 如果已經有一個對象位於特定索引上，則檢查 Entry 其屬性 next，如果為 null， 則當前 Entry 對象成為 LinkedList 中的下一個節點。 如果 next 的參數值不是 null，則遵循步驟直到 next 被評估為 null。

如果我們 put 一個不同的 value 對象到相同的 key 值，會取代舊值，是如何做的 ?

在確定 Entry 對象的索引位置之後，在對計算得出的索引進行 Linkedist 迭代(Iterator)時，

為每個 Entry 對象 使用 equals方法 比較 key 值。

Multi-Thread 環境中使用 HashMap 會有什麼問題？

• 1.8 以前

在並發的情況下，rehash 會造成元素之間形成一個循環的 LinkedList。

• 1.8 以後，新的解 hash 衝突方案解決了此問題。

但仍會造成資料流失。

HashMap 可以如何解決 Non Thread-Safe 的問題 ?

Collections 的 synchronizedMap 方法使 HashMap 具有 Thread - safe。

N ConcurrentHashMap 怎麼保證 Thread-Safe ? JDK 1.8 前後的鎖有什麼區別 ?

• 1.8以前 - 分段鎖

• 1.8以後 - CAS / Synchronized

彼此之間的差異

ArrayList 和 LinkedList 和 Vector 差別 ?

ArrayList

• 將元素儲存在動態調整大小的陣列中。

• 繼承 RandomAccess 標記介面，表示可以透過索引隨機訪問。

• 不能夠任意新增或刪除，只能從尾端新增，且時間複雜度受元素位置影響。

• 記憶體消耗較低。

• 非同步的，執行緒不安全。

LinkedList

• 將元素儲存在雙鏈結列表的資料結構中。

• 只允許順序訪問。

• 能夠指定位置新增或刪除，且時間複雜度不受元素位置影響。

• 記憶體消耗較高，因為鏈結結構，必須額外保存頭尾的位址與資料 。

• 非同步的，執行緒不安全。

Vector

• JDK的第一個版本中添加的舊類別，後來在1.2版才新增了 ArrayList。

• 同步的，Thread 安全。

• 默認情況下， Vector 在內部調整大小時會將其陣列大小加倍，而 arrayList 只會增加一半。

TreeSet 和 SortSet 的關係 ?

TreeSet 實作了 SortSet 介面。

HashMap 和 ConcurrentHashMap 和 LinkedHashMap 和 HashTable 的差別?

HashMap

• 是非同步的，執行緒不安全，相對效率較好。

• 允許有一個 null key 鍵值 和 任意數量的 value 值。

• Iterator 屬於 fail - fast 模式。

ConcurrentHashMap

LinkedHashMap

HashTable

• 是同步的，執行緒安全，相對效率較差。

• 不允許有 null Key 鍵值 或 value 值。

• Iterator 屬於 fail -safe 模式。

• 已逐漸被淘汰，若有執行緒問題，普遍使用 ConcurrentHashMap。

什麼是 Queue 和 Stack ? 兩者之間的差異 ?

設計用於處理元素進出先後的集合。

• Queue 通常但不一定以FIFO(先進先出)的方式對元素進行排序，也可以 LIFO (後進先出)。

• Stack 也是 Queue 的一種形式，但是只能 LIFO (後進先出)。

• Queue 是介面，繼承了 Collection 介面，底下有許多不同的實作。

• Stack 是類別，繼承了 Vector 類別，且都是同步的，執行緒安全。