想要了解集合，首先要知道一个东西，叫数据结构。所谓数据结构，其实就是计算机存储，组织数据的方式。

常用的数据结构有8大类

数组，链表，树，堆，栈，队列，哈希表，图

在集合中比较常见的是数组，链表，红黑树

什么是集合

Java 集合（Collection）是 Java 提供的一套用于存储和操作多个对象的框架，位于java.util包下。它替代了传统的数组，提供了更灵活、功能更丰富的数据结构，以及便捷的操作方法。

Java 集合两大体系Collection和Map

Collection是单列集合（单列集合元素存储方式就是一个个元素存储），

Collection 接口的主要子接口
List：有序、可重复的集合
List最大的特点就是存储的元素是有顺序的，并且可以存储重复的元素
ArrayList：基于动态数组实现，查询快，增删慢
LinkedList：基于双向链表实现，增删快，查询慢
Vector：线程安全的动态数组（古老类，效率较低）
Set：无序、不可重复的集合
Set最大的特点就是存储的元素是无顺序的，并且不可以存储重复的元素
HashSet：基于哈希表实现，无序，查询快
LinkedHashSet：继承 HashSet，维护元素插入顺序
TreeSet：基于红黑树实现，元素有序（自然排序或定制排序）
Queue：队列，通常按 FIFO（先进先出）原则操作
LinkedList：可作为队列使用
PriorityQueue：优先级队列，元素按优先级排序

Map是双列集合（双列集合元素存储方式是以key，value键值对的方式进行存储）

Map 接口的主要实现类
HashMap：基于哈希表实现，无序，查询快
LinkedHashMap：继承 HashMap，维护键值对的插入顺序
TreeMap：基于红黑树实现，键有序
Hashtable：线程安全的哈希表（古老类，效率较低）
ConcurrentHashMap：线程安全的 HashMap，并发性能好

ArrayList和LinkedList和Vector

ArrayList底层的数据结构是数组，而LinkedList底层的数据结构是链表
Vector支持线程同步，是线程访问安全的，ArrayList线程不安全。

数组的特点就是通过索引来查询数据，因此查询数据速度比较快，而因为数组的内存空间是连续性的因此在添加数据和删除数据的时候，因此效率没这么快

链表的特点就是内存空间不是连续性的，因此查询的时候需要遍历检索，效率没这么高，而元素的底层是由prev，元素和next三部分组成的节点。因此在增删数据的时候只需要把节点的next，断开原本的prev，然后连接新的prev，因此无需移动元素，效率更高，被断开的节点会慢慢地被gc回收

ArrayList动态扩容

ArrayList默认数组的大小为10，扩容的时候采用的是采用移位运算
ArrayList的扩容因子为1.5

ArrayList和LinkedList的使用场景

在工作中对元素进行增删操作时使用LinkedList，而进行查询的操作使用的是ArrayList

ArrayList底层结构是基于数组，因为数组最大的特点就是有索引作为下标，查询时比较方便快捷，但在增删操作时要进行元素位置的移动，因此效率比较慢。

LinkedList的底层结构基于链表，查询的时候回通过这般搜索的方式进行查找因此效率会比较慢，

但在增删操作时只需要将链表节点的头尾指针进行修改即可，因此效率会比较快。

在ArrayList中访问元素的最糟糕的时间复杂度是O(1)，而在LinkedList中可能就是O(n)了。在ArrayList中增加或者删除某个元素时候，如果触发到了扩容机制，那么底层就会调用到System.arraycopy方法，被native修饰，该方法会直接通过内存复制，省去了大量的数组寻址访问等时间。但是相比于LinkedList而言，在频繁的修改元素的情况下，选用LinkedList的性能会更加好一点

如果去学习过jvm的话，应该会对“内存碎片“这个名词比较熟悉。

基于数组结构的数据在存储信息的时候都需要有连续的内存空间，

所以如果当内存碎片化情况较为严重的时候，可能在使用ArrayList的时候会有OOM的异常抛出。

复制某个ArrayList到另一个ArrayList中去

使用clone()方法，比如ArrayList newArray = oldArray.clone();
使用ArrayList构造方法，比如：ArrayList myObject = new ArrayList(myTempObject);
使用Collection的copy方法。

fail-fast机制

在ArrayList设计的时候，其实还包含有了一个modCount参数，

这个参数需要和expectedModCount 参数一起使用，expectedModCount参数在进行修改的时候会被modCount进行赋值操作，

当多个线程同时对该集合中的某个元素进行修改之前都会进行expectedModCount 和modCount的比较操作，

只有当二者相同的时候才会进行修改，两者不同的时候则会抛出异常。

COW容器

jdk1.5之前，由于常用的ArrayList并不具有线程安全的特性，因此在1.5之后的并发包里面出现了CopyOnWrite容器，简称为COW。

通俗的理解是当我们往一个容器添加元素的时候，不直接往当前容器添加，而是先将当前容器进行Copy，复制出一个新的容器，然后新的容器里添加元素，添加完元素之后，再将原容器的引用指向新的容器。

这样做的好处是我们可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。

所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。

并发包juc里面的CopyOnWriteArrayList中，核心原理主要是通过加入了ReentrantLock来保证线程安全性，从而解决了ArrayList的线程安全隐患问题。

集合的选择建议

需要有序可重复：选择ArrayList（查询多）或LinkedList（增删多）
需要无序不可重复：选择HashSet
需要排序的集合：选择TreeSet（元素）或TreeMap（键）
需要键值对存储：选择HashMap（一般情况）或LinkedHashMap（需顺序）
多线程环境：考虑使用ConcurrentHashMap等线程安全集合