李文軒 2019-03-19
聲明：這是本人學(xué)習(xí)極客時間的Java核心36講的筆記，有侵權(quán)請聯(lián)系我。
Vector, ArrayList, LinkedList 有何區(qū)別？
這三個類都實(shí)現(xiàn)了集合框架里的
List，即有序集合。具體功能都有相似的地方，比如，提供按照位置進(jìn)行定位、添加或者刪除的操作，都提供迭代器以遍歷其內(nèi)容。-
不同在于具體設(shè)計(jì)、行為、性能和性能安全等。
- Vector
- 線程安全的動態(tài)數(shù)組
- 內(nèi)部是用對象數(shù)組來保存數(shù)據(jù)
- 可自動增加容量，每次提高一倍
- ArrayList
- 動態(tài)數(shù)組
- 不是線程安全的，性能高很多
- 可自動增加容量，每次增加50%
- LinkedList
- 雙向鏈表
- 不是線程安全的
- 不需要擴(kuò)容，size=capacity
- Vector
-
應(yīng)用場景分析
Vector和ArrayList作為動態(tài)數(shù)組，都很適合需要大量隨機(jī)訪問的場合。但是除了對尾部數(shù)據(jù)的操作，大部分（除尾部以外所有元素）操作性能都很差。LinkedList的節(jié)點(diǎn)插入與刪除的性能都很好，可是隨機(jī)訪問性能較差。-
讀寫機(jī)制：
-
ArrayList在插入元素時，若超過當(dāng)前數(shù)組預(yù)定義的最大值時，數(shù)組需要擴(kuò)容；擴(kuò)容過程需要調(diào)用底層System.ArrayCopy()方法進(jìn)行數(shù)組復(fù)制。在刪除元素時并不會減小容量（若需要，可調(diào)用trimToSize()方法）。在查找元素時要遍歷數(shù)組，對于非null的元素采取equals()的方式尋找。 -
LinkedList在插入元素時，先創(chuàng)建一個Entry對象，并更新此元素和前后元素的引用。查找元素時要遍歷鏈表。刪除元素時，要遍歷鏈表，找到元素，并更新前后元素的引用。 -
Vector與ArrayList僅在插入元素時有不同。默認(rèn)下，Vector初創(chuàng)時是一個容量為10的數(shù)組，capacityIncrement為0。當(dāng)需要擴(kuò)容時，先檢查capacityIncrement；若此值大于0，數(shù)組大小將擴(kuò)容到size+capacityIncremnet；若小于等于0（默認(rèn)值），將擴(kuò)大到原先的兩部。
-
Java的集合框架（Collection）
- Map并沒有出現(xiàn)在Java的
Collection里 -
java.util.concurrent這里也先不涉及
三大類集合
- List，有序集合，提供了方便訪問、插入、刪除
- Set，不允許重復(fù)元素，即不存在兩個對象
equals返回true。 - Queue/Deque，Java提供的標(biāo)準(zhǔn)隊(duì)列結(jié)構(gòu)的實(shí)現(xiàn)。支持 FIFO 和 LIFO 等特定行為。
Set
TreeSet 支持自然順序訪問；添加、刪除、包含等操作要相對低效 (log(n)時間)。
HashSet 利用哈希算法；若哈希散列正常，可以提供常數(shù)時間的添加、刪除、包含等操作；但不保證有序。
LinkedHashSet 在內(nèi)部構(gòu)建了一個記錄插入順序但雙向鏈表，從而提供了按照插入順序遍歷的能力；也保證了常數(shù)時間的添加、刪除、包含等操作；操作性能略低于HashSet，因?yàn)橐S護(hù)鏈表。
遍歷元素時，
HashSet性能受自身容量影響。LinkedHashSet由于內(nèi)部鏈表，遍歷性能與元素?cái)?shù)量有關(guān)。
線程安全問題
其實(shí)集合框架也支持并發(fā)編程的場景
實(shí)現(xiàn)方式就是每個基本方法（get、set、add）都添加
synchronized都符合迭代時
fail-fast行為，當(dāng)發(fā)生意外當(dāng)并發(fā)修改時，盡早拋出ConcurrentModificationException異常。Collection 的工具類
static <T> List<T> synchronizedList(List<T> list)
- 運(yùn)用
List list = Collections.synchronizedList(new ArrayList());
排序
- 對于原始數(shù)據(jù)類型，現(xiàn)在所使用的是 雙軸快速排序（
Dual-Pivot QuickSort），是一種改進(jìn)的快速排序算法 - 對于對象數(shù)據(jù)類型，目前是TimSort，思想上是一種歸并和二分插入排序（binarySort）結(jié)合的優(yōu)化排序算法。
- 可有調(diào)用
parallelSort方法，充分利用多核處理器的能力，底層實(shí)現(xiàn)基于fork-join框架
