（八）Java-Collection

一、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）快速查找和排序

提供高效的查找和排序算法，特别是对于大量数据的处理。