1. ArrayList
   0. 通過數(shù)組實現(xiàn)
   1. add，會進行擴容（當(dāng)前數(shù)組大小 + （當(dāng)前數(shù)組大小 / 2））
   2. remove，刪除對應(yīng)的下標(biāo)，并通過System.arraycopy進行數(shù)組平移
   3. 不能使用for循環(huán)進行數(shù)組的刪除，因為刪除數(shù)組會平移，應(yīng)該使用迭代器
   4. 多線程并發(fā)不能使用ArrayList，要使用CopyOnWriteArrayList
   5. 添加多，查找少應(yīng)該使用LinkedList，避免頻繁copy

2. LinkedList
   0. 通過雙向鏈表實現(xiàn)
   1. add直接在末尾添加一個Node
   2. remove，通過遍歷記數(shù)找到對應(yīng)的下標(biāo)。index < (size >> 1)如果是前半段則順序查找，如果是后半段則倒序查找
   3. 修改多，應(yīng)該用LinkedList。查詢多則使用ArrayList

3. CopyOnWriteArrayList
   1. 底層原理與ArrayList相似
   2. 線程安全
   3. 每次數(shù)組操作都是通過拷貝新數(shù)組進行操作，然后再賦值回去
   4. add，通過ReentrantLock + 數(shù)組拷貝 + volatile實現(xiàn)線程安全。通過ReentrantLock加鎖，volatile實現(xiàn)內(nèi)存共享，數(shù)組拷貝觸發(fā)內(nèi)存地址變更，同步其他線程
   5. 盡量使用addAll和removeAll，來進行批量操作，因為每次add或remove都會進行一次數(shù)組拷貝。

4. hashMap
   0. 數(shù)組 + 鏈表 + 紅黑樹實現(xiàn)
   1. 當(dāng)鏈表長度大于8鏈表轉(zhuǎn)為紅黑樹，當(dāng)紅黑樹大小小于等于6時，變回鏈表。（紅黑樹的出現(xiàn)是為了解決鏈表過長的問題）
   2. put的實現(xiàn)過程：1. 對key計算Hash值（計算公式：hash = (h = key.hashCode()) ^ (h >>> 16)） 2. 通過計算((n - 1) & hash)獲得數(shù)組的下標(biāo)，如果對應(yīng)的下標(biāo)中沒有值，則直接進行賦值。如果有值，意味著發(fā)生了hash沖突，需要解決沖突。 3. 出現(xiàn)沖突時首先判斷key是否相等，內(nèi)存地址是否相等。如果都相等，那就直接覆蓋。 4. 如果key不相等，則先判斷當(dāng)前的node，如果是紅黑樹，則根據(jù)紅黑樹的規(guī)則直接插入。如果是鏈表，則直接插入鏈表末尾。如果鏈表長度大于等于8且數(shù)組長度大于64，則擴展為紅黑樹。
   3. 為什么鏈表長度是8？
   因為當(dāng)鏈表長度為8時，鏈表的沖突概率已經(jīng)很小了。為了處理特殊情況（大于等于8）就轉(zhuǎn)為紅黑樹。雖然紅黑樹的訪問復(fù)雜度是O(LogN)，鏈表的是O(n)，紅黑樹比鏈表訪問要快，但是紅黑樹的內(nèi)存占用是鏈表的2倍。
   4. 擴容算法（參考）
   jdk1.7：在插入元素時，判斷如果當(dāng)前元素(鍵值對)個數(shù)超過閾值，并且出現(xiàn)了hash沖突，此時會進行擴容，將數(shù)組變?yōu)樵瓉淼膬杀?，并且所有元素重新計算hash，放到新的數(shù)組中。因為1.7中元素的鏈表插入是采用的頭插法，所以多線程下會出現(xiàn)死循環(huán)的問題。
   jdk1.8：擴容是發(fā)生在插入元素之后。如果插入的鏈表后，鏈表個數(shù)是7個，那么就會進行擴容，如果數(shù)組長度超過64，則當(dāng)前鏈表改為紅黑樹，如果沒有超過64，則數(shù)組的大小變?yōu)樵瓉淼?倍。如果鏈表個數(shù)沒有達到7個，則判斷hashMap的元素個數(shù)是否超過閾值(size > 0.75 * 16)，如果超過了，同樣進行擴容（之后擴大數(shù)組的容量，不會轉(zhuǎn)換紅黑樹）。
   5. 調(diào)用 new HashMap(1000) 構(gòu)造方法，內(nèi)部還會擴容嗎？
   會的，因為HashMap的構(gòu)造參數(shù)中還有一個加載因子（0.75），所以實際上容量不到1000，后續(xù)還需要擴容。加載因子的作用是判斷HashMap內(nèi)部是否需要擴容。即當(dāng)內(nèi)部容量達到1000 * 0.75 = 750之后，就會擴容，而不是達到1000才擴容。擴容之后，空間變大了，hash沖突降低了。

5. ArrayMap
   0. 由兩個數(shù)組組成的Map
   1. 數(shù)組1存放hash值，數(shù)組2存放key+value
   2. get，通過計算hash找到對應(yīng)的下標(biāo)，再通過二分查找，找到hash對應(yīng)的key/value
   3. put，通過計算hash找到數(shù)組2中的下標(biāo)，如果對應(yīng)下標(biāo)沒有值，直接插入。如果有值，則插入到后面，后面的數(shù)組統(tǒng)一后移
   4. 緩存機制：緩存數(shù)組長度為4或者8的數(shù)組，每個上限10個。目的：為了減少頻繁創(chuàng)建和銷毀數(shù)組對象。

6. ConcurrentHashMap
   0. 通過volatile修飾Map，保證其在內(nèi)存中的可見性，確保線程同步
   1. 在putValue時，通過for循環(huán)和CAS自旋確保不會出現(xiàn)同步問題
   2. 在擴容時，會通過狀態(tài)確保擴容過程
   3. 在操作節(jié)點時，通過synchronized鎖住節(jié)點

7. LinkedBlockingQueue和ArrayBlockingQueue
   在隊列存放滿后，存數(shù)據(jù)的線程會進入阻塞，等待空間。
   在隊列為空時，取數(shù)據(jù)的線程會進入阻塞，等待新的數(shù)據(jù)到來。
   通過AQS的await進行阻塞，通過signal進行喚醒

   名字	底層實現(xiàn)	容量大小
   LinkedBlockingQueue	使用鏈表實現(xiàn)	Int.MAX_VALUE
   ArrayBlockingQueue	使用數(shù)組實現(xiàn)	需要初始化時指定容量

8. LRU數(shù)據(jù)結(jié)構(gòu)實現(xiàn)（https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247490403&idx=1&sn=dd361a87d74eec4ca9ef97efe016c906）
   雙向鏈表 + HashMap

參考資料：
面試官: 我必問的容器知識點! - 掘金 (juejin.cn)
Carson帶你學(xué)Java：手把手帶你源碼分析 HashMap 1.7
重讀源碼之 SparseArray 和 ArrayMap