ArrayList
0. 通過(guò)數(shù)組實(shí)現(xiàn)
1. add蜻韭，會(huì)進(jìn)行擴(kuò)容（當(dāng)前數(shù)組大小 + （當(dāng)前數(shù)組大小 / 2））
2. remove臀栈，刪除對(duì)應(yīng)的下標(biāo)月腋，并通過(guò)System.arraycopy進(jìn)行數(shù)組平移
3. 不能使用for循環(huán)進(jìn)行數(shù)組的刪除妄迁，因?yàn)閯h除數(shù)組會(huì)平移疗韵，應(yīng)該使用迭代器
4. 多線程并發(fā)不能使用ArrayList兑障，要使用CopyOnWriteArrayList
5. 添加多，查找少應(yīng)該使用LinkedList，避免頻繁copyLinkedList
0. 通過(guò)雙向鏈表實(shí)現(xiàn)
1. add直接在末尾添加一個(gè)Node
2. remove流译，通過(guò)遍歷記數(shù)找到對(duì)應(yīng)的下標(biāo)逞怨。index < (size >> 1)如果是前半段則順序查找，如果是后半段則倒序查找
3. 修改多福澡，應(yīng)該用LinkedList叠赦。查詢多則使用ArrayListCopyOnWriteArrayList
1. 底層原理與ArrayList相似
2. 線程安全
3. 每次數(shù)組操作都是通過(guò)拷貝新數(shù)組進(jìn)行操作，然后再賦值回去
4. add革砸，通過(guò)ReentrantLock + 數(shù)組拷貝 + volatile實(shí)現(xiàn)線程安全除秀。通過(guò)ReentrantLock加鎖，volatile實(shí)現(xiàn)內(nèi)存共享算利，數(shù)組拷貝觸發(fā)內(nèi)存地址變更册踩，同步其他線程
5. 盡量使用addAll和removeAll，來(lái)進(jìn)行批量操作效拭，因?yàn)槊看蝍dd或remove都會(huì)進(jìn)行一次數(shù)組拷貝暂吉。hashMap
0. 數(shù)組 + 鏈表 + 紅黑樹(shù)實(shí)現(xiàn)
1. 當(dāng)鏈表長(zhǎng)度大于8鏈表轉(zhuǎn)為紅黑樹(shù)，當(dāng)紅黑樹(shù)大小小于等于6時(shí)允耿，變回鏈表借笙。（紅黑樹(shù)的出現(xiàn)是為了解決鏈表過(guò)長(zhǎng)的問(wèn)題）
2. put的實(shí)現(xiàn)過(guò)程：1. 對(duì)key計(jì)算Hash值（計(jì)算公式：hash = (h = key.hashCode()) ^ (h >>> 16)） 2. 通過(guò)計(jì)算((n - 1) & hash)獲得數(shù)組的下標(biāo)，如果對(duì)應(yīng)的下標(biāo)中沒(méi)有值较锡，則直接進(jìn)行賦值业稼。如果有值，意味著發(fā)生了hash沖突蚂蕴，需要解決沖突低散。 3. 出現(xiàn)沖突時(shí)首先判斷key是否相等，內(nèi)存地址是否相等骡楼。如果都相等熔号，那就直接覆蓋。 4. 如果key不相等鸟整，則先判斷當(dāng)前的node引镊，如果是紅黑樹(shù)，則根據(jù)紅黑樹(shù)的規(guī)則直接插入篮条。如果是鏈表弟头，則直接插入鏈表末尾。如果鏈表長(zhǎng)度大于等于8且數(shù)組長(zhǎng)度大于64涉茧，則擴(kuò)展為紅黑樹(shù)赴恨。
3. 為什么鏈表長(zhǎng)度是8？
因?yàn)楫?dāng)鏈表長(zhǎng)度為8時(shí)伴栓，鏈表的沖突概率已經(jīng)很小了伦连。為了處理特殊情況（大于等于8）就轉(zhuǎn)為紅黑樹(shù)雨饺。雖然紅黑樹(shù)的訪問(wèn)復(fù)雜度是O(LogN)，鏈表的是O(n)惑淳，紅黑樹(shù)比鏈表訪問(wèn)要快额港，但是紅黑樹(shù)的內(nèi)存占用是鏈表的2倍。
4. 擴(kuò)容算法（參考）
jdk1.7：在插入元素時(shí)汛聚，判斷如果當(dāng)前元素(鍵值對(duì))個(gè)數(shù)超過(guò)閾值锹安，并且出現(xiàn)了hash沖突，此時(shí)會(huì)進(jìn)行擴(kuò)容倚舀，將數(shù)組變?yōu)樵瓉?lái)的兩倍叹哭，并且所有元素重新計(jì)算hash，放到新的數(shù)組中痕貌。因?yàn)?.7中元素的鏈表插入是采用的頭插法风罩，所以多線程下會(huì)出現(xiàn)死循環(huán)的問(wèn)題。
jdk1.8：擴(kuò)容是發(fā)生在插入元素之后舵稠。如果插入的鏈表后超升，鏈表個(gè)數(shù)是7個(gè)，那么就會(huì)進(jìn)行擴(kuò)容哺徊，如果數(shù)組長(zhǎng)度超過(guò)64室琢，則當(dāng)前鏈表改為紅黑樹(shù)，如果沒(méi)有超過(guò)64落追，則數(shù)組的大小變?yōu)樵瓉?lái)的2倍盈滴。如果鏈表個(gè)數(shù)沒(méi)有達(dá)到7個(gè)，則判斷hashMap的元素個(gè)數(shù)是否超過(guò)閾值(size > 0.75 * 16)轿钠，如果超過(guò)了巢钓，同樣進(jìn)行擴(kuò)容（之后擴(kuò)大數(shù)組的容量，不會(huì)轉(zhuǎn)換紅黑樹(shù)）疗垛。
5. 調(diào)用 new HashMap(1000) 構(gòu)造方法症汹，內(nèi)部還會(huì)擴(kuò)容嗎？
會(huì)的贷腕，因?yàn)镠ashMap的構(gòu)造參數(shù)中還有一個(gè)加載因子（0.75）背镇，所以實(shí)際上容量不到1000，后續(xù)還需要擴(kuò)容泽裳。加載因子的作用是判斷HashMap內(nèi)部是否需要擴(kuò)容芽世。即當(dāng)內(nèi)部容量達(dá)到1000 * 0.75 = 750之后，就會(huì)擴(kuò)容诡壁，而不是達(dá)到1000才擴(kuò)容。擴(kuò)容之后荠割，空間變大了妹卿，hash沖突降低了旺矾。ArrayMap
0. 由兩個(gè)數(shù)組組成的Map
1. 數(shù)組1存放hash值，數(shù)組2存放key+value
2. get夺克，通過(guò)計(jì)算hash找到對(duì)應(yīng)的下標(biāo)箕宙，再通過(guò)二分查找，找到hash對(duì)應(yīng)的key/value
3. put铺纽，通過(guò)計(jì)算hash找到數(shù)組2中的下標(biāo)柬帕，如果對(duì)應(yīng)下標(biāo)沒(méi)有值，直接插入狡门。如果有值陷寝，則插入到后面，后面的數(shù)組統(tǒng)一后移
4. 緩存機(jī)制：緩存數(shù)組長(zhǎng)度為4或者8的數(shù)組其馏，每個(gè)上限10個(gè)凤跑。目的：為了減少頻繁創(chuàng)建和銷(xiāo)毀數(shù)組對(duì)象。ConcurrentHashMap
0. 通過(guò)volatile修飾Map叛复，保證其在內(nèi)存中的可見(jiàn)性仔引，確保線程同步
1. 在putValue時(shí)，通過(guò)for循環(huán)和CAS自旋確保不會(huì)出現(xiàn)同步問(wèn)題
2. 在擴(kuò)容時(shí)褐奥，會(huì)通過(guò)狀態(tài)確保擴(kuò)容過(guò)程
3. 在操作節(jié)點(diǎn)時(shí)咖耘，通過(guò)synchronized鎖住節(jié)點(diǎn)-
LinkedBlockingQueue和ArrayBlockingQueue
在隊(duì)列存放滿后，存數(shù)據(jù)的線程會(huì)進(jìn)入阻塞撬码，等待空間儿倒。
在隊(duì)列為空時(shí)，取數(shù)據(jù)的線程會(huì)進(jìn)入阻塞耍群，等待新的數(shù)據(jù)到來(lái)义桂。
通過(guò)AQS的await進(jìn)行阻塞，通過(guò)signal進(jìn)行喚醒名字 底層實(shí)現(xiàn) 容量大小 LinkedBlockingQueue 使用鏈表實(shí)現(xiàn) Int.MAX_VALUE ArrayBlockingQueue 使用數(shù)組實(shí)現(xiàn) 需要初始化時(shí)指定容量 LRU數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)（https://mp.weixin.qq.com/s?__biz=MzU4NDE3MTEyMA==&mid=2247490403&idx=1&sn=dd361a87d74eec4ca9ef97efe016c906）
雙向鏈表 + HashMap
參考資料：
面試官: 我必問(wèn)的容器知識(shí)點(diǎn)! - 掘金 (juejin.cn)
Carson帶你學(xué)Java：手把手帶你源碼分析 HashMap 1.7
重讀源碼之 SparseArray 和 ArrayMap
