天天看點

【重難點】【Java集合 03】ArrayList、LinkedList、 Vector 和 Stack 的差別、CopyOnWriteArrayList【重難點】【Java集合 03】ArrayList、LinkedList 和 Vector 的差別、util 包下的 List、CopyOnWriteArrayList一、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 數組中,然後再釋放互斥鎖,達到保護資料的目的