arrarylist
ArrayList集合是Collection和List介面的實現類。底層的資料結構是陣列。
它是執行緒不安全！
ArrayList的特點
單列集合
：
對應與Map集合來說【雙列集合】
有序性
：
存入的元素和取出的元素是順序是一樣的 元素可以重複
：
可以存入兩個相同的元素
含帶索引的方法
：
陣列與生俱來含有索引【下角標】
ArrayList預設容量是10，jdk8之中是懶載入，初始化容量是0，新增第一個元素會擴容到10，最大容量是2^31 - 1 - 8。減8是為了儲存ArrayList集合的基本資訊。
ArrayList為什麼查詢快、增刪慢
arraryLiat底層是一個object物件陣列，增刪查也是透過對陣列操作來實現的。
陣列是一種，查詢快、增刪慢！ 查詢資料是透過索引定位，查詢任意資料耗時均相同。查詢效率賊高！
刪除資料時，要將原始資料刪除，同時後面的每個資料前移。刪除效率就比較低！
新增資料，在新增陣列的位置加入陣列，同時在陣列後面位置後移以為！新增效率也低！
arraryLsit中add方法
建立arraryList若是沒有傳入初始長度。會先建立一個空陣列集合。在新增元素的時候判斷當前陣列的容量是否有儲存空間，如果沒有則會擴容到初始容量。
如果有傳參的話，會判斷傳入的引數是否符合規範，符合的話就直接建立。所以若是集合固定長度，這種方法更好一點。
ArrayList擴容原理
add方法先要確保陣列的容量足夠，防止陣列已經填滿還往裡面新增資料造成陣列越界：
如果陣列空間足夠，直接將資料新增到陣列中
如果陣列空間不夠了，會擴容1。5倍擴容。
擴容是將
原始陣列copy新陣列中，同時向新陣列後面加入資料
ArrayList執行緒安全問題及解決方案
導致ArraryList執行緒不安全的原因是它的add方法，add方法做了兩大步驟
判斷elementData陣列容量是否滿足需求
在elementData對應位置上設定值
假設容量足夠，當兩個執行緒同時進入第一步的時候，這時候都滿足，但是真正新增值的時候，慢一點的執行緒會覆蓋前面那個執行緒的值。
假設只有一個容量剩餘，當兩個執行緒同時進入第一步的時候，這時候都滿足。但是快一點的執行緒新增成功後。慢一點的執行緒就會陣列下標越界的錯。
解決方案
使用Vector集合，Vector集合是執行緒安全的。淘汰了的。
使用Collections。synchronizedList。它會自動將我們的list方法進行改變，最後返回給我們 一個加鎖了List。（不合適，慢）
使用JUC中的CopyOnWriteArrayList類進行替換。（最佳）
LinkedList
LinkedList是List 介面的連結列表實現的雙向連結串列。它實現所有可選的列表操作，並且允許所有元素（包括 null ）插入。除了實現 List 介面外， LinkedList 類還為在列表的開頭及結尾 get 、 remove 和 insert 元素提供了統一 的命名方法。這些操作允許將連結列表用作堆疊、佇列或雙端佇列。
特點 ：
有序性 ： 存入和取出的順序是一致的
元素可以重複 ： 含有帶索引的方法
獨有特點 ： 資料結構是連結串列，可以作為棧、佇列或者雙端佇列！
LinkedList的資料結構
原始碼：
可以看到其中是一個Node類，以內部類的形式存在於LinkedList中。包含前一個節點和後一個節點的指向。
連結串列資料結構的特點 ：
查詢慢，增刪快！
連結串列資料結構基本構成，是一個node類 每個node類中，有上一個節點【prev】和下一個節點【next】
連結串列一定存在至少兩個節點，first和last節點 如果LinkedList沒有資料，irst和last都是為null
LinkedList沒有最大容量個初始容量，也不需要擴容，理論只要記憶體夠大，可以存無限的值
LinkedLis查詢慢（相對arraryList）
看到雖然用了二分法，但是之後還是用了迴圈，需要遍歷查詢。還有就是連結串列結構在記憶體中不是連線在一起的，地址是任意的。查詢起來指標需要移動。
增加快
刪除快
HashMap
HashMap是Map介面的實現類，基於雜湊表結構實現的。其主要特點是以key-value儲存形式儲存數 據，即用與存放鍵值對。HashMap 的操作不是同步的，這意味著它執行緒不安全。
hashMap特點：
無序性 ： 存入和取出元素順序不一致
唯一性 ： 鍵key是唯一的 可存null ： 鍵和值位置都可以是null，但是鍵位置只能是一個null
資料結構 ： 資料結構控制的是鍵key而非值value！
HashMap儲存資料過程和資料結構
hashMap的資料結構在jdk1。8前後是不一樣的，
jdk1。8之前由連結串列 + 陣列構成，jdk1。8之後改為連結串列+陣列+紅黑樹構成。陣列是hashMap的主體，連結串列和紅黑樹是為了解決雜湊衝突而存在的。
雜湊衝突是指兩個物件呼叫的hashCode方法計算的雜湊碼一致，雜湊碼就睡導致計算的陣列索引值相同。
JDK1。8 以後在解決雜湊衝突時有了較大的變化，當連結串列長度大於閾值（8）並且當前陣列的長度大於64時，此時此索引位置上的所有資料改為使用紅黑樹儲存。 JDK1。8引入紅黑樹大程度優化了HashMap的效能，為了保證HashSet集合元素的唯一，需要根據物件的hashCode和equals方法一起判斷。
HashMap初始化容量是16，如果要指定容量，必須是2的n次冪。將資料均勻的
分佈在位桶陣列上，因為hashMap元素具體放在陣列哪個位置是經過key值得hash&（length-1） 計算得到的。
&位運算
：相同的二進位制數位上，都是1的時候，結果為1，否則為零。
但是，當傳入的初始值不是2的n次冪，hashMap原始碼也會幫忙糾錯。它會透過位移運算和或運算之後，並且是離傳入值最近的2的n次冪數字。
為什麼
HashMap的載入因子0.75預設初始值是16
載入因子loadFactor的預設值為0。75f是官方給出的一個比較好的臨界值。
載入因子越大趨近於1，陣列中的存放的資料（Node）也就越多，也就越稠密，也就是會讓連結串列的長 度增加。
載入因子越小趨近於0，陣列中的存放的資料（Node）也就越少，也就越稀疏。也就是會讓連結串列的長 度不會太長。
HashMap的紅黑樹轉換邊界值詳解
HashMap的紅黑樹轉換邊界值是8，是一個定義在HashMap中的成員變數。在HashMap官方註釋說明：理想的情況下，優秀的hash演算法，會讓所有桶的節點的分佈頻率會遵循泊松分佈。我們可以看到，一個 桶中連結串列長度達到8個元素的機率為0。00000006，幾乎是不可能的事件。因為資料被均勻分佈在每個桶 中，所以幾乎不會有桶中的連結串列長度會達到閾值！
所以8這個資料是根據機率統計決定的。
HashMap擴容機制
當hashMap集合中實際儲存的值超過臨界值或則hashMap中單個桶中連結串列長度超過8並且陣列長度沒有超過64時也會擴容。
擴容的時候，會將原陣列中桶內的節點透過rehash，均勻分散在了新的陣列的桶中。rehash時會呼叫resize方法，重新計算集合資料在新陣列中的位置，主要演算法是：（n-1）&hash；n代表陣列長度。這個演算法比較巧妙。擴容前後，只是多了一個bit位。所以節點要麼就在原來的位置，要麼就被分配到“原位置+舊容量”這個位置。
