備戰-Java 容器
玉階生白露，夜久侵羅襪。
簡介：備戰-Java 容器
容器主要包括 Collection 和 Map 兩種，Collection 存儲着對象的集合，而 Map 存儲着key-value 鍵值對（兩個對象）的映射表。
TreeSet：基于紅黑樹實作，支援有序性操作，例如根據一個範圍查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的時間複雜度為 O(1)，TreeSet 則為 O(logN)。
HashSet：基于哈希表實作，支援快速查找，但不支援有序性操作。并且失去了元素的插入順序資訊，也就是說使用 Iterator 周遊 HashSet 得到的結果是不确定的。
LinkedHashSet：具有 HashSet 的查找效率，并且内部使用雙向連結清單維護元素的插入順序。
ArrayList：基于動态數組實作，支援随機通路。
Vector：和 ArrayList 類似，但它是線程安全的。
LinkedList：基于雙向連結清單實作，隻能順序通路，但是可以快速地在連結清單中間插入和删除元素。不僅如此，LinkedList 還可以用作棧、隊列和雙向隊列。
LinkedList：可以用它來實作雙向隊列。
PriorityQueue：基于堆結構實作，可以用它來實作優先隊列。
TreeMap：基于紅黑樹實作。
HashMap：基于哈希表實作。
HashTable：和 HashMap 類似，但它是線程安全的，這意味着同一時刻多個線程同時寫入 HashTable 不會導緻資料不一緻。它是遺留類，不應該去使用它，而是使用 ConcurrentHashMap 來支援線程安全，ConcurrentHashMap 的效率會更高，因為 ConcurrentHashMap 引入了分段鎖。
LinkedHashMap：使用雙向連結清單來維護元素的順序，順序為插入順序或者最近最少使用（LRU）順序。(LRU算法是Least Recently Used的縮寫，即最近最少使用)
Collection 繼承了 Iterable 接口，其中的 iterator() 方法能夠産生一個 Iterator 對象，通過這個對象就可以疊代周遊 Collection 中的元素。
從 JDK 1.5 之後可以使用 foreach 方法來周遊實作了 Iterable 接口的聚合對象。
View Code
java.util.Arrays.asList() 可以把數組類型轉換為 List 類型。
值得注意的是 asList() 的參數為泛型的變長參數，不能使用基本類型數組作為參數，隻能使用相應的包裝類型數組。
也可以使用以下方式調用 asList()：
如果沒有特别說明，以下源碼分析基于 JDK 1.8。
在 IDEA 中 輕按兩下 shift 鍵調出 Search EveryWhere，查找源碼檔案，找到之後就可以閱讀源碼。
因為 ArrayList 是基于數組實作的，是以支援快速随機通路。RandomAccess 接口辨別着該類支援快速随機通路，其預設數組大小為10
添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠，如果不夠時，需要使用 grow() 方法進行擴容，新容量的大小為 <code>oldCapacity + (oldCapacity >> 1)</code>，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，是以新容量大約是舊容量的 1.5 倍左右。（oldCapacity 為偶數就是 1.5 倍，為奇數就是 1.5 倍-0.5）
擴容操作需要調用 <code>Arrays.copyOf()</code> 把原數組整個複制到新數組中，這個操作代價很高，是以最好在建立 ArrayList 對象時就指定大概的容量大小，減少擴容操作的次數。
需要調用 System.arraycopy() 将 index+1 後面的元素都複制到 index 位置上，該操作的時間複雜度為 O(N)，可以看到 ArrayList 删除元素的代價是非常高的。
ArrayList 基于數組實作，并且具有動态擴容特性，是以儲存元素的數組不一定都會被使用，那麼就沒必要全部進行序列化。
儲存元素的數組 elementData 使用 transient 修飾，該關鍵字聲明數組預設不會被序列化。
ArrayList 實作了 writeObject() 和 readObject() 來控制隻序列化數組中有元素填充那部分内容。
序列化時需要使用 ObjectOutputStream 的 writeObject() 将對象轉換為位元組流并輸出。而 writeObject() 方法在傳入的對象存在 writeObject() 的時候會去反射調用該對象的 writeObject() 來實作序列化。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理類似。
modCount 用來記錄 ArrayList 結構發生變化的次數。結構發生變化是指添加或者删除至少一個元素的所有操作，或者是調整内部數組的大小，僅僅隻是設定元素的值不算結構發生變化。
在進行序列化或者疊代等操作時，需要比較操作前後 modCount 是否改變，如果改變了需要抛出 ConcurrentModificationException。代碼參以上序列化中的 writeObject() 方法。
它的實作與 ArrayList 類似，但是使用了 synchronized 進行同步。
Vector 的構造函數可以傳入 capacityIncrement 參數，它的作用是在擴容時使容量 capacity 增長 capacityIncrement。如果這個參數的值小于等于 0，擴容時每次都令 capacity 為原來的兩倍。
調用沒有 capacityIncrement 的構造函數時，capacityIncrement 值被設定為 0，也就是說預設情況下 Vector 每次擴容時容量都會翻倍。
Vector 是同步的，是以開銷就比 ArrayList 要大，通路速度更慢。最好使用 ArrayList 而不是 Vector，因為同步操作完全可以由程式員自己來控制；
Vector 每次擴容請求其大小的 2 倍（也可以通過構造函數設定增長的容量），而 ArrayList 是 1.5 倍。
可以使用 <code>Collections.synchronizedList();</code> 得到一個線程安全的 ArrayList。
也可以使用 concurrent 并發包下的 CopyOnWriteArrayList 類。
寫操作在一個複制的數組上進行，讀操作還是在原始數組中進行，讀寫分離，互不影響。
寫操作需要加鎖，防止并發寫入時導緻寫入資料丢失。
寫操作結束之後需要把原始數組指向新的複制數組。
CopyOnWriteArrayList 在寫操作的同時允許讀操作，大大提高了讀操作的性能，是以很适合讀多寫少的應用場景。
但是 CopyOnWriteArrayList 有其缺陷：
記憶體占用：在寫操作時需要複制一個新的數組，使得記憶體占用為原來的兩倍左右；
資料不一緻：讀操作不能讀取實時性的資料，因為部分寫操作的資料還未同步到讀數組中。
是以 CopyOnWriteArrayList 不适合記憶體敏感以及對實時性要求很高的場景。
基于雙向連結清單實作，使用 Node 存儲連結清單節點資訊。
每個連結清單存儲了 first 和 last 指針：
ArrayList 基于動态數組實作，LinkedList 基于雙向連結清單實作。ArrayList 和 LinkedList 的差別可以歸結為數組和連結清單的差別：
數組支援随機通路，但插入删除的代價很高，需要移動大量元素；
連結清單不支援随機通路，但插入删除隻需要改變指針。
https://www.cnblogs.com/taojietaoge/p/11359542.html
Hashtable 使用 synchronized 來進行同步。
HashMap 可以插入鍵為 null 的 Entry。
HashMap 的疊代器是 fail-fast 疊代器。
HashMap 不能保證随着時間的推移 Map 中的元素次序是不變的。
參考連結：https://www.cnblogs.com/taojietaoge/p/10301711.html
ConcurrentHashMap 和 HashMap 實作上類似，最主要的差别是 ConcurrentHashMap 采用了分段鎖（Segment），每個分段鎖維護着幾個桶（HashEntry），多個線程可以同時通路不同分段鎖上的桶，進而使其并發度更高（并發度就是 Segment 的個數）。
Segment 繼承自 ReentrantLock。
預設的并發級别為 16，也就是說預設建立 16 個 Segment。
每個 Segment 維護了一個 count 變量來統計該 Segment 中的鍵值對個數。
在執行 size 操作時，需要周遊所有 Segment 然後把 count 累計起來。
ConcurrentHashMap 在執行 size 操作時先嘗試不加鎖，如果連續兩次不加鎖操作得到的結果一緻，那麼可以認為這個結果是正确的。
嘗試次數使用 RETRIES_BEFORE_LOCK 定義，該值為 2，retries 初始值為 -1，是以嘗試次數為 3。
如果嘗試的次數超過 3 次，就需要對每個 Segment 加鎖。
JDK 1.7 使用分段鎖機制來實作并發更新操作，核心類為 Segment，它繼承自重入鎖 ReentrantLock，并發度與 Segment 數量相等。
JDK 1.8 使用了 CAS 操作來支援更高的并發度，在 CAS 操作失敗時使用内置鎖 synchronized。
并且 JDK 1.8 的實作也在連結清單過長時會轉換為紅黑樹。
繼承自 HashMap，是以具有和 HashMap 一樣的快速查找特性。
内部維護了一個雙向連結清單，用來維護插入順序或者 LRU 順序。
accessOrder 決定了順序，預設為 false，此時維護的是插入順序。
LinkedHashMap 最重要的是以下用于維護順序的函數，它們會在 put、get 等方法中調用。
當一個節點被通路時，如果 accessOrder 為 true，則會将該節點移到連結清單尾部。也就是說指定為 LRU 順序之後，在每次通路一個節點時，會将這個節點移到連結清單尾部，保證連結清單尾部是最近通路的節點，那麼連結清單首部就是最近最久未使用的節點。
在 put 等操作之後執行，當 removeEldestEntry() 方法傳回 true 時會移除最晚的節點，也就是連結清單首部節點 first。
evict 隻有在建構 Map 的時候才為 false，在這裡為 true。
removeEldestEntry() 預設為 false，如果需要讓它為 true，需要繼承 LinkedHashMap 并且覆寫這個方法的實作，這在實作 LRU 的緩存中特别有用，通過移除最近最久未使用的節點，進而保證緩存空間足夠，并且緩存的資料都是熱點資料。
以下是使用 LinkedHashMap 實作的一個 LRU 緩存：
設定最大緩存空間 MAX_ENTRIES 為 3；
使用 LinkedHashMap 的構造函數将 accessOrder 設定為 true，開啟 LRU 順序；
覆寫 removeEldestEntry() 方法實作，在節點多于 MAX_ENTRIES 就會将最近最久未使用的資料移除。
WeakHashMap 的 Entry 繼承自 WeakReference，被 WeakReference 關聯的對象在下一次垃圾回收時會被回收。
WeakHashMap 主要用來實作緩存，通過使用 WeakHashMap 來引用緩存對象，由 JVM 對這部分緩存進行回收。
Tomcat 中的 ConcurrentCache 使用了 WeakHashMap 來實作緩存功能。
ConcurrentCache 采取的是分代緩存：
經常使用的對象放入 eden 中，eden 使用 ConcurrentHashMap 實作，不用擔心會被回收（伊甸園）；
不常用的對象放入 longterm，longterm 使用 WeakHashMap 實作，這些老對象會被垃圾收集器回收。
當調用 get() 方法時，會先從 eden 區擷取，如果沒有找到的話再到 longterm 擷取，當從 longterm 擷取到就把對象放入 eden 中，進而保證經常被通路的節點不容易被回收。
當調用 put() 方法時，如果 eden 的大小超過了 size，那麼就将 eden 中的所有對象都放入 longterm 中，利用虛拟機回收掉一部分不經常使用的對象。
玉階生白露
夜久侵羅襪