手撕Java系列-集合框架详解，List，Set，Queue，Deque，Map，并发集合，集合工具类，Stream API

1. 接口：定义了集合的基本操作，比如添加、删除元素等。
2. 实现：这些接口的具体实现类，提供了具体的数据结构来支持集合的操作。
3. 算法：对集合进行搜索、排序等操作的方法。

1. 集合框架主要接口

Collection：这是所有集合类的根接口，它定义了集合的基本操作，如添加(add)、移除(remove)等方法。

• List：有序集合，允许重复元素。可以按索引访问元素。常见的实现有ArrayList、LinkedList。
• Set：不允许包含重复元素的集合。常见的实现有HashSet、TreeSet、LinkedHashSet。
• Queue：队列，通常用于保存一组将要处理的元素。主要实现包括LinkedList作为双端队列，以及PriorityQueue作为优先级队列。
• Deque：双端队列，可以从两端插入或移除元素。LinkedList实现了这个接口。

Map：映射关系，存储键值对，每个键最多只能映射到一个值。常见的实现有HashMap、TreeMap、LinkedHashMap、Hashtable等。

Gitee链接地址，建议收藏，后续我会对专栏进行整理，每篇文章进行校正和调整，然后统一存放在gitee仓库中

2. 集合框架常见实现类

2.1. List 实现类

Java集合框架中的List接口代表一个有序的集合，用户可以精确控制每个元素插入的位置。实现List接口的主要类包括：

1. ArrayList

   • 基于动态数组实现。
   • 支持快速随机访问（通过索引访问）。
   • 插入和删除操作可能会比较慢，因为这些操作可能需要移动大量元素。
   • 线程不同步；如果在多线程环境中使用，需要外部同步或使用Collections.synchronizedList方法进行包装。
   • 初始容量较小，但会随着元素的增加而自动增长。
   • 适用于读取操作远多于写入操作的情况。

2. LinkedList

   • 基于双向链表实现。
   • 在列表中间插入和删除元素非常高效，不需要移动其他元素。
   • 随机访问性能较差，因为需要从头或尾开始遍历到指定位置。
   • 实现了Deque接口，因此可以用作双端队列，也非线程安全。
   • 适用于应用程序需要频繁地在列表中插入和删除元素的场景。

3. Vector

   • 类似于ArrayList，也是基于动态数组实现。
   • 所有方法都是同步的，因此它是线程安全的。
   • 性能通常比ArrayList差，因为同步机制带来了额外的开销。
   • 和ArrayList一样支持随机访问。
   • 早期版本的Java中，当需要线程安全的列表时使用。现在推荐使用ArrayList并配合适当的同步机制，或者使用CopyOnWriteArrayList。

4. Stack

   • 继承自Vector，是一个后进先出（LIFO）的数据结构。
   • 提供了标准的栈操作，如push(), pop(), peek()等。
   • 由于它直接继承自Vector，所以所有的方法都是同步的。
   • 虽然它可以用于栈操作，但由于它继承自Vector，通常建议使用Deque接口提供的ArrayDeque作为更现代的选择。

5. CopyOnWriteArrayList

   • 基于数组实现，但在每次修改时都会创建一个新的副本。
   • 线程安全，适合读多写少的情况。
   • 写操作成本较高，因为它涉及到整个数组的复制。
   • 迭代器不会抛出ConcurrentModificationException，即使在迭代过程中列表被修改。
   • 适用于并发读取非常高且写入相对较少的情况。

6. AbstractList, AbstractSequentialList

   • 它们是抽象类，提供了部分List接口的默认实现。
   • AbstractList为基于随机访问的列表提供了一些基本实现。
   • AbstractSequentialList则为顺序访问的列表提供了一些基本实现。
   • 通常不直接实例化，而是用来帮助开发新的列表实现。

选择合适的List实现类主要取决于你的具体需求，比如是否需要线程安全性、对随机访问的需求程度以及插入/删除操作的频率等。例如，在单线程环境下并且经常进行随机访问时，ArrayList通常是最佳选择；而在需要频繁插入/删除元素的情况下，则应考虑使用LinkedList。对于高并发读取低并发写的场景，CopyOnWriteArrayList可能更为合适。

2.2.Set 实现类

Java集合框架中的Set接口代表一个不包含重复元素的集合。Set接口继承自Collection接口，并且添加了额外的约束，即不允许存储重复的对象。以下是Set接口的主要实现类及其特点和适用场景：

1. HashSet

   • 基于哈希表（HashMap）实现。
   • 不保证元素的顺序，即元素的排列顺序可能会随着集合的修改而变化。
   • 提供了常数时间性能 O(1) 的基本操作（如添加、删除和查找）。
   • 允许使用 null 值。
   • 非线程安全；如果需要线程安全，可以使用 Collections.synchronizedSet 或者 CopyOnWriteArraySet。
   • 适用于不需要关心元素的顺序，并且需要高效的插入、删除和查找操作的场景。

2. LinkedHashSet

   • 基于哈希表和双向链表实现。
   • 维护了一个运行于所有条目的双向链表，这个链表定义了迭代顺序，该顺序通常就是元素被插入到集合中的顺序。
   • 插入、删除和查找操作的时间复杂度为 O(1)。
   • 保持插入顺序。
   • 允许使用 null 值。
   • 非线程安全。
   • 适用于需要保持元素的插入顺序并且不需要排序的场