概览

容器主要包括 Collection 和 Map 两种，Collection 存储着对象的集合，而 Map 存储着键值对（两个对象）的映射表。
本章介绍的主要是 List

Collection

1. Set

• TreeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

• HashSet：基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

• LinkedHashSet：具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

2. List

• ArrayList：基于动态数组实现，支持随机访问。

• Vector：和 ArrayList 类似，但它是线程安全的。

• LinkedList：基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

3. Queue

• LinkedList：可以用它来实现双向队列。

• PriorityQueue：基于堆结构实现，可以用它来实现优先队列。

概览部分引用 CyC2018

List

List 接口继承了 Collection ，List 中的元素有序可重复；

List 接口的实现类主要有 ArrayList，LinkedList 和 Vector；

ArrayList

ArrayList 是 List 使用中最常用的实现类，它的底层数据结构是数组，ArrayList 查询速度快，效率高，但是增和删较慢，并且是线程不安全的集合；

基本属性

ArrayList 底层是一个数组，其默认的初始容量为10

 //数据对象存放的数组，当前对象不参与序列化(主要是关键字transient起作用的)   transient Object[] elementData; //默认的初始容量 private static final int DEFAULT_CAPACITY = 10; //ArrayList 的大小（它是元素个数） private int size; //数组的最大长度   private static final int MAX_ARRAY_SIZE = 2147483639; 

构造器

• 无参构造器

  开始创建出时，该数组的长度是 1 ， 而 size 是 0 ，当进行第一次的 add 时，elementData 将会被“复制”为长度为 10 的默认值；

 //使用默认构造函器创建，则默认对象内容是该值 DEFAULTCAPACITY_EMPTY_ELEMENTDATA private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //构造一个初始容量为10的空列表 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 

• int 参数的构造器

  构造一个具有指定初始容量的空列表，如果传入的参数大于等于 0 ，那么就直接使用参数数值进行初始化，如果参数值小于 0 ，那么直接直接抛出异常；

 public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity); } } 

• Collection 参数的构造器

  构造一个包含指定集合的元素的列表，其顺序由集合的迭代器返回；

  将 Collection<? extends E> c 中保存的数据，首先转换成数组形式（toArray() 方法），然后判断当前数组长度是否为 0 ，如果为0 则替换为空数组（EMPTY_ELEMENTDATA）；否则先判断是否为 Object 数组类型，然后进行数据拷贝；

   public ArrayList(Collection<? extends E> c) {         elementData = c.toArray(); if ((size = elementData.length) != 0) { if (elementData.getClass() != Object[].class)                 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { this.elementData = EMPTY_ELEMENTDATA; } } 

  方法 Arrays.copyOf

  它新建了一个数组并且将原数组的内容拷贝到长度为newLength的新数组中，并且返回该新数组；

   public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { //先判断类型是否正确，如果正确则直接创建一个 Object 数组，长度为传入的长度 newLength          T[] copy = ((Object)newType == (Object)Object[].class) ? (T[]) new Object[newLength] //否则，执行使用反射创建一个对应的数组 : (T[]) Array.newInstance(newType.getComponentType(), newLength);         System.arraycopy(original, 0, copy, 0,                          Math.min(original.length, newLength)); return copy; } 

  方法System.arraycopy

  它就是从指定的源数组将元素中复制到目标数组，复制从指定的位置开始，到设定的复制长度结束，然后从目标数组的指定起始位置依次插入；

 // src 源数组 // srcPos 源数组要复制的起始位置 // dest 要赋值到的目标数组 // destPos 目标数组放置的起始位置 // length 复制的长度 // 使用了native关键字，说明调用的是C/C++其他语言写的底层函数 public static native void arraycopy(Object src, int  srcPos,                                         Object dest, int destPos, int length); 

add 方法 和扩容

boolean add(E e) 方法

 public boolean add(E e) { //由于添加一个元素，因此先 size+1 判断数组的容量是否够用 ensureCapacityInternal(size + 1); //上述判断或者扩容完成后，进行赋值，并且长度 size++         elementData[size++] = e; return true; } //确保数组内部容量 private void ensureCapacityInternal(int minCapacity) { //如果使用的是无参构造器，那么第一次添加一个值后 //会判断目前数组的地址是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //如果是，比较传入的 minCapacity 和 DEFAULT_CAPACITY 的值，无参构造时，肯定设置为 DEFAULT_CAPACITY //如果再次扩容那么，下此minCapacity就是size+1的值             minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } //确认实际容量，将选择好的数组容量传入 ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) {         modCount++; //如果传入的数组容量minCapacity 大于 原本的长度 elementData.length 就会扩容 if (minCapacity - elementData.length > 0) //传入扩容的长度 grow(minCapacity); } private void grow(int minCapacity) { //获取原本的容量 int oldCapacity = elementData.length; //计算新的容量数值（右移一位代表oldCapacity/2） //右移的值加上原来的数值就是新的容量值，即 1.5*oldCapacity //扩容为原来容量的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0)             newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)             newCapacity = hugeCapacity(minCapacity); //使用数组工具类并传入新的长度以及数组的地址进行复制扩容         elementData = Arrays.copyOf(elementData, newCapacity); } 

add 总结

• add 元素时，先确定数组是否能够继续存储元素；
• 如果是第一次 add 元素，那么将数组长度默认值赋值给当前数组长度，并进行扩容；
• 扩容时将会扩容为原来容量的1.5倍；
• 扩容成功后将元素再添加进数组中并发会true。

void add(int index, E element) 方法

该方法和第一个方法其实都类似，只不过该方法可以确定插入的索引；

 public void add(int index, E element) { //判断插入的索引位置是否正确 rangeCheckForAdd(index); //确保容量（或扩容） ensureCapacityInternal(size + 1); //对源数组进行复制处理（位移），从index + 1到size - index //即向后移动位于当前位置和后面的元素         System.arraycopy(elementData, index, elementData, index + 1,                          size - index); //在指定的位置赋值         elementData[index] = element;         size++; } 

boolean addAll(int index, Collection<? extends E> c) 方法

addAll 方法首先传过来的 Collection 集合转换为数组，然后做扩容处理，接着使用 System.arraycopy 把转换后的数组复制到列表尾部；

remove 方法

E remove(int index) 方法

根据索引删除元素，并返回删除的元素；

 public E remove(int index) { //检查传入的索引是否正确 rangeCheck(index);         modCount++; //获取要删除的元素值         E oldValue = elementData(index); //判断是否删除的是最后一个元素，如果不是，则将删除位置后的元素向左移 numMoved 个位置 int numMoved = size - index - 1; if (numMoved > 0) //从 index+1 开始移动元素到数组的 index 位置，即，将删除的元素直接覆盖             System.arraycopy(elementData, index+1, elementData, index,                              numMoved); //直接将删除的元素置为 null ，并且等待垃圾收集器收集 //size 减一         elementData[--size] = null; // clear to let GC do its work //返回删除的元素值 return oldValue; } //判断索引是否正确，错误时抛出 IndexOutOfBoundsException 异常 private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } //由于是数组，直接根据索引获取元素值即可  E elementData(int index) { return (E) elementData[index]; } 

remove 总结

• 先判断删除的索引是否正确；
• 获取到将要删除的元素；
• 通过数组的赋值将删除的元素覆盖，并且将数组的最后一位置为 null 。

线程问题

ArrayList 是线程不安全的集合；

示例：

public class ListTest{ public static void main(String[] args) {         ArrayList<String> list = new ArrayList<>(); for (int i = 1; i <= 3; i++) { new Thread(()->{                 list.add(UUID.randomUUID().toString().substring(0,8));                 System.out.println(list); },String.valueOf(i)).start(); } } } 

上述代码运行结果如下，而且每次运行的结果“类型”可能都不同

[null, 697f0ec8, b502b230] [null, 697f0ec8, b502b230] [null, 697f0ec8, b502b230] 

如果再将线程数量调大，会发现有如下结果：

[null, c3d3c6ae, 34f4af7e, 9aa99807, 04816aec] ... at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)         at java.util.ArrayList$Itr.next(ArrayList.java:851)[null, c3d3c6ae, 34f4af7e, 9aa99807, 04816aec]         at java.util.AbstractCollection.toString(AbstractCollection.java:461)         at java.lang.String.valueOf(String.java:2994)         at java.io.PrintStream.println(PrintStream.java:821)         at ListTest.lambda$0(ListTest.java:11)         at java.lang.Thread.run(Thread.java:745) java.util.ConcurrentModificationException 

[null, c3d3c6ae, 34f4af7e, 9aa99807, 04816aec] ... at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)         at java.util.ArrayList$Itr.next(ArrayList.java:851)[null, c3d3c6ae, 34f4af7e, 9aa99807, 04816aec]         at java.util.AbstractCollection.toString(AbstractCollection.java:461)         at java.lang.String.valueOf(String.java:2994)         at java.io.PrintStream.println(PrintStream.java:821)         at ListTest.lambda$0(ListTest.java:11)         at java.lang.Thread.run(Thread.java:745) java.util.ConcurrentModificationException 

• 出现异常

  java.util.ConcurrentModificationException ，并发修改异常

• 导致原因

  并发情况下多线程对集合进行增，删，改等操作，从而使给集合出现修改错误；

• 解决方案

  • 使用 Vector 代替；
  • 使用 Collections.synchronizedList() ；
  • 使用 JUC 的 CopyOnWriteArrayList ；

CopyOnWriteArrayList

boolean add(E e) 方法

 public boolean add(E e) { //对修改的内容加锁 final ReentrantLock lock = this.lock;         lock.lock(); try { //getArray() 方法直接获取到原本的数组地址并赋值给 elements             Object[] elements = getArray(); //获取数组长度 int len = elements.length; //直接进行复制的时候将容量加一，不用继续去扩容             Object[] newElements = Arrays.copyOf(elements, len + 1); //存储元素 e             newElements[len] = e; //将添加完毕的数组再次赋值给原本的数组 setArray(newElements); return true; } finally { //释放锁             lock.unlock(); } } 

适用场景
CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。

但是 CopyOnWriteArrayList 有其缺陷：

• 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
• 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

总结

CopyOnWrite 容器，即写时复制；往一个容器添加元素的时候，不直接往当前容器 Object[] 添加，而是先将当前的容器 Object[] 进行 copy 复制，复制出一个新的容器 Object[] newElements ，然后在新的容器 Object[] newElements 中添加元素，添加完毕后再将原容器的引用指向新的容器，也就是 setArray(newElements) ；这样的好处就是可以对 CopyOnWrite 容器进行并发的读取而不需要加锁，因为当前容器不会添加任何元素。因此， CopyOnWrite 容器也是一种读写分离的思想。

LinkedList

LinkedList 的底层是通过双向链表来实现的，LinkedList 对于添加和删除较快，而查询元素较慢，并且也是线程不安全的；

• 单链表结构与顺序存储结构的对比：
  存储分配方式：
• 顺序存储结构：用一段连续的存储单元依次存储线性表的数据元素；
• 单链表：用一组任意的存储单元存放线性表的元素。
  时间性能：
  查找：
• 顺序存储结构O(1);
• 单链表O(n)。
  插入和删除：
• 顺序存储结构需要平均移动表长一半的元素为O(n)；
• 单链表仅为O(1)。
  空间性能：
• 顺序存储结构需要预先分配存储空间，若分大，浪费，若分小，容易溢出；
• 单链表不需要预先分配存储空间，只要有才分配，元素个数不受限制。

Node 结点

 private static class Node<E> { //每个结点存储的元素值         E item; //当前结点的后继         Node<E> next; //当前节点的前驱         Node<E> prev; //Node 构造器，每次创建 Node 时，都要传入这三个值 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 

双向链表，头和尾各有 first 和 last 指针；

基本属性

//链表中存放的元素个数，初始为 0 transient int size = 0; //头节点 transient Node<E> first; //尾节点 transient Node<E> last; 

构造器

• 无参构造器

  public LinkedList() {} 

  创建一个空的链表；

• Collection 参数的构造器

   public LinkedList(Collection<? extends E> c) { this(); addAll(c); } 

  构造一个包含指定集合的元素的列表，其顺序由集合的迭代器返回；

  boolean addAll(Collection<? extends E> c) 方法，将传入的指定的集合中的所有元源添加到该链表中；

add 方法

boolean add(E e) 方法

 public boolean add(E e) { //直接调用 linkLast 方法进行尾插 linkLast(e); return true; } void linkLast(E e) { //获取出 last 尾指针（类似“备份”） final Node<E> l = last; /*         将传入的元素 e ，使用 Node 的有参构造器创建一个新的结点 newNode ，         该节点的前驱是上一步获取的 last 指针（l 指针），后继为 null，         */ final Node<E> newNode = new Node<>(l, e, null); //使得尾指针 last 指向上步创建的新的结点 newNode         last = newNode; //如果 l 指针为 null ，说明是第一次添加元素，first 和 last 都为 null if (l == null) //由于第一次添加元素，则让 first 指针也指向新创建的结点 newNode             first = newNode; else //否则，就让获取出 last 指针的 l 指针的后继指向 newNode 结点             l.next = newNode; //长度 +1         size++;         modCount++; } 

add 总结

• add 方法使用的是尾插法进行添加操作的；
• 都会先获取一个维护 last 尾指针的 l 指针；
• 将获取的 l 指针用作新创建结点的前驱（prev），由于是尾插则新结点的后继是 null ；
• 重新赋值 last 尾指针，让其指向新的结点元素；
• 判断 l 指针是否为空（第一次操作时为空链表，last 和 first 指针都指向 null ）；
• 不为空时，就让 l 指针的后继 next 指向新结点，将前后两个结点“串联”起来。

void addFirst(E e) 方法

 public void addFirst(E e) { linkFirst(e); } private void linkFirst(E e) { //和尾插法类似，先获取出 first 指针 final Node<E> f = first;f         //创建新的结点元素，因为头插法，前驱为 null ，后继就是上步获取的 f 指针（first 指针） final Node<E> newNode = new Node<>(null, e, f); //让 first 指针指向新的结点元素         first = newNode; //判断是否为空，如果为空说明第一次添加 if (f == null) //让 last 指针也指向新结点             last = newNode; else //否则，就让             f.prev = newNode;         size++;         modCount++; } 

上述的两个添加方法，最不能理解的就是前驱和后继的指向问题。尾插法来说，在创建新的结点时其新结点的前驱是 l 指针（也可以说是链表原本的最后一个结点），如何让新添加的元素和之前的尾元素关联起来呢？

新结点的前驱是上个元素的结点，因此直接让 l.next 指向新结点元素即可（虽然 last 指针已经指向新结点元素，但是备份的 l 指针不仅保存在新结点的前驱中，同时也是上一个尾结点）。

remove 方法

E remove() 方法

 public E remove() { return removeFirst(); } public E removeFirst() { //获取头指针 first final Node<E> f = first; //只要头指针不为空，说明存在元素，否则抛出异常 if (f == null) throw new NoSuchElementException(); //进行删除 return unlinkFirst(f); } private E unlinkFirst(Node<E> f) { //获取出要删除的结点中的元素 element final E element = f.item; //获取要删除结点的后继，也就是下一个节点 final Node<E> next = f.next; //下面两步手动置为 null，让 GC 能够更快的清理无指向的空结点         f.item = null;         f.next = null; // help GC //让头指针 first 指向之前获取出的头结点的下一个结点元素         first = next; //如果下一个结点元素为 null ，说明删除的就是链表中的最后一个元素，所以让尾指针也置为 null if (next == null)             last = null; else //否则，让新的头结点的前驱置为 null（断开与之前头结点的最后联系）             next.prev = null; //长度 -1         size--;         modCount++; return element; } 

remove 总结

• 先获取头指针 first；
• 让 next 结点指向要删除结点的后继结点；
• 使要删除的结点的元素和后继都置为 null；
• 接着让头指针 first 指向 next 结点；
• 判断删除的是否是最后一个元素，如果是则让 last 指针也指向 null；
• 否则，让 next 结点的前驱，也就是现在的头结点的前驱置为 null；

E removeLast() 方法和 E removeFirst() 类似；

Vector

Vector 是 List 的另外一个实现类，完全支持 List 的全部功能，Vector 是一个比较古老的集合， JDK1.0 就已经存在，它的底层和 ArrayList 一样，也是一个 Object 数组；Vector 与 ArrayList的主要是区别是，Vector 是线程安全的，但是性能比ArrayList要低；

基本属性

//存储元素的数组  protected Object[] elementData; //记录数组的元素个数 protected int elementCount; //数组的增长系数 protected int capacityIncrement; 

构造器

 public Vector() { //默认容量为 10 this(10); } public Vector(int initialCapacity) { this(initialCapacity, 0); } //传入初始容量和数组的增长系数 public Vector(int initialCapacity, int capacityIncrement) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity); this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } //将指定的集合元素转化为Vector public Vector(Collection<? extends E> c) {         elementData = c.toArray();         elementCount = elementData.length; // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class)             elementData = Arrays.copyOf(elementData, elementCount, Object[].class); } 

Vector 的扩容

其实 Vector 和 ArrayList 的 add ， remove 方法大致都类似， Vector add 元素（ensureCapacityHelper 方法）时，都要调用该方法来确保足够的容量，代码如下:

 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; //根据 capacityIncrement 进行判断，capacityIncrement>0 增加capacityIncrement个容量，否则扩容为之前的2倍 int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                                          capacityIncrement : oldCapacity); if (newCapacity - minCapacity < 0)             newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0)             newCapacity = hugeCapacity(minCapacity); //也是利用 Arrays.copyOf 进行数组的复制         elementData = Arrays.copyOf(elementData, newCapacity); }