集合学习笔记——Collection 全家桶

àì夳堔傛蜴生んèń 2023-10-03 21:49 3阅读 0赞

![format_png][]

**Collection**是我们日常开发中使用频率非常高的集合，它的主要实现有`List`和`Set`,区别是`List`是有序的，元素可以重复;`Set`是无序的，元素不可以重复，我们简单看下继承关系：

![format_png 1][]

1.  **List**的实现类主要线程不安全的`ArrayList`和`LinkedList`以及线程安全的`CopyOnWriteArrayList`;
2.  **Set**的实现类主要有线程不安全的`HashSet`和`TreeSet`以及线程安全的`CopyOnWriteArraySet`。

个人觉得，以上集合组件类其实并不难，所以我不打算分析源码，其中`HashSet`和`TreeSet`底层使用分别是[HashMap][]和[TreeMap][], 所以只要看下之前的文章就比较容易理解了。

## 1.ArrayList VS LinkedList ##

**ArrayList**:

1.  底层是通过`数组`(内存地址连续)实现的，直接可以通过下标找到目标元素，时间复杂度是**O(1)**,而`LinkedList`需要移动指针遍历每个元素，时间复杂度是**O(N)**,所以 **Arraylist**查找元素的速度比`Linkedlist`快.
2.  **Arraylist**在新增和删除元素时，可能扩容和复制数组。而`Linkedlist`实例化对象只需要修改指针即可.
3.  **Arraylist** 可能会造成一定空间的浪费，因为它要预先开辟空间
4.  默认的初始容量是10个，每次扩容为原来的1.5倍(当数组满了才会扩容，不像HashMap有扩容因子)

![format_png 2][]

**LinkedList**:

1.  底层是通过`线性表(链表)`(内存空间不连续)来实现的，是一个双向链表
2.  **LinkedList**不支持高效的随机访问，它需要移动指针遍历每个元素
3.  没有初始容量，没有扩容机制

![format_png 3][]

**时间复杂度对比**：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>数组</th> 
   <th>链表</th> 
   <th>说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>随机访问</td> 
   <td>O(1)</td> 
   <td>O(N)</td> 
   <td>随机访问数组比链表快</td> 
  </tr> 
  <tr> 
   <td>头部插入</td> 
   <td>O(N)</td> 
   <td>O(1)</td> 
   <td>插入：链表快于数组，因为数组要移动其他元素的位置</td> 
  </tr> 
  <tr> 
   <td>头部删除</td> 
   <td>O(N)</td> 
   <td>O(1)</td> 
   <td>删除：链表快于数组，因为数组要移动其他元素的位置</td> 
  </tr> 
  <tr> 
   <td>尾部插入</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>插入速度一样快，但是数组有可能是触发扩容动作</td> 
  </tr> 
  <tr> 
   <td>尾部删除</td> 
   <td>O(1)</td> 
   <td>O(1)</td> 
   <td>删除速度一样快</td> 
  </tr> 
  <tr> 
   <td>指定位置插入</td> 
   <td>O(N)</td> 
   <td>O(N)</td> 
   <td>数组：在第几个元素后面插入，后面的元素需要向后移动，链表：需要先找到第几个元素，然后修改指针指向操作</td> 
  </tr> 
 </tbody> 
</table>

> 总体来说：**ArrayList**查询速度快，**LinkedList**插入删除速度快。

**使用场景**：

1.  如果应用程序对数据有较多的随机访问，`ArrayList`性能要优于`LinkedList`；
2.  如果应用程序有更多的插入或者删除操作，较少的随机访问，`LinkedList`性能要优于`ArrayList`；
3.  不过`ArrayList`的插入，删除操作也不一定比`LinkedList`慢，如果在`ArrayList`靠近末尾的地方插入，那么`ArrayList`只需要移动较少的数据（或者无需移动数据)，此时二者耗时几乎差不多(`LinkedList`是双向链表，可以快速定位头尾部的节点)

## 2.HashSet VS TreeSet ##

**HashSet** 和 **TreeSet** 都是元素不能重复的集合，其中**TreeSet**具有排序的功能。

**HashSet源码分析**：

public class HashSet<E>
        extends AbstractSet<E>
        implements Set<E>, Cloneable, java.io.Serializable
    {
        static final long serialVersionUID = -5024744406713321676L;
    
        /**
         *
         * HashSet底层用的就是HashMap，只不过只使用了HashMap的key
         */
        private transient HashMap<E,Object> map;
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();
    
        /**
         * 无参构造器：内部创建一个HashMap
         */
        public HashSet() {
            map = new HashMap<>();
        }
    
        /**
         * 参数是集合
         */
        public HashSet(Collection<? extends E> c) {
            map = new HashMap<>(Math.max((int) (c.size()/0.75f) + 1, 16));
            addAll(c);
        }
    
        /**
         * 指定容量的构造器，这个容量将传递给HashMap
         */
        public HashSet(int initialCapacity) {
            map = new HashMap<>(initialCapacity);
        }
    
        /**
         * add元素，发现它确实是添加到了HashMap中
         */
        public boolean add(E e) {
            return map.put(e, PRESENT)==null;
        }
    
        //.....省略其他代码
    }
    复制代码

> 不难发现，`HashSet`底层使用的就是[HashMap][],只不过是只使用了`HashMap`的`key`,根据`HashMap`的特点，key如果相同，则旧值覆盖新值，所以达到去重的效果。

**TreeSet源码分析**:

public class TreeSet<E> extends AbstractSet<E>
        implements NavigableSet<E>, Cloneable, java.io.Serializable
    {
        /**
         * 内存真正存储元素的组件：TreeMap, 只不过是只使用了key
         */
        private transient NavigableMap<E,Object> m;
    
        // Dummy value to associate with an Object in the backing Map
        private static final Object PRESENT = new Object();
    
        /**
         * 空参数构造器：其内部创建了TreeMap, 但是只使用TreeMap的key
         */
        public TreeSet() {
            this(new TreeMap<E,Object>());
        }
    
        /**
         * 可以传入一个比较器，这个比较器将交给TreeMap
         */
        public TreeSet(Comparator<? super E> comparator) {
            this(new TreeMap<>(comparator));
        }
    
        /**
         * 添加元素：将添加到TreeMap中
         */
        public boolean add(E e) {
            return m.put(e, PRESENT)==null;
        }
      }  
    复制代码

> 不难发现，`TreeSet`底层使用的是[TreeMap][],只不过是只使用了`TreeMap`的`key`,根据**TreeMap**的特点，默认是按照`自然排序`(`key`必须要实现`Comparable`接口),或者指定比较器`Comparator`，自定义比较规则。

## 3.线程安全的CopyOnWriteArrayList ##

> **CopyOnWriteArraySet** 底层使用的也是`CopyOnWriteArrayList`

先简单总结下它的底层原理：

1.  `CopyOnWriteArrayList`内部也是通过数组来实现的，在向`CopyOnWriteArrayList`添加元素时，会复制一个新的数组，写操作在新数组上进行，读操作在原数组上进行(**写时复制**的思想)
2.  `写操作会加锁`，防止并发写入造成数据丢失的问题
3.  写操作结束后会把原数组指向新数组
4.  `CopyOnWriteArrayList`允许在进行写操作的同时来读取数据，大大提高了读的性能，因此适合读多写少的场景(写多读少的话，会大量复制数组，非常耗费内存)，但是`CopyOnWriteArrayList`可能读到的数据不是最新的数据，所以不适合实时性要求高的场景(数据不一致的问题)。

> 只能保证最终一致，不能保证实时一致

我们看下源码：

public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
        private static final long serialVersionUID = 8673264195747942595L;
    
        /** 
         * 通过 ReentrantLock 来保证写时的线程安全
         */
        final transient ReentrantLock lock = new ReentrantLock();
    
        /** 
         * 底层仍然是使用数组来存储数据
         */
        private transient volatile Object[] array;
      
    
        /**
         * 读取数据，没有加锁，直接读就可以
         */
        public E get(int index) {
            return get(getArray(), index);
        }
        
        private E get(Object[] a, int index) {
            return (E) a[index];
        }
    
        /**
         * 添加元素（写）
         * 
         * 1.首先加锁
         * 2.获取原数组
         * 3.根据原数据复制一个新的数组
         * 4.然后对新数组进行写操作（这中间读的话，仍然读的是原数组)
         * 5.将新数组赋给原数组
         */
        public boolean add(E e) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len + 1);
                newElements[len] = e;
                setArray(newElements);
                return true;
            } finally {
                lock.unlock();
            }
        }
    
         /**
         * 删除元素（写）：和 add一样
         * 
         * 1.首先加锁
         * 2.获取原数组
         * 3.根据原数据复制一个新的数组
         * 4.然后对新数组进行写操作（这中间读的话，仍然读的是原数组)
         * 5.将新数组赋给原数组
         */
        public E remove(int index) {
            final ReentrantLock lock = this.lock;
            lock.lock();
            try {
                Object[] elements = getArray();
                int len = elements.length;
                E oldValue = get(elements, index);
                int numMoved = len - index - 1;
                if (numMoved == 0)
                    setArray(Arrays.copyOf(elements, len - 1));
                else {
                    Object[] newElements = new Object[len - 1];
                    System.arraycopy(elements, 0, newElements, 0, index);
                    System.arraycopy(elements, index + 1, newElements, index,
                                     numMoved);
                    setArray(newElements);
                }
                return oldValue;
            } finally {
                lock.unlock();
            }
        }
     } 
    复制代码

源码并不复杂，就是**写时复制**的思想，我们简单用一张图来展示下：

![format_png 4][]

好了，关于**Collection**集合下常用的组件就分析到这里吧，对比**Map**，这些就显得比较简单了，源码也很容易理解。

[format_png]: https://img-blog.csdnimg.cn/img_convert/57580b80fc44313a58c396b605715f8c.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/88d3e556409729f04ca85442f664d22c.webp?x-oss-process=image/format,png
[HashMap]: https://juejin.cn/post/7163967689172615199
[TreeMap]: https://juejin.cn/post/7166513360865853453
[format_png 2]: https://img-blog.csdnimg.cn/img_convert/64ad2c8d1e719975dec6fb14da4ad8de.webp?x-oss-process=image/format,png
[format_png 3]: https://img-blog.csdnimg.cn/img_convert/b7e1ff280b9f2a5c51dc9e948f03da5b.webp?x-oss-process=image/format,png
[format_png 4]: https://img-blog.csdnimg.cn/img_convert/df0815a74b41369a5543555c6ee39197.webp?x-oss-process=image/format,png