蹊源的Java笔记—集合之Collection接口

拼搏现实的明天。 2022-12-18 15:57 190阅读 0赞

# 蹊源的Java笔记—集合之Collection接口 #

## 前言 ##

在`java`中我们最常的数据接口就是集合，在面试的时候最常问的问题也是集合相关的问题，结合自己的面试经验，我做了简单地整理，希望可以能够帮助小伙伴们一二。

**集合之Map接口**可参考我的博客：[蹊源的Java笔记—集合之Map接口][Java_Map]

## 正文 ##

## 集合 ##

**集合**有两个接口组成：`Collection`和`Map`  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]

## Collection接口 ##

**Collection接口有3个子接口分别是：**

*  **List**：有序且元素是可重复的
 *  **Set**：无序并元素是不可重复的
 *  **Queue**：先进先出的线性数据结构，并且只能观察到队首元素.

**List接口**

**List的常用实现类有**:

*  **ArrayList**：底层是通过数组实现的，查询性能高，插入和删除比较慢。它遍历的优势是在于它在内存的连续性决定的。
 *  **LinkedList** ：通过双向链表实现，查询性能略低，但插入和删除性能高，除了实现了`List`接口，还实现了`Queue`接口。
 *  **Vector**：数据结构与`ArrayList`类似，通过`synchronized`来实现线程安全，并且`Stack`栈是实现`Vector`接口的。

**重点知识点：**

1.实现`ArrayList`线程安全的方式

*  使用`synchronized`或者锁
 *  直接使用`Vector`，但jdk1.2官方推荐弃用
 *  使用`Collections.synchronizedList(list)`来实现

2.`ArrayList`的构建与扩容

*  `ArrayList arrayList =new ArrayList()`,默认生成一个容量为0的数组，只有`add()`元素时才会分配默认10的初始容量。
 *  如果当10个容量都满了，就会扩容50%的大小，即到达15的容量。

所以在实际的使用如果存取一个已知大小的数组时，尽可能要设置初始容量，避免触发连续的扩容操作。

3.`ArrayList`插入和删除为什么性能比较差？  
插入和删除都涉及到了数组的`copy`（即数据迁移），操作的位置越在前面，需要`copy`的数组长度就越长。

4.`Vector`为什么会被弃用？  
`Vector`所有的方法都使用了`synchronized`来实现线程安全的，这种在所有方法上都使用了`synchronized`极大影响了整个数据操作的性能，实际上`hashtable`也有类似的问题。所以`ArrayList`在`jdk1.2`后作为`Vector`的替代品。

**Set接口**

**Set的常用实现类有**：

*  **HashSet**:是基于`HashMap`实现的，默认构造函数是构建一个初始容量为16，负载因子为0.75 的`HashMap`。通过重写`equals(Object obj)`方法和`hashCode()` 来实现去重。
 *  **TreeSet**:数据结构是红黑树，通过比较器来实现去重。它的有序性指的是：会通过比较器队元素进行排序。
 *  **LinkedHashSet**：`LinkedHashSet`底层使用`LinkedHashMap`来保存所有元素，通过重写`equals(Object obj)`方法和 `hashCode()` 来实现去重。它的有序性指的是，存储的顺序和取出的顺序是一致的。

**Queue接口**

**Queue的实现类主要有三类：**

*  **非阻塞的实现类**：如`ConcurrentLinkedQueue`，采用`CAS`操作实现无界线程安全队列,避免了加锁影响了性能。
 *  **阻塞的实现类**：如`ArrayBlockingQueue`（有界）、`LinkedBlockingQueue`（无界），它的阻塞性表现在当队列满了，再新增元素时会阻塞该线程，暂停添加，等待队列有空位置。
 *  **双端队列**：`Dueue`,元素可以在两端进行新增和移除操作。

阻塞队列实现阻塞同步的方式很简单，使用的就是是`lock`锁的多条件（`condition`）阻塞控制。

**Queue常见的方法：**

*  **add()**：在队列队尾新增元素，已满抛异常。
 *  **offer()**：在队列队尾新增元素，已满返回`false`。
 *  **remove()** :删除队首元素，元素为空抛异常。
 *  **poll()**：删除队首元素，元素为空返回`null`,不为空则得到该元素。
 *  **element()** ：查询队首元素，为空抛异常。
 *  **peek()** ：查询队首元素，为空返回`null`。

**ConcurrentLinkedQueue**

`ConcurrentLinkedQueue`是`java.util.concurrent`下提供的原子操作的线程安全队列，它和`LinkedBlockingQueue`都是线程安全的，它们的区别在于：

*  **LinkedBlockingQueue**： 多用于任务队列，适用于一个消费者消费多个不同的生产者不同的消息。
 *  **ConcurrentLinkedQueue**：多用于消息队列，适用于一个生产者为不同的消费者提供相同的消息。

**ArrayBlockingQueue**

`ArrayBlockingQueue`线程池配置经常使用到的有界阻塞队列。

*  `ArrayList`不适合做队列，但是数组是可以做队列，`ArrayBlockingQueue`的实现就是一个环形队列，它是一个定长的、线程安全阻塞式队列，内部是用一个定长数组来实现的。它的线程安全和阻塞性都是通过`ReentrantLock`来实现的。
 *  `ArrayBlockingQueue`的出队列和入队列过程，可以抽象地看作一个在内存上定长的游标卡尺。所以当发生出队时，队头是不断变化的，并不是一直`items[0]`，第一次是0，第二次出队是1，所以这样就不需要涉及数据迁移的操作了。

private final E[] items;//底层数据结构
        private int takeIndex;//用来为下一个take/poll/remove的索引（出队）
        private int putIndex;//用来为下一个put/offer/add的索引（入队）
        private int count;//队列中元素的个数
    
        /** Main lock guarding all access */
        private final ReentrantLock lock;//锁
        /** Condition for waiting takes */
        private final Condition notEmpty;//等待出队的条件
        /** Condition for waiting puts */
        private final Condition notFull;//等待入队的条件

## 其他 ##

**1.集合和数组的区别**

*  **数组特点**：大小固定，只能存储相同数据类型的数据
 *  **集合特点**：大小可动态扩展，可以存储各种类型的数据

集合和数组的相互转变

//array转换为list
    int[] arr = { 1,3,4,6,6};
    List list =Arrays.asList(arr);
    
    //list转化成Array
    String arratb[] =(String [])list.toArray();

**2.集合的种类**

*  **普通集合**：通常性能最高，但是不保证多线程的安全 性和并发的可靠性，如`ArrayList`。
 *  **线程安全集合**：仅仅是给集合添加了 `synchronized` 同步锁，严重牺牲了性能，而且对并发的效率就 更低了，如`HashTable`。
 *  **并发集合**：则通过复杂的策略不仅保证了多线程的安全又提高的并发时的效率，如`ConcurrentLinkedQueue`。

**3.java提供的集合工具类——Collections**

**Collections**是`java`提供的一个 `Set`、`List`和`Map`等集合的工具类， 提供了大量方法对集合进行排序、查询和修改等操作:

*  **Collections.sort(list)**：使用集合中的某一字段，对集合进行排序:
 *  **Collections.shuffle(list)**: 对集合进行随机排序:
 *  **Collections.binarySearch(list, “o”)**:查找指定集合中的元素，返回所查找元素的索引
 *  **Collections.max(list)/Collections.min(list)**:求最大值/求最小值
 *  **Collections.indexOfSubList(list, subList)/Collections.lastindexOfSubList(list, subList)**:首次/最后一次 出现元素的索引
 *  **Collections.replaceAll(list, “a”, “b”)**:替换批定元素为某元素,若要替换的值存在刚返回`true`,反之返回`false`
 *  **Collections.reverse(list)**:反转集合中元素的顺序

**Collections**提供对集合对象实现同步控制等方法：

*  **Collections.synchronizedCollection(collection)**:针对实现`collection`接口对象的集合提供线程同步控制
 *  **Collections.synchronizedList(list)**：针对实现`list`接口对象的集合提供线程同步控制
 *  **Collections.synchronizedSet(set)**:针对实现`set`接口对象的集合提供线程同步控制
 *  **Collections.synchronizedMap(map)**:针对实现`map`接口对象的集合提供线程同步控制

**4.流式表达式**

**Stream** 是 `Java8` 中处理集合的关键抽象概念，它可以指定你希望对集合进行的操作，可以执行非常复杂的查找、过滤和映射数据等操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 1]

**Stream的特性：**

*  **不存储数据**： 数组或集合的基础上创建`stream`，`stream`不会专门存储数据。
 *  **不改变原数据**： 对`stream`的操作也不会影响到创建它的数组和集合 ,对于`stream`的聚合、消费或收集操作（终止操作）只能进行一次，再次操作会报错。
 *  **延迟执行**：`Stream`延迟执行的特性，意味着它在聚合操作执行前修改数据源是允许的，一旦开始聚合操作就不允许了。

**聚合操作**

聚合操作类似`SQL`语句一样的操作， 比如`filter`, `map`, `reduce`, `find`, `match`, `sorted`等：

**中间操作**

中间操作返回结果还是`Stream`流对象。

**筛选与切片：**

*  **filter**：过滤流中的某些元素
 *  **limit(n)**：获取n个元素
 *  **skip(n)**：跳过n元素，配合`limit(n)`可实现分页
 *  **distinct()**：通过流中元素的 `hashCode()` 和 `equals()` 去除重复元素

**映射**

*  **map()**：接收一个函数作为参数，该函数会被应用到每个元素上，并将其映射成一个新的元素。
 *  **flatMap()**：接收一个函数作为参数，将流中的每个值都换成另一个流，然后把所有流连接成一个流。

**排序**

*  **sorted()**：产生一个新流，其中按自然顺序排序。
 *  **sorted(Comparator comp)**: 产生一个新流，其中按比较器顺序排序

**终止操作**

终止操作与中间操作相比，终止操作返回值已经不再是`Stream`流对象了，所以叫终止操作，能够获取到对应的值了。  
一个是`Stream`流对象只能执行一次终止操作。

**查找与匹配**

*  **allMatch(Predicate p)**：检查是否匹配所有元素
 *  **findAny()**： 返回当前流中的任意元素
 *  **max(Comparator c)**： 返回流中最大值
 *  **forEach(Consumer c)**：迭代器

**归约**

*  **reduce(T iden,BinaryOperator b)**： 可以将流中元素反复结合起来，得到一个值。
 *  **reduce(BinaryOperator b)**： 可以将流中元素反复结合起来，得到一个值。返回`Optional`。

**收集**

*  **collect(Collector c)**： 将流转换为其他形式。接收一个`Collector`接口的实现，用于给`Stream`中元素

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 2]

[Java_Map]: https://xiyuan.blog.csdn.net/article/details/109372735
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221122/c0eb97318df642e184d596c7a69e4e79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221122/bf413578859d4b228c26f300eba8db61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDk5MDgxOA_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221122/d49ea30fa5cb42d5b6c7710eaf66c8dc.png