關(guān)于List虹钮、Set
手畫Collection結(jié)構(gòu)圖（Vector和Stack已經(jīng)廢棄）
集合框架圖.png
Collection思維導圖
Collection下集合的類關(guān)鍵詞
- List 有序廷蓉，可重復集合
- Set 無序愕把，不可重復集合
- Queue 先進先出隊列
- Deque 雙向隊列
- Array 數(shù)組方式實現(xiàn)嵌灰，內(nèi)存上不連續(xù)
- Linked 鏈表方式實現(xiàn)，內(nèi)存上連續(xù)
- CopyOnWrite 采用寫入時復制技術(shù)
- SkipList 采用跳表技術(shù)提高搜索效率
- Concurrent 非阻塞的方式實現(xiàn)線程安全
- Blocking 阻塞方式實現(xiàn)線程安全
Collection下哪些是線程安全的础浮？
- CopyOnWrite系列：CopyOnWriteArrayList帆调、CopyOnWriteArraySet
- Concurrent系列：ConcurrentLinkedQueue、ConcurrentLinkedDeque豆同、ConcurrentSkipListSet
- Blocking系列：ArrayBlockingQueue贷帮、LinkedBlockingQueue、LinkedBlockingDeque诱告、DelayQueue撵枢、SynchronousQueue民晒、PriorityBlockingQueue
ArrayList和LinkedList的差異
- 結(jié)構(gòu)上：ArrayList數(shù)組實現(xiàn)，內(nèi)存連續(xù)锄禽，LinkedList 鏈表實現(xiàn)潜必，內(nèi)存不連續(xù)
- 在隨機訪問上：ArrayList更快
- 插入/刪除：LinkedList更快
ArrayList是如何擴容的
- 計算最小需要空間
- 判斷是否需要擴容
- 擴容到原來的1.5倍
- 使用System.arraycopy方法將數(shù)據(jù)復制到新的內(nèi)存空間
ArrayList擴容因子為什么是1.5倍
真實的倍數(shù)為oldCapacity + (oldCapacity >> 1)，約等于1.5倍沃但，這么設(shè)計應該是出于位運算性能的考慮磁滚。
fast-fail機制
- 對集合的每一次增刪操作都會增加modCount的值
- iterator遍歷集合前會記錄該值
- 調(diào)用next方法時會校驗該值是否發(fā)生改變，如果改變拋出并發(fā)修改異常宵晚。
fast-fail機制常發(fā)生在哪些場景
- 多線程對Util包下集合的并發(fā)操作（可通過使用CopyOnWrite系列類）
- 遍歷集合的同時進行增刪操作（可通過使用Iterator的增刪方法）
- subList后對主列表的增刪垂攘，將導致子列表的遍歷、增淤刃、刪報錯
并發(fā)容器CopyOnWrite系列類
- 讀寫分離晒他，如果是寫操作，則復制一個新集合逸贾，在新集合內(nèi)添加或刪除元素陨仅。待一切修改完成之后，再將原集合的引用指向新的集合
- 擴容的空間代價比較大
- 使用批量添加或刪除方法
- 適用于讀多寫極少的情況
關(guān)于隊列
各隊列特點
| 隊列 | 數(shù)據(jù)結(jié)構(gòu) | 是否有界 | 線程安全 |
|---|---|---|---|
| ArrayBlockingQueue | 數(shù)組 | 有 | ReentrantLock保證出入隊線程安全 |
| LinkedBlockingQueue | 鏈表 | 無 | 出入隊鎖分別使用ReentrantLock |
| DelayQueue | 二叉堆 | 無 | 同上 |
| PriorityBlockingQueue | 二叉堆 | 無 | 同上 |
| SynchronousQueue | 隊列或堆棧 | - | CAS保證出入隊線程安全 |
隊列方法
| 方法名 | 描述 | 備注 |
|---|---|---|
| add | 增加一個元索 | 如果隊列已滿铝侵，則拋出異常 |
| remove | 移除并返回隊列頭部的元素 | 如果隊列為空灼伤，則拋出異常 |
| element | 返回隊列頭部的元素 | 如果隊列為空，則拋出異常 |
| offer | 添加一個元素并返回true | 如果隊列已滿咪鲜，則返回false |
| poll | 移除并返問隊列頭部的元素 | 如果隊列為空狐赡，則返回null |
| peek | 返回隊列頭部的元素 | 如果隊列為空，則返回null |
| put | 添加一個元素 | 如果隊列滿疟丙，則阻塞 |
| take | 移除并返回隊列頭部的元素 | 如果隊列為空颖侄，則阻塞 |
ArrayBlockingQueue 入隊代碼流程
- 獲取鎖
- 判斷是否已滿，滿則等待
- 加入數(shù)組
- 喚醒出隊線程
為什么ArrayBlockingQueue單鎖實現(xiàn)隆敢，而LinkedBlockingQueue是雙鎖发皿。
崔慧？
PriorityBlockingQueue入隊流程
- 獲取鎖
- 自旋判斷隊列容量是否足夠拂蝎，不足時擴容
- 二叉堆排序
- 喚醒出隊線程
PriorityBlockingQueue擴容機制
- 擴容大小，小于64時約為2倍惶室，大于64時約為1.5倍
- 默認大小温自，11
- 通過自旋CAS加鎖后再進行擴容
DelayQueue 入隊流程
- 加鎖
- 加入PriorityBlockingQueue隊列
- 判斷剛加入的是否為隊首
- 是則leader設(shè)置為空，喚醒一個線程
- 釋放鎖
DelayQueue出隊流程
- 加鎖
- 取隊首皇钞，判斷是否到了執(zhí)行時間悼泌，是則喚醒其他線程、釋放鎖并返回
- 如果已經(jīng)有l(wèi)eader夹界，則永久等待
- 如果沒有l(wèi)eader馆里，則晉升為leader，等待直到隊首的執(zhí)行時間
- 釋放鎖
DelayQueue的重點
- 底層依賴PriorityBlockingQueue
- 入隊的數(shù)據(jù)必須實現(xiàn)Delayed接口
- leader的作用,多個消費者線程同時用take方法去取時，只有一個線程能成為leader鸠踪，其他的會由于leader不為空 丙者，而永久等待。
SynchronousQueue的重點
- 容量為0
- 匹配插入線程和移除線程营密，資源從插入線程移交給移除線程
- 有公平模式（先進先出隊列）和非公平模式（先進后出棧）
- 適合作為管道械媒，資源從一個線程傳遞給另一個線程
ConcurrentLinkedQueue 核心
- 不允許null入列，因為尾節(jié)點的定位是通過next是否為null判斷的
- 底層使用cas包裝入列出列安全评汰。
- head節(jié)點跟tail不一定指向頭節(jié)點或尾節(jié)點纷捞，可能存在滯后性。
- size方法是通過遍歷獲取的被去，當同時存在其他線程入隊出隊操作時主儡，該值可能不精確。
