【重難點】【Java集合 03】ArrayList、LinkedList、 Vector 和 Stack 的差別、CopyOnWriteArrayList

【重難點】【Java集合 03】ArrayList、LinkedList 和 Vector 的差別、util 包下的 List、CopyOnWriteArrayList

文章目錄

• 【重難點】【Java集合 03】ArrayList、LinkedList 和 Vector 的差別、util 包下的 List、CopyOnWriteArrayList
• 一、ArrayList、LinkedList、Vector 和 Stack 的差別
• • 1.ArrayList
  • 2.LinkedList
  • 3.Vector
  • 2.Stack
• 二、CopyOnWriteArrayList

一、ArrayList、LinkedList、Vector 和 Stack 的差別

1.ArrayList

ArrayList 是一個動态數組，也是我們最常用的集合。它允許任何符合規則的元素插入（包括 NULL）

ArrayList 的初始容量為 10，随着容器中的元素不斷增加，容器的大小也會随之增加。每次向容器中增加元素的時候都會進行容量檢查，當快溢出時就會進行擴容操作

ArrayList 擅長随機通路，同時 ArrayList 是非同步的

2.LinkedList

LinkedList 是一個雙向連結清單，由于實作的方式不同、LinkedList 不能随機存取，它所有的操作都要按照雙向連結清單執行

LinkedList 是非同步的

3.Vector

Vector 是線程安全的動态數組，它的操作與 ArrayList 幾乎一樣

2.Stack

Stack 繼承自 Vector，實作了一個後進先出的棧

二、CopyOnWriteArrayList

CopyOnWriteList 相當于線程安全的 ArrayList，和 ArrayList 一樣，它是個可變數組。但是和 ArrayList 不同的是，它具有以下特性：

• 它最适合具有以下特征的應用程式：List 大小通常保持很小，隻讀操作遠多于可變操作，需要在周遊期間防止線程間的沖突
• 它是線程安全的
• 可變操作（add、set、remove）的開銷很大，因為需要複制整個數組
• 疊代器支援 hasNext()、next() 等不可變操作，但不支援可變操作
• 使用疊代器進行周遊的速度很快，并且不會與其它線程發生沖突，在構造疊代器時，疊代器依賴于不變的數組快照

CopyOnWrite 沒有采用獨占鎖，而是采用讀寫分離的思想解決線程安全問題。寫線程擷取鎖的時候，其他的線程會阻塞，它的核心是複制思想：

• 當我們往一個容器添加元素的時候，不是直接往目前容器添加，而是先将目前容器進行複制，複制出一個新的容器，然後往新的容器裡添加元素，添加完元素之後，再将原容器的引用指向新的容器

動态數組機制：

• CopyOnWriteList 内部有一個 volatile 數組來儲存資料。在添加、修改或删除資料時會建立一個數組，并将更新後的資料拷貝到建立的數組中，最後再将該數組指派給 volatile 數組。由于它在添加、修改或删除資料時都會建立數組，是以涉及到這些操作時，它的效率很低，如果隻是進行周遊的話，效率比較高

線程安全機制通過 volatile 和互斥鎖實作：

• 通過 volatile 數組儲存資料，一個線程讀取 volatile 時，總能看到其它線程對該 volatile 數組最後的寫入，是以讀到的資料總是最新的
• 通過互斥鎖來保護資料，在添加、修改或删除資料時擷取互斥鎖。在添加、修改或删除之後，先将資料更新到 volatile 數組中，然後再釋放互斥鎖，達到保護資料的目的