文章目錄
- 前言
- 一、List類圖
- 二、集合總結
- 1. ArrayList與Vector集合區別
- 2. ArrayList與CopyOnWriteArrayList集合區別
- 3. 時間復雜度 / 空間復雜度
- 4. modCount答疑解惑
- 三、《不講武德系列》- 原始碼分析
- 1. ArrayList
- 2. LinkedList
- 3. Vector
- 4. CopyOnWriteArrayList
- ~~ 碼上福利
前言
業精于勤荒于嬉，行成于思毀于隨；
在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，開始思考…
今天一起來聊一聊 List集合，看到這里，筆者懂，大家莫慌，先來寶圖鎮樓 ~
我勸這位小伙子，耗子尾汁，
咳咳… 相信大家滿腦子的各種List已被這些經典的畫面以及臺詞沖淡了，那么，目的已達到，那我們言歸正傳，對于螢屏前帥氣的猿友們來說，ArrayList，LinkedList，Vector，CopyOnWriteArrayList… 張口就來，閉眼能寫，但是呢，我相信大部分的猿友們并沒有刨根問底真正去看過其原始碼，此時，筆者帥氣的臉龐似有似無洋溢起一抹微笑，畢竟是查看過原始碼的猿，就是那么的不講武德，吃我一記閃電五連鞭，話不多說，來吧，展示…
一、List類圖
二、集合總結
1. ArrayList與Vector集合區別
- 相同點：
-
都實作了List介面；
-
底層采用陣列實作；
- 不同點：
-
執行緒安全方面：
ArrayList執行緒不安全；
Vector執行緒安全；
-
擴容方面：
⑴ ArrayList擴容后是原陣列長度的1.5倍；
⑵ Vector擴容后是原陣列長度的2倍；
-
默認長度方面：
⑴ ArrayList底層陣列默認長度為0；
⑵ Vector底層陣列默認長度為10；
-
擴容增加容量方面：
⑴ ArrayList不支持自定義；
⑵ Vector中可通過有參構造自定義capacityIncrement增長容量；
2. ArrayList與CopyOnWriteArrayList集合區別
- 相同點：
-
都是實作與List介面；
-
底層采用陣列實作;
-
查詢效率高，增刪效率低；
- 不同點：
-
執行緒安全方面：
⑴ ArrayList執行緒不安全；
⑵ CopyOnWriteArrayList集合 add() / remove()方法通過ReentrantLock鎖保證執行緒安全、get()方法執行緒不安全；
-
擴容方面：
⑴ ArrayList擴容后是原陣列長度的1.5倍；
⑵ CopyOnWriteArrayList每次擴容長度為原陣列長度+1；
3. 時間復雜度 / 空間復雜度
-
O(1)：
O(1)就是最低的時間復雜度了，也就是耗時/耗空間與輸入資料大小無關，無論輸入資料增大多少倍，耗時/耗空間都不變， 哈希演算法就是典型的O(1)時間復雜度，在不考慮沖突的情況下，無論資料規模多大，都可以在一次計算后找到目標；
-
O(n)：
時間復雜度為O(n)，就代表資料量增大幾倍，耗時也增大幾倍，比如常見的遍歷演算法， 要找到一個陣列里面最大的一個數，你要把n個變數都掃描一遍，操作次數為n，那么演算法復雜度是O(n)；
-
O(log n)
時間復雜度為O(log n)，當資料增大n倍時，耗時增大log n倍（這里的log是以2為底的，比如，當資料增大256倍時，耗時只增大8倍，是比線性還要低的時間復雜度），二分查找就是O(log n)的演算法，每找一次排除一半的可能，256個資料中查找只要找8次就可以找到目標，
-
各集合復雜度：
-
ArrayList：通過下標查詢為 O(1)，通過遍歷陣列查詢為 O(n)；
-
LinkedList：O(n)，雖然原始碼中在查詢前進行折半查詢，但原理還是全表查找，故為O(n)；
-
Vector：通過下標查詢為 O(1)，通過遍歷陣列查詢為 O(n)；
-
CopyOnWriteArrayList：通過下標查詢為 O(1)，通過遍歷陣列查詢為 O(n)；
4. modCount答疑解惑
相信猿友在《不講武德系列》各篇集合原始碼分析中都常見到 modCount這個變數，到底什么意思呢，一起分析下：
-
含義：
用來記錄當前集合操作次數；
比如在ArrayList，每一次呼叫add / remove / clear等方法時都會記錄一次；
那 modCount 到底是作用來做什么的呢？這里牽扯到另一個重要的概念，Fail-Fast 機制：
-
含義：
Fail-Fast 機制，快速失敗機制；
當某一個執行緒在使用迭代器的程序中，有其他執行緒修改了modCount，此時會通過modCount是否變化來判斷當前執行緒安全問題，如modCount發生變化則拋出ConcurrentModificationException例外；
注意：此機制出現在使用迭代器的程序中，建議大家使用回圈時優先選用迭代器遍歷，
三、《不講武德系列》- 原始碼分析
1. ArrayList
不講武德，一起聊聊List集合之ArrayList
2. LinkedList
不講武德，一起聊聊List集合之LinkedList
3. Vector
不講武德，一起聊聊List集合之Vector
4. CopyOnWriteArrayList
不講武德，一起聊聊List集合之CopyOnWriteArrayList
~~ 碼上福利
大家好，我是猿醫生：
在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，掃碼一起學習吧…
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/243345.html
標籤：其他
下一篇：命令列快速開啟應用程式