集合簡介
疊代器
Iterable接口
Iterator 接口
Collection接口
List體系
體系結構
List接口
ArrayList源碼解析
Map體系
Map接口
HashMap源碼分析
HashMap的常見問題
hashCode()、equals()
Set體系
常見實作類
集合周遊
集合工具類 Collections
數組、list的互相轉換
使用集合的注意點
jdk源碼版本1.8。
體系結構圖隻列出了常見的接口、類，白色的是接口，黃色的類（包括抽象類）。
集合用于存儲指定類型的元素，部分集合還實作了棧、隊列、樹等資料結構。
集合的兩個根接口
Collection 單列集合
Map 雙列集合
Map内置了2個單例集合分别存儲key、value，key唯一辨別一個鍵值對，使用Set存儲，不可重複。
集合的實作類都重寫了toString()方法。
iterable 可疊代的，繼承了此接口的接口、類都具有可疊代的能力
Iterable接口提供了3個方法，對應3種疊代方式
iterator 疊代器
forEach循環
spliterator()，這個是流式操作中的方法
iterator 疊代器，可通過疊代器疊代元素
Iterator 接口在擷取疊代器後，提供了2種疊代方式
while循環 + hasNext() + next()
forEachRemaining()
此外還提供了在疊代中删除底層集合元素的 remove() 方法。
jdk提供了 fail-fast 機制，如果在周遊集合時，其它線程修改了正在周遊的集合，會快速失敗，抛出異常。
如果要保證集合的線程安全，盡量使用juc中線程安全的集合。
這篇博文中涉及到的Collection、List、Set、Map接口，都可以仔細看下，學習一下如何設計接口。
相關問題：讓你設計一個 list | set | map | 集合，你會怎麼設計
Collection接口主要做了2件事
繼承了 Iterable 接口，具有疊代能力。Map中存儲key、value的2個集合也是Collection體系的，也具有疊代能力。
定義了操作集合本身、單個元素、批量操作、流式操作的一些通用方法。
List 元素有序、可重複，有序是指元素有對應的下标，可通過下标檢索元素，元素可重複是建立在元素有序的基礎上的。
List的實作類衆多，圖中隻列出了常見的，添加元素時List的常見實作類都可以添加值為null的元素，如果某些實作類不允許添加值為null的元素，則add(null)會抛出空指針異常。
RandomAccess隻是一個标記接口，标示具有随機通路能力，一般都是使用内置數組來實作随機通路。
實作 Cloneable 接口，是為了使用根類Object的clone()拷貝集合，但這隻是一種淺拷貝。
ArrayList、Vector、Stack
ArrayList、Vector都是基于數組實作的，内置了一個數組，添加元素時如果數組容量不足都會動态擴容。
Vector有一個子類Stack，用于實作棧，Vector、Stack中的很多方法都使用 synchronized 修飾，線程安全，ArrayList則不是線程安全的。
如果不需要保證線程安全，盡量用ArrayList代替Vector；需要要保證線程安全，盡量用juc下的類代替Vector。
LinkedList
LinkedList是基于雙向連結清單實作的list，本身還可以作為（雙端）隊列使用。
連結清單本身是按添加順序進行存儲，但不具有下标，是以使用了 AbstractSequentialList 來增加下标操作。AbstractSequentialList 相當于擴充卡，在連結清單的基礎上增加下标操作。
ArrayList、Vector、LinkedList的比較
ArrayList、Vector基于數組，随機存取，查找元素速度快，但增删元素時要移動大量元素，速度慢，适合以讀為主、增删不頻繁的場景；LinkedList基于雙向連結清單，查找元素要周遊連結清單，速度慢，但增删元素隻需修改引用，速度快，适合增删元素頻繁的場景。
空間使用率 ArrayList、Vector 不如 LinkedList，但這2個類都提供了 trimToSize() 方法用于修剪集合，用容量正合适的數組來存儲元素。
ArrayList、LinkedList不是線程安全的，Vector線程安全。維護線程安全有額外開銷，且Vector缺點很多，一般不用，如果不要求線程安全，盡量用 ArrayList 代替 Vector。
List中的元素有序（可通過下标操作），List接口定義了常用的下标操作，比如
add()、remove()、set() 在指定位置上添加|删除|更新元素
indexOf() 擷取指定元素對應的下标
subList() 擷取指定區間上的子集合
ArrayList的部分源碼
Arrays.copyOf()、System.arraycopy() 都可以複制數組元素
ArrayList的擴容機制
計算過程如下
如果建立 ArrayList 時沒有顯式指定初始容量，則第一次添加元素時會取預設容量、所需容量中的較大者作為所需容量；
如果所需容量大于原容量的1.5倍，則取所需容量，否則取原容量的1.5倍
如果目标容量大于容量上限（ Integer.MAX_VALUE - 8 ），則取 Integer.MAX_VALUE
ensureCapacity() 手動擴容
ArrayList、Vector這些基于數組的list都提供了手動擴容的 ensureCapacity() 方法，上面的幾個擴容相關的方法都是private，這個是public，暴露出來的手動擴容方法。
如果即将要向ArrayList、Vector、Stack中添加大量元素，可以先調用 ensureCapacity() 一次性擴容，以減少自動擴容次數，提高性能
HashMap：使用哈希表存儲元素，使用的哈希值是key的
LinkedHashMap：在哈希表的基礎上，增加了一個雙向連結清單維護元素的添加順序。元素的增改删查都是通過哈希表進行，效率高，更新哈希表時會同步更新到連結清單，連結清單隻用于周遊。
SortedMap：元素按指定的順序進行存儲。Sorted 有序，指的是存儲有序，并沒有關聯下标。可以用函數式接口 Comparator 指定排序規則。
NavigableMap：可導航的map，可導航指的是提供了一些方法，可以擷取key大于、小于指定值的所有鍵值對，可以擷取開頭、末尾部分的鍵值對，可以擷取首、尾鍵值對，可以擷取指定區間上的所有鍵值對。
TreeMap：使用紅黑樹存儲元素。可以構造方法中用 Comparator 接口指定排序規則，未指定時預設使用自然排序。
Hashtable：t是小寫，和HashMap一樣都是使用哈希表存儲元素，但Hashtable線程安全，隻是缺點較多，很少使用。
Properties：主要用于加載、解析properties檔案
EnumMap：以枚舉類的執行個體作為key
TreeMap可指定排序方式，LinkedHashMap使用雙向連結清單維護添加順序，TreeMap、LinkedHashMap在某種程度上也可以認為是有序的，隻不過不是 list 這種元素關聯下标的有序。
性能比較
TreeMap：内部要維護紅黑樹，增删元素性能差
Hashtable：要保證線程安全，有額外開銷，性能差
LinkedHashMap：在HashMap的基礎上要維護一個雙向連結清單，增删性能比HashMap稍微差一些，但正由于雙向連結清單，周遊時速度往往比HashMap快。
HashMap：元素的增删查改性能都不錯，周遊時需要先過濾掉哈希表中的空桶，速度往往比LinkedHashMap慢。
關于Dictionary
Hashtable在繼承Dictionary的同時實作了Map，Dictionary、Map基本是一樣的，包含了大量的相同方法
NOTE: This class is obsolete. New implementations should implement the Map interface, rather than extending this class.
官方在注釋中提示，Dictionary将被廢棄，使用Map代替。同時繼承Dictionary、實作Map隻是作為過渡，後續版本不再 extends Dictionary，直接implements Map。
HashMap、Hashtable的聯系與差別
相同點：都是使用哈希表存儲元素
HashMap線程不安全，Hashtable提供的方法基本都使用 synchronized 修飾，線程安全
HashMap的key、value都可以為null，Hashtable的key、value都不能為null
Hashtable缺點很多，基本不用，官方建議：如果不需要保證線程安全，盡量使用HashMap代替Hashtable；如果需要保證線程安全，盡量使用juc中的 ConcurrentHashMap 代替 Hashtable。
Map使用内部接口Entry來封裝鍵值對。
成員變量
靜态内部類
預留給 LinkedHashMap 重寫的空方法
HashMap在自身的元素增删改操作中，分别調用了以下對應的方法，這些方法在HashMap中都是空實作，都是作為擴充點留給LinkedHashMap重寫的。
LinkedHashMap在HashMap的基礎上要維護連結清單，對這3個方法的重寫都是更新連結清單，用于在更新哈希表後同步更新連結清單。
hash()、tableSizeFor()
構造方法
hash系列集合都可以通過構造方法指定初始容量、負載因子。
負載因子較大時，節省記憶體空間，但容易發生哈希沖突，元素存儲效率降低；負載因子較小時，哈希沖突頻率低，元素存儲效率高，但存在大量空桶、浪費空間，如果不是LinkedHashMap這種有雙向連結清單的，周遊時還需要周遊所有的桶，要判斷大量的空桶，周遊速度慢。
預設的負載因子 0.75 是時間、空間的折中，一般使用預設的負載因子即可。
盡量預估元素數量，建立hash系列集合時指定初始容量，避免頻繁重哈希，以提升性能，初始容量一般設定為：預估的元素數量 / 0.75，結果向上取整。
put()方法
put()流程
對key進行hash計算，傳給 putVal() 方法，後續都是 putVal() 在操作
如果數組為空，則先 resize() 初始化數組
計算數組下标（存儲位置）
如果該位置尚未存儲元素，則直接存儲到該位置；如果該位置已經存儲了紅黑樹或連結清單，則把元素添加到紅黑樹中或添加到連結清單尾部，添加到連結清單中後，如果連結清單長度大于8，會将連結清單轉換為紅黑樹。如果已存在相同的key，不再進行添加，會先記錄原來的元素，并替換value。
如果是添加操作，會把哈希表結構修改次數+1、已存儲的元素個數+1，如果已存儲的元素個數超過重哈希門檻值，則進行重哈希，對數組進行擴容。
更新操作傳回的是原來的value，添加操作傳回的是null。
resize() 擴容|重哈希
resize()除了擴容，還具有初始化功能。
HashMap擴容機制
如果原容量達到容量上限，則重哈希門檻值直接取 Integer.MAX_VALUE，不再進行擴容，直接傳回原數組，任其發生hash沖突；
如果原容量大于等于預設容量，且擴容為原容量的2倍後仍小于最大容量，則将容量、重哈希門檻值都擴大為原來的2倍；
如果原容量為0（負數不合法），且原重哈希門檻值大于0，則初始化容量為原重哈希門檻值；
否則（原容量、原重哈希門檻值都為0），初始化容量為預設容量（16），重哈希門檻值為預設容量*預設負載因子再取整（12）。
如果新的重哈希門檻值為0，則以單精度浮點數的方式重新計算重哈希門檻值。
建立新數組，重新計算存儲位置，将原數組各個bucket中存儲的元素複制到新數組中，并傳回新數組。
get()方法
get()流程
對key進行hash計算，傳給 getNode() 方法擷取對應的鍵值對，再從鍵值對中擷取value，不存在對應的鍵值對時傳回null
getNode() 擷取對應的鍵值對時，先計算數組下标，嘗試比對該位置存儲的第一個元素，第一個元素比對就直接傳回，如果該位置存儲了多個元素，則根據節點類型，從紅黑樹中擷取比對的鍵值對，或周遊連結清單擷取比對的鍵值對。
開發中用過哪些集合
list：ArrayList、LinkedList
set：HashSet、LinkedHashSet
map：HashMap、LinkedHashMap
juc：CopyOnWriteArrayList、CopyOnWriteArraySet、ConcurrentHashMap
HashMap的資料結構，和之前版本的差別
jdk6、7：數組+連結清單，使用連結清單解決hash沖突
jdk8：數組+連結清單+紅黑樹，連結清單太長會影響哈希表的性能，是以引入了紅黑樹，連結清單長度大于8時會轉換為紅黑樹，紅黑樹節點數量小于6時會退化為連結清單。總體來看，jdk8的HashMap比jdk7的性能高。
HashMap是如何解決哈希沖突的
使用拉鍊法，将哈希位址相同的元素存儲在連結清單中。
HashMap使用的雜湊演算法是怎麼實作的
在key的hashCode基礎上進行了位移、異或計算，位移16位是時間、空間上折中。
HashMap的容量為什麼要是2的n次方
n是哈希表容量（數組長度），hash是 hash(key) 的結果。
将容量指定為2的次方，主要是為了計算哈希位址（數組下标）時的性能考慮
HashMap計算哈希位址（建構的哈希函數）實際使用的是 除留餘數法 <code>hash % n</code>，這種方式可以使計算得到的哈希位址比較均勻、分散。
n是2的次方時，<code>hash % n</code> 可以轉換為 <code>(n - 1) & hash</code>，位運算 & 比取模 % 高效得多。
添加到連結清單中時是插入到連結清單頭部還是尾部
jdk8之前：采用頭插法，插傳入連結表頭部
jdk8及之後：頭插法可能發生死循環問題，是以從jdk8開始采用尾插法，插傳入連結表尾部，以解決死循環問題。
HashMap的死循環問題
HashMap不是線程安全的，多線程同時往同一個HashMap的同一個連結清單中插入元素時，可能出現環形連結清單，進而導緻 get() 擷取元素時出現死循環。
在多線程環境下，盡量用 ConcurrentHashMap 代替 HashMap。
相關問題
有沒有重寫過 hashcode()、equals()？是怎麼重寫的？
為什麼重寫 equals() 時必須重寫 hashCode()？
為什麼要使用hashCode | hashCode的作用
hashCode是專門給哈希表設計的，用于擷取擷取哈希碼值，傳回一個 int 型的整數作為哈希碼值，在實作哈希表中起着重要作用。
根類Object的hashCode()是native方法，把對象的記憶體位址轉換為int型的整數作為hashCode傳回，如果對象的記憶體位址相同，則hashCode()傳回的哈希碼值也相同。
hashCode主要有2個作用
計算元素在哈希表中的存儲位置（數組下标）
搭配 equals() 用于判斷哈希表中是否已存在相同的key|元素
為什麼要重寫hashCode()、equals()
不重寫hashCode()、equals()，預設使用根類Object的這2個方法，情況如下
2個User對象都是new出來的，是不同的對象，它們的hashCode不同，equals()比較記憶體位址為true，是以都會放到map中。
複用User對象，使用的都是堆中的同一個對象，記憶體位址相同 => hashCode相同、equals()比較記憶體位址為true => 哈希表會認為key相同，是以第二個put()是更新操作，隻更新對應的value，不會作為新的鍵值對添加。
從業務邏輯的角度來說，userId都變了，這顯然是一個不同的使用者，put()應該做添加而非更新。
重寫hashCode()、equals()主要是基于業務邏輯上的考慮，確定使用同一個java對象存儲不同實體對象的屬性時也能被添加到哈希表中。
jdk自帶的引用類型（包括String）都重寫了 equals()、hashCode()，隻需給要存儲到哈希表中的、自定義的類重寫。這裡的存儲到哈希表中指的是 HashMap中的key、HashSet中的元素，如果隻是作為HashMap的value存儲，則不必重寫。
重寫equals()時為什麼要重寫hashCode()
因為是根據 hashCode、equals 共同判斷哈希表中是否已存在相同的元素|key，隻通過equals()無法判斷，還需要借助 hashCode。此外根類Object約定
equals() 判斷2個對象等價時，這2個對象的 hashCode() 傳回的哈希碼值也應該相同
是以重寫equals()時也應該重寫hashCode，確定在equals()傳回true時，這2個對象傳回的hashCode也相同。
重寫hashCode()、equals()的基本原則|要求
equals() 判斷2個對象等價，則這2個對象的 hashCode() 傳回的哈希碼值也應該相同。
這是個充分不必要條件，equals()為true，則hashCode一定相同；hashCode相同，equals()不一定為true。
這也是約定，可在Object類的 hashCode()、equals() 的方法注釋上檢視這些内容。
重寫hashCode()、equals()示例
以上使用的 <code>id.hashCode()</code>、<code>id.equals(another.id)</code> 代碼都不健壯，id可能為null，可能發生NPE，使用前應該判斷是否為null，或者使用工具類 Objects 中的方法代替
本質都是一樣的
Objects的hashCode、equals()源碼如下
HashSet
HashSet是通過内置的HashMap實作的，key存儲元素，value指向同一個Object對象。
LinkedHashSet
繼承自HashSet，實質是使用 LinkedHashMap實作，哈希表+雙向連結清單。
TreeSet
TreeSet實質是通過TreeMap實作的，鍵值對的value都指向同一個Object對象。
EnumSet
使用内置的 Enum<?>[ ] 存儲枚舉類執行個體。EnumSet并沒有繼承或者内置 EnumMap，但實作思路和EnumMap差不多。
EnumSet：使用數組存儲元素，不需要維護連結清單、樹之類的資料結構，性能高。
HashSet：使用哈希表存儲元素，增改删查性能不錯
LinkedHashSet：在哈希表的基礎上還要維護雙向連結清單，增改删查速度比HashSet稍微差一些，但正因為用雙向連結清單維護元素的添加順序，周遊比HashSet快，可以做到按元素添加順序進行周遊。
TreeSet：内部要維護紅黑樹，開銷大。
這些set都不是線程安全的，多線程操作時需要用 Collections.synchronizedXxx() 轉換為線程安全的集合，或者使用juc提供的CopyOnWriteArraySet、ConcurrentSkipListSet。
單例集合可以直接使用疊代器，Map可以先擷取key、value、Entry組成的單例集合，再擷取對應的疊代器。
stream 流式操作
forEach
所有集合都可使用
增強的for循環
如果list這種元素關聯了下标的，可以使用下标進行疊代
size() 擷取已存儲的元素個數。
Collections提供了大量的集合操作方法，包括查找最值、二分搜尋、統計元素出現次數、替換、排序、反序、同步等，常見的如下
單例集合轉數組：單例集合本身都提供了 toArray() 方法可以轉換為數組
數組轉list：工具類 Arrays.asList()
1、周遊
周遊集合時，不能使用集合本身的删除方法來删除集合元素，會直接抛出異常，可以使用疊代器的remove()來删除疊代器最近一次傳回的元素，或使用stream來疊代集合。
使用疊代器周遊集合時，如果循環體内部又嵌套了疊代器，容易出問題，嵌套疊代盡量用增強for循環代替疊代器。
2、集合為空的判斷
集合為空、空集合是2個概念，集合為空是指集合自身沒有初始化、是null，空集合是指集合自身已初始化、但沒有存儲元素。空集合用 isEmpty() 進行判斷。
3、字元串、list的下标操作
通過下标操作時，一定要考慮下标是否合法、是否會越界。
使用 subXxx(start, end) 提取區間時，都是左閉右開 [start, end) ，如果 start==end ，傳回的是空集合、空串。
使用 subXxx() 逐個區間提取時，最後一批的終止坐标應該是元素個數，即 list.size() 或 str.length()，這樣才不會遺漏最後一個元素，實際并沒有用到最後一個坐标，不會發生越界。