一、Collection接口

1.特點

Collection實現子類可以存放多個元素，每個元素可以是Object；

有些Collection的實現類，可以存放重復的元素，有些不可以；

有些Collection的實現類，有些是有序的（List），有些則不是有序（Set）；

Collection接口沒有直接的實現子類，通過其子接口List和Set來實現的。

2.方法

add ： 添加單個元素；

remove ： 刪除指定元素；

contains ： 查找元素是否存在；

size ： 獲取元素個數；

isEmpty ： 判斷是否為空；

clear ： 清空；

addAll ： 添加多個元素；

containaAll ：查找多個元素是否都存在；

removeAll ： 刪除多個元素。

3.遍歷

Iterator（迭代器）（不推薦使用）

增強 for 循環

二、List

1.特點

List集合類中元素有序（即添加和取出順序一致），且可重復；

List集合中的每個元素都有其對應的順序索引，即支持索引；

List容器中的元素都對應一個整數型的序號記錄其在容器中的位置，根據序號存取容器中的元素；

List常用接口有 ArrayList、LinkedList、Vector。

2.方法

void add (int index,Object ele) ：在index位置插入ele元素；

boolean addAll (int index,Collection eles) ：從index位置開始將eles集合中的所有元素添加進來；

Object get (int index) ：獲取指定index位置的元素；

int indexOf (Object obj) ：返回obj在集合中首次出現的位置；

int lastIndexOf (Object obj) ：返回obj在集合中末次出現的位置；

Object remove (int index) ：移除指定index位置的元素，并返回此元素；

Object set (int index,Object ele) ：設置指定index的位置的元素為ele，相當于是替換；

List subList (int fromIndex,int toIndex) ：返回從fromIndex到toIndex位置的子集合。

3.遍歷

Iterator（迭代器）（不推薦使用）

增強 for 循環

普通for循環

4.實現

ArrayList、LinkedList、Vector的比較：

三、ArrayList

1.概述

底層實現：實現了 List 接口，基于動態數組。

特點：有序、可重復、動態大小。

初始容量：10

擴充機制：1.5倍（內部通過 grow() 方法完成擴容）

訪問速度：時間復雜度為 O(1)，隨機訪問速度快。

增刪速度：時間復雜度為 O(n)，插入和刪除速度較慢，尤其是在列表中間插入或刪除時，因為需要移動大量元素。

線程安全性：不是線程安全的。

常用場景：適用于頻繁讀取而不頻繁插入或刪除的場景。

2.構造方法

ArrayList() ?????????????????? // 默認構造方法，創建一個容量為 10 的空列表 ArrayList(int initialCapacity) // 創建一個指定初始容量的空列表 ArrayList(Collection<? extends E> c) // 創建一個包含指定集合元素的列表

3.常用方法

add(E e)：將指定元素添加到列表的末尾。

add(int index, E element)：將指定元素添加到指定位置。

get(int index)：返回指定索引處的元素。

set(int index, E element)：用指定元素替換指定位置的元素。

remove(int index)：刪除指定位置的元素，并返回該元素。

remove(Object o)：刪除列表中第一次出現的指定元素，如果元素不存在則返回 false。

clear()：刪除列表中的所有元素。

size()：返回列表中元素的數量。

isEmpty()：如果列表為空，返回 true。

contains(Object o)：判斷列表中是否包含指定元素。

indexOf(Object o)：返回指定元素第一次出現的索引，找不到返回 -1。

lastIndexOf(Object o)：返回指定元素最后一次出現的索引。

toArray()：將列表轉換為一個普通數組。

toArray(T[] a)：將列表轉換為指定類型的數組。

4.線程安全

使用 Collections.synchronizedList() 方法：

List<String> list = Collections.synchronizedList(new ArrayList<>())

使用 CopyOnWriteArrayList()方法（是一個線程安全的變體，適合讀多寫少的場景）：

List<String> list = new CopyOnWriteArrayList<>()

四、Vector

1.概述

底層實現：實現了 List 接口，并繼承自 AbstractList 類，基于動態數組，類似于 ArrayList。

特點：有序、可重復、動態大小。

初始容量：10

擴充機制：2倍（內部通過 grow() 方法完成擴容/可指定增量）

訪問速度：時間復雜度為 O(1)，隨機訪問速度快。

增刪速度：時間復雜度為 O(n)，插入和刪除速度較慢。

線程安全性：線程安全，因為所有的方法都是同步的。

常用場景：適用于需要線程安全且不特別關注性能的場景。由于同步的開銷，相較于 ArrayList 性能會有所下降。

// 創建一個初始容量為 5，容量增量為 3 的 Vector Vector<Integer> vector = new Vector<>(5, 3);

2.構造方法

Vector() ?????????????????? // 默認構造方法，創建一個容量為 10 的空向量 Vector(int initialCapacity) // 創建一個指定初始容量的空向量 Vector(int initialCapacity, int capacityIncrement) // 創建一個指定初始容量和擴展大小的空向量 Vector(Collection<? extends E> c) // 創建一個包含指定集合元素的向量

3.常用方法

add(E e)：將指定元素添加到向量的末尾；

add(int index, E element)：將指定元素插入到指定位置；

addElement(E obj)：將指定元素添加到向量的末尾（ Vector特有方法）；

get(int index)：返回指定位置的元素；

set(int index, E element)：用指定元素替換指定位置的元素；

elementAt(int index)：返回指定位置的元素（Vector特有方法）；

firstElement()：返回向量中的第一個元素；

lastElement()：返回向量中的最后一個元素；

remove(int index)：刪除指定位置的元素，并返回該元素；

remove(Object o)：刪除列表中第一次出現的指定元素；

removeElement(Object obj)：刪除指定的元素；

removeAllElements()：刪除所有元素；

size()：返回向量的大小，即元素的個數；

isEmpty()：如果向量為空，返回 true；

contains(Object o)：判斷向量中是否包含指定的元素；

indexOf(Object o)：返回指定元素第一次出現的索引，找不到返回 -1；

lastIndexOf(Object o)：返回指定元素最后一次出現的索引；

toArray()：將向量轉換為一個普通數組；

toArray(T[] a)：將向量轉換為指定類型的數組；

iterator()：返回一個迭代器，用于遍歷向量。

五、LinkedList

1.概述

底層實現：基于鏈表，由一系列的節點（Node）組成，每個節點包含兩個部分。

數據部分：存儲實際的數據。

指針部分：指向下一個節點的引用（或者在雙向鏈表中，指向前一個節點和下一個節點的引用）。

特點：有序，可重復，動態大小，內存開銷大。

訪問速度：隨機訪問速度較慢，需要從頭開始遍歷。

增刪速度：插入和刪除速度較快，只需更改指針而不移動元素。

線程安全性：不是線程安全的。

常用場景：適用于頻繁插入和刪除操作的場景。

2.基本類型

單向鏈表：

每個節點有一個數據部分和一個指向下一個節點的指針。鏈表的末尾節點的指針指向 null。

雙向鏈表：

每個節點有兩個指針：一個指向下一個節點，另一個指向前一個節點。

循環鏈表：

單向鏈表或雙向鏈表的變體，末尾節點指向頭節點（而不是 null），形成一個環。

3.操作

插入：

在頭部插入（頭插法）、在尾部插入（尾插法）、在指定位置插入。

刪除：

刪除頭節點、刪除尾節點、刪除指定位置的節點。

查找：

查找鏈表中的元素，可以通過遍歷鏈表逐一比較每個節點的值。

更新：

更新鏈表中的某個節點的值，首先找到該節點，再修改其數據部分。

4.時間復雜度

插入和刪除操作：

? 在鏈表的頭部插入或刪除：O(1)

? 在鏈表的尾部插入或刪除：O(1)（但如果沒有尾指針則需要 O(n)）

在中間插入或刪除：

? O(n)（需要遍歷到特定位置）

查找操作：

? O(n)（必須遍歷鏈表才能找到特定元素）

訪問操作：

? O(n)（無法直接通過索引訪問，必須從頭開始遍歷）

六、Set

1.特點

無序（添加和取出的順序不一致），沒有索引；

不允許重復元素，所以最多包含一個null；

Set的常用實現類有：HashSet、LinkedHashSet和TreeSet。

2.遍歷

Iterator（迭代器）（不推薦使用）

增強 for 循環

3.線程安全

CopyOnWriteArraySet（基于 CopyOnWriteArrayList）

4.實現

HashSet、LinkedHashSet、TreeSet和CopyOnWriteArraySet比較：

七、HashSet

1.概述

底層實現：基于哈希表（HashMap）實現，使用哈希算法來存儲元素。

特點：無序、不可重復，高效。

初始容量：16 ????

負載因子：0.75

擴充機制：條目數 > 容量 × 負載因子，哈希表將會自動增加桶的數量，一般是當前容量的兩倍（rehashing），會重新計算所有現有元素的存儲位置。

存儲規則：存儲的元素不可重復，元素在 HashSet 中沒有順序，即元素存儲的順序不一定與插入順序相同。

增刪速度：一般為時間復雜度O(1)，最壞為O(n)。

線程安全性：線程不安全。

場景：適用于需要高效地添加、刪除和查找元素，并且不關心元素的順序。

2.哈希值和哈希沖突

? HashSet 使用元素的 hashCode() 方法來決定元素的存儲位置。如果兩個不同的元素有相同的哈希值，就會發生哈希沖突。為了減少沖突，HashSet 會使用鏈表或紅黑樹等結構來存儲具有相同哈希值的元素。通過 equals() 方法判斷兩個元素是否相等。

hashCode()：返回一個整數值，表示對象的哈希值。這個哈希值用于決定對象在哈希表中的存儲位置。

equals()：用于比較兩個對象是否相等。

3.常用方法

add(E e)：將指定元素添加到集合中；

remove(Object o)：從集合中移除指定元素，如果集合中包含該元素；

contains(Object o)：檢查集合中是否包含指定元素o；

size()：返回集合中元素的數量；

isEmpty()：檢查集合是否為空；

clear()：清空集合中的所有元素。

八、LinkedHashSet

1.概述

底層實現：繼承HashSet，實現了Set接口；結合了哈希表和鏈表的特性。

特點：插入有序、不可重復、性能低于HashSet。

初始容量：16 ????負載因子：0.75

擴充機制：同HashSet。

存儲規則：根據元素的 hashCode 值來決定元素的存儲位置，同時使用鏈表維護元素的次序。

查增刪速度：平均情況下為 O(1)。

線程安全性：線程不安全。

場景：維護元素的插入順序、去重并保留順序、性能要求不高，但需要順序。

2.構造方法

// 創建一個空的 LinkedHashSet，默認初始容量 16，負載因子 0.75 LinkedHashSet<E> set1 = new LinkedHashSet<>(); // 創建一個指定初始容量的 LinkedHashSet LinkedHashSet<E> set2 = new LinkedHashSet<>(int initialCapacity); // 創建一個指定初始容量和負載因子的 LinkedHashSet LinkedHashSet<E> set3 = new LinkedHashSet<>(int initialCapacity, float loadFactor); // 使用一個現有的集合創建一個 LinkedHashSet LinkedHashSet<E> set4 = new LinkedHashSet<>(Collection<? extends E> c);

3.常見方法

add(E e)：添加元素；

remove(Object o)：刪除指定元素；

contains(Object o)：是否存在；

size()：返回元素的數量；

clear()：清空集合；

isEmpty()：是否為空；

iterator()：返回一個迭代器，遍歷集合；

forEach()：使用 forEach() 方法遍歷集合。

九、TreeSet

1.概述

底層實現:基于紅-黑樹（一種自平衡的二叉查找樹）實現。

特點：有序、不可重復、高效、支持 NavigableSet 接口。

存儲規則:存儲的元素不可重復，元素有序,按照自然順序或者指定的比較器進行排序。如果元素是自定義對象，則需要實現 Comparable 接口或者提供 Comparator。

增刪速度：時間復雜度 O(log n)。

線程安全性：線程不安全。

場景：適用于需要元素有序存儲，并且支持自然順序或者自定義排序規則。

2.底層解析

紅黑樹具有以下特性：

每個節點要么是紅色，要么是黑色。

根節點始終是黑色的。

每個葉子節點（NIL）是黑色的。

如果一個紅色節點有子節點，那么該子節點必須是黑色的。

從任何節點到其所有后代葉節點的路徑上，必須包含相同數量的黑色節點。

3.常見操作和方法

add(E e)：添加元素；

remove(Object o)：刪除指定元素；

contains(Object o)：檢查指定元素是否存在；

size()：返回元素數量；

first()：返回集合中的第一個元素，即最小的元素；

last()：返回集合中的最后一個元素，即最大的元素；

headSet(E toElement)：返回一個視圖，小于 toElement 的所有元素；

tailSet(E fromElement)：返回一個視圖，大于等于 fromElement 所有元素；

subSet(E fromElement, E toElement)：返回一個視圖，包含在 fromElement 和 toElement 之間的元素；

pollFirst()：移除并返回最小元素（即第一個元素）；

pollLast()：移除并返回最大元素（即最后一個元素）。

十、CopyOnWriteArrayList

?是Java中一個線程安全的List實現類，屬于 java.util.concurrent包。與常見的 ArrayList 相比，CopyOnWriteArrayList 的一個顯著特點是寫操作時會復制數組，從而保證線程安全。

1.概述

底層數據結構：動態數組，通過復制數組的方式來實現對集合的寫操作。

對于寫操作，會創建一個新的內部數組，然后將數據復制到這個新數組中，修改操作只會作用于這個新數組。這意味著寫操作的成本較高。

主要特點：有序、可重復，讀操作不受影響，寫操作代價較高。

初始容量：0 (可指定)

時間復雜度：讀：O(1)或O(n)，其他：O(n)。

線程安全性：線程安全。

應用場景：適用于對并發讀有較高需求，但寫操作較少的場景，如緩存、事件監聽、日志記錄等。

2.構造方法

// 創建一個空的 CopyOnWriteArrayList CopyOnWriteArrayList<E> list = new CopyOnWriteArrayList<>(); // 創建一個包含指定元素的 CopyOnWriteArrayList CopyOnWriteArrayList<E> list2 = new CopyOnWriteArrayList<>(Collection<? extends E> c); // 創建一個包含指定容量的 CopyOnWriteArrayList CopyOnWriteArrayList<E> list3 = new CopyOnWriteArrayList<>(Object[] array);

3.常見操作和方法

add(E e)：將元素添加到末尾；

remove(Object o)：刪除指定的元素；

get(int index)：獲取指定索引位置的元素；

set(int index, E element)：替換指定位置的元素，實際上是通過復制數組來實現的，性能開銷較大；

size()：返回元素個數；

contains(Object o)：是否包含指定元素；

clear()：清空所有元素，實際上是通過創建一個新的空數組實現的；

iterator()：返回一個迭代器，該迭代器支持并發讀取；

forEach()：遍歷集合。

3.優缺點

優點：CopyOnWriteArrayList 提供了高效的并發讀操作，適用于讀多寫少的場景，能保證線程安全。

缺點：由于寫操作的開銷較大，因此不適用于寫操作頻繁的場景。

十一、CopyOnWriteArraySet

? 是一個線程安全的集合類，基于 CopyOnWriteArrayList 實現，用于提供高效的讀取操作和線程安全的寫入操作。

? 與 HashSet 和 TreeSet 等傳統集合不同，它采用 Copy-On-Write（寫時復制）策略，意味著每次對集合進行修改（如添加或刪除元素）時，都會復制底層的數組，并將修改應用到新數組中，而不是直接修改原數組。這使得 CopyOnWriteArraySet 特別適合于讀多寫少的場景。

1.概述

底層數據結構：基于CopyOnWriteArrayList，動態數組。實現了 Set 接口。

主要特點：無序、不可重復，高效的讀操作，寫操作代價較高

時間復雜度：讀O(1)或O(n)，寫O(n)。

線程安全性：線程安全。

應用場景：讀多寫少的應用、需要線程安全的應用、高并發環境。

2.常用操作

添加元素 (add(E e))；

刪除元素 (remove(Object o))；

檢查元素是否存在 (contains(Object o))；

獲取集合大小 (size())；

清空集合 (clear())；

迭代器 (iterator())。

十二、Collections

? 是 Java 提供的一個工具類，位于 java.util 包中，包含了多個靜態方法，旨在對集合框架中的集合對象進行操作和增強功能。它提供了對集合的排序、查找、同步化、反轉、填充等操作的支持，簡化了集合類的使用和操作。

1.排序

升序排序：

sort(List<T> list)

List<Integer> list = Arrays.asList(5, 2, 8, 1, 4); Collections.sort(list); // [1, 2, 4, 5, 8]

根據指定的比較器 Comparator 對列表進行排序：

sort(List<T> list, Comparator<? super T> c)

List<String> list = Arrays.asList("banana", "apple", "cherry"); Collections.sort(list, Comparator.reverseOrder()); // ["cherry", "banana", "apple"]

2.查找最大值和最小值

（1）返回集合中的最大/小元素，依據元素的自然順序：

max(Collection<? extends T> coll)

min(Collection<? extends T> coll)

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5); Integer max = Collections.max(list); // 5 Integer min = Collections.min(list); // 1

（2）根據給定的比較器返回集合中的最大/小元素：

max(Collection<? extends T> coll, Comparator<? super T> comp)

min(Collection<? extends T> coll, Comparator<? super T> comp)

List<String> list = Arrays.asList("apple", "banana", "cherry"); String max = Collections.max(list, Comparator.reverseOrder()); // "cherry" String min = Collections.min(list, Comparator.reverseOrder()); // "apple"

3.反轉和旋轉

反轉列表中元素的順序：

reverse(List<?> list)

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5); Collections.reverse(list); // [5, 4, 3, 2, 1]

將列表中的元素按指定距離旋轉。正數表示向右旋轉，負數表示向左旋轉：

rotate(List<?> list, int distance)

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5); Collections.rotate(list, 2); // [4, 5, 1, 2, 3]

4.填充和替換

用指定的對象填充整個列表中的元素：

fill(List<? super T> list, T obj)

List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c")); Collections.fill(list, "x"); // ["x", "x", "x"]

替換列表中所有等于 oldVal 的元素為 newVal：

replaceAll(List<T> list, T oldVal, T newVal)

List<String> list = new ArrayList<>(Arrays.asList("apple", "banana", "apple")); Collections.replaceAll(list, "apple", "orange"); // ["orange", "banana", "orange"]

5.線程安全集合

返回一個線程安全的列表，所有的操作都會通過同步來確保線程安全：

synchronizedList(List<T> list)

List<Integer> list = new ArrayList<>(); List<Integer> synchronizedList = Collections.synchronizedList(list);

返回一個線程安全的集合，所有操作都會通過同步來確保線程安全：

synchronizedSet(Set<T> s)

Set<Integer> set = new HashSet<>(); Set<Integer> synchronizedSet = Collections.synchronizedSet(set);

返回一個線程安全的映射，所有操作都會通過同步來確保線程安全：

?synchronizedMap(Map<K, V> m)

Map<String, Integer> map = new HashMap<>(); Map<String, Integer> synchronizedMap = Collections.synchronizedMap(map);

6.空集合和常量集合

（1）返回一個空列表。返回的列表是不可修改的：

emptyList() 、emptySet()

List<String> emptyList = Collections.emptyList(); // [] Set<String> emptySet = Collections.emptySet(); // []

（2）返回一個空映射。返回的映射是不可修改的：

emptyMap()

Map<String, String> emptyMap = Collections.emptyMap(); // {}

（3）返回一個只包含指定元素的不可修改的列表：

singletonList(T o)、singleton(T o)

List<String> singletonList = Collections.singletonList("apple"); // ["apple"] Set<String> singletonSet = Collections.singleton("apple"); // ["apple"]

（4）返回一個只包含一個映射的不可修改的映射：

singletonMap(K key, V value)

Map<String, String> singletonMap = Collections.singletonMap("key", "value"); // {"key"="value"}

7. 其他常用方法

（1）shuffle(List<?> list)

隨機打亂列表中的元素。

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5); Collections.shuffle(list); // 列表順序會隨機改變

（2）unmodifiableList(List<? extends T> list)

返回一個不可修改的列表，修改會拋出 UnsupportedOperationException。

List<String> list = Arrays.asList("apple", "banana", "cherry"); List<String> unmodifiableList = Collections.unmodifiableList(list);

（3）unmodifiableSet(Set<? extends T> s)

返回一個不可修改的集合，修改會拋出 UnsupportedOperationException。

Set<String> set = new HashSet<>(Arrays.asList("apple", "banana")); Set<String> unmodifiableSet = Collections.unmodifiableSet(set);

（4）unmodifiableMap(Map<? extends K, ? extends V> m)

返回一個不可修改的映射，修改會拋出 UnsupportedOperationException。

Map<String, String> map = new HashMap<>(); map.put("key1", "value1"); Map<String, String> unmodifiableMap = Collections.unmodifiableMap(map);

十三、其他API工具

1.Guava

? 提供了豐富的集合框架、緩存、字符串處理、并發工具等功能。

（1）增強的集合類型

ImmutableList / ImmutableSet / ImmutableMap: 不可變集合，線程安全且不易被修改。

Multiset: 允許重復元素的集合，可以統計元素的出現次數。

Multimap: 鍵到多個值的映射，支持一個鍵對應多個值。

BiMap: 雙向映射，鍵和值都是唯一的。

（2）緩存

Cache: 提供高效的緩存實現，支持過期策略和容量限制。

（3）字符串處理

Joiner: 簡化字符串拼接的操作。

Splitter: 方便地將字符串分割成集合。

（4）并發工具

ListenableFuture: 擴展了 Future 的功能，支持回調機制。

RateLimiter: 控制方法調用頻率。

（5）其他實用工具

Optional: 提供對可能為 null 的值的優雅處理，減少 null 引用帶來的問題。

Preconditions: 提供參數檢查工具，確保方法參數的有效性。

2.Apache Commons Collections

（1）主要特性

額外的集合類型：

? Bag: 允許重復元素的集合，并支持計數功能。

? MultiValuedMap: 每個鍵可以對應多個值的映射。

? TreeSortedSet: 有序集合，基于紅黑樹實現。

（2）裝飾器模式

通過裝飾器模式增強已有集合的功能，比如創建只讀集合、同步集合等。

示例：SynchronizedCollection 可以為集合提供線程安全的訪問。

（3）過濾器和轉換器

提供多種過濾器和轉換器，可以對集合進行操作，比如只保留特定條件的元素或轉換元素類型。

（4）集合工具

提供各種靜態方法用于操作集合，如合并、差集、交集等。

示例：CollectionUtils 類提供了很多便利的方法。

（5）快速查找和排序

提供高效的查找和排序算法，特別是對于大量數據的處理。