关注“Java 后端技术全栈”**
回复“面试”获取全套面试材料
Java 汇合框架早也是个老话题了，明天次要是总结一下对于 Java 中的汇合框架 List 的外围知识点。必定有人会问，这篇写的是 List 那接下来就还有三篇？是的，java 汇合框架一共会有四篇。心愿通过这个系列能让你全面的 get 到 Java 汇合框架的外围知识点。
目标
更心愿通过这个系列的文章有所播种，不仅能够用于工作中，也能够用于面试中。
Java 汇合 是一个存储雷同类型数据的容器，相似数组，汇合能够不指定长度，然而数组必须指定长度。汇合类次要从 Collection 和 Map 两个根接口派生进去，比方罕用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。包目录：java.util
学过 Java 的都晓得 Java 有四大汇合框架，JDK 版本 1.8
- List
- Set
- Queue
- Map
罕用汇合 UML 类图
上面展现罕用的汇合框架（上面图中的两种线：虚线为实现，实线为继承）
ArrayList
ArrayList 是基于 动静数组 实现，容量能主动增长的汇合。随机拜访效率高 ，随机插入、随机删除效率低。 线程不平安，多线程环境下能够应用 Collections.synchronizedList(list) 函数返回一个线程平安的 ArrayList 类，也能够应用 concurrent 并发包下的 CopyOnWriteArrayList 类。
动静数组，是指当数组容量不足以寄存新的元素时，会创立新的数组，而后把原数组中的内容复制到新数组。
次要属性：
1// 存储理论数据，应用 transient 润饰，序列化的时不会被保留
2transient Object[] elementData;
3// 元素的数量，即容量。4private int size;
数据结构：动静数组
特色：
- 容许元素为 null；
- 查问效率高、插入、删除效率低，因为大量 copy 原来元素；
- 线程不平安。
应用场景：
- 须要疾速随机拜访元素
- 单线程环境
罕用办法介绍
add(element) 流程：增加元素
1 private static final int DEFAULT_CAPACITY = 10;
2 // 增加的数据 e 放在 list 的前面
3 public boolean add(E e) {4 ensureCapacityInternal(size + 1);
5 elementData[size++] = e;
6 return true;
7 }
8 private void ensureCapacityInternal(int minCapacity) {9 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
10 }
11 private static int calculateCapacity(Object[] elementData, int minCapacity) {12 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {13 return Math.max(DEFAULT_CAPACITY, minCapacity);
14 }
15 return minCapacity;
16 }- 判断以后数组是否为空，如果是则创立长度为 10（默认）的数组，因为 new ArrayList 的时没有初始化；
- 判断是否须要扩容，如果以后数组的长度加 1（即 size+1）后是否大于以后数组长度，则进行扩容 grow()；
- 最初在数组开端增加元素，并 size+1。
grow() 流程：扩容
1 private void grow(int minCapacity) {
2 // overflow-conscious code
3 int oldCapacity = elementData.length;
4 int newCapacity = oldCapacity + (oldCapacity >> 1);
5 if (newCapacity - minCapacity < 0)
6 newCapacity = minCapacity;
7 if (newCapacity - MAX_ARRAY_SIZE > 0)
8 newCapacity = hugeCapacity(minCapacity);
9 // minCapacity is usually close to size, so this is a win:
10 elementData = Arrays.copyOf(elementData, newCapacity);
11 }- 创立新数组，长度扩充为原数组的 1.5 倍（oldCapacity >> 1 就是相当于 10>>1==10/2=5，二进制位运算）；
- 如果扩充 1.5 倍还是不够，则依据理论长度来扩容，比方 addAll() 场景；
- 将原数组的数据应用 System.arraycopy（native 办法）复制到新数组中。
add(index,element) 流程：向指定下标增加元素
1 public void add(int index, E element) {2 rangeCheckForAdd(index);
3
4 ensureCapacityInternal(size + 1); // Increments modCount!!
5 System.arraycopy(elementData, index, elementData, index + 1,
6 size - index);
7 elementData[index] = element;
8 size++;
9 }
10 private void rangeCheckForAdd(int index) {11 if (index > size || index < 0)
12 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
13 }- 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 <=2，否则报 IndexOutOfBoundsException 异样；
- 扩容查看；
- 通过拷贝形式，把数组地位为 index 至 size-1 的元素都往后挪动一位，腾出地位之后放入元素，并 size+1。
set(index,element) 流程：设置新值，返回旧值
1 public E set(int index, E element) {2 rangeCheck(index);
3
4 E oldValue = elementData(index);
5 elementData[index] = element;
6 return oldValue;
7 }
8 private void rangeCheck(int index) {9 if (index >= size)
10 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
11 }- 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 小于 <2，下标是从 0 开始的，size= 2 阐明下标只有 0 和 1；
- 保留被笼罩的值，因为最初须要返回旧的值；
- 新元素笼罩地位为 index 的旧元素，返回旧值。
get(index) 流程：通过下标获取 list 中的数据
1 public E get(int index) {2 rangeCheck(index);
3 return elementData(index);
4 }
- 判断下标有没有越界；
- 间接通过数组下标来获取数组中对应的元素，get 的工夫复杂度是 O(1)。
remove(index) 流程：依照下标移除 lsit 中的数据
1 public E remove(int index) {2 rangeCheck(index);
3 modCount++;
4 E oldValue = elementData(index);
5 int numMoved = size - index - 1;
6 if (numMoved > 0)
7 System.arraycopy(elementData, index+1, elementData, index,
8 numMoved);
9 elementData[--size] = null; // clear to let GC do its work
10 return oldValue;
11 }- 查看指定地位是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 < 2；
- 保留要删除的值，因为最初须要返回旧的值；
- 计算出须要挪动元素个数，再通过拷贝使数组内地位为 index+1 到 size-1 的元素往前挪动一位，把数组最初一个元素设置为 null（精辟小技巧），返回旧值。
remove(object) 流程：
1 public boolean remove(Object o) {2 if (o == null) {3 for (int index = 0; index < size; index++)
4 if (elementData[index] == null) {5 fastRemove(index);
6 return true;
7 }
8 } else {9 for (int index = 0; index < size; index++)
10 if (o.equals(elementData[index])) {11 fastRemove(index);
12 return true;
13 }
14 }
15 return false;
16 }
17 private void fastRemove(int index) {
18 modCount++;
19 int numMoved = size - index - 1;
20 if (numMoved > 0){
21 // 数组拷贝
22 System.arraycopy(elementData, index+1, elementData, index,
23 numMoved);
24 }
25 // 不便 GC
26 elementData[--size] = null;
27 }- 遍历数组，比拟 obejct 是否存在于数组中；
- 计算出须要挪动元素个数，再通过拷贝使数组内地位为 index+1 到 size-1 的元素往前挪动一位，把数组最初一个元素设置为 null（精辟小技巧）。
总结：
- new ArrayList 创建对象时，如果没有指定汇合容量则初始化为 0；如果有指定，则依照指定的大小初始化；
- 扩容时，先将汇合扩充 1.5 倍，如果还是不够，则依据理论长度来扩容，保障都能存储所有数据，比方 addAll() 场景。
- 如果新扩容后数组长度大于（Integer.MAX_VALUE-8），则抛出 OutOfMemoryError。
- 倡议在应用的时候，先评估一下要存多少数据，而后就能够大抵或者精确的给 ArrayList 指定大小，这样就会防止一直屡次扩容对系统带来的开销。
LinkedList
LinkedList 是能够在任何地位进行 插入 和移除 操作的 有序汇合 ，它是基于双向链表实现的， 线程不平安 。LinkedList 性能比拟弱小，能够实现 栈、队列 或双向队列。
次要属性：
1// 链表长度
2transient int size = 0;
3// 头部节点
4transient Node<E> first;
5// 尾部节点
6transient Node<E> last;
7
8/**
9* 动态外部类，存储数据的节点
10* 前驱结点、后继结点，那证实至多是双向链表
11*/
12private static class Node<E> {
13 // 本身结点
14 E item;
15 // 下一个节点
16 Node<E> next;
17 // 上一个节点
18 Node<E> prev;
19}数据结构：双向链表
特色：
- 容许元素为 null；
- 插入和删除效率高，查问效率低；
- 程序拜访会十分高效，而随机拜访效率（比方 get 办法）比拟低；
- 既能实现栈 Stack（后进先出），也能实现队列（先进先出）, 也能实现双向队列，因为提供了 xxxFirst()、xxxLast() 等办法；
- 线程不平安。
应用场景：
- 须要疾速插入，删除元素
- 依照程序拜访其中的元素
- 单线程环境
add() 流程：
1 public boolean add(E e) {2 linkLast(e);
3 return true;
4 }
5 void linkLast(E e) {
6 final Node<E> l = last;
7 final Node<E> newNode = new Node<>(l, e, null);
8 last = newNode;
9 if (l == null)
10 first = newNode;
11 else
12 l.next = newNode;
13 size++;
14 modCount++;
15 }- 创立一个新结点，结点元素 e 为传入参数，前继节点 prev 为“以后链表 last 结点”，后继节点 next 为 null；
- 判断以后链表 last 结点是否为空，如果是则把新建结点作为头结点，如果不是则把新结点作为 last 结点。
- 最初返回 true。
get(index) 流程：
1 public E get(int index) {2 checkElementIndex(index);
3 return node(index).item;
4 }
5 /**
6 * Returns the (non-null) Node at the specified element index.
7 */
8 Node<E> node(int index) {9 if (index < (size >> 1)) {
10 Node<E> x = first;
11 for (int i = 0; i < index; i++)
12 x = x.next;
13 return x;
14 } else {
15 Node<E> x = last;
16 for (int i = size - 1; i > index; i--)
17 x = x.prev;
18 return x;
19 }
20 }
21 private void checkElementIndex(int index) {22 if (!isElementIndex(index))
23 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
24 }
25 private boolean isElementIndex(int index) {
26 return index >= 0 && index < size;
27 }- 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 < 2；
- index 小于“双向链表长度的 1/2”则从头开始往后遍历查找，否则从链表开端开始向前遍历查找。
remove() 流程：
1 public E remove(int index) {2 checkElementIndex(index);
3 return unlink(node(index));
4 }
5 private void checkElementIndex(int index) {6 if (!isElementIndex(index))
7 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
8 }
- 判断 first 结点是否为空，如果是则报 NoSuchElementException 异样；
- 如果不为空，则把待删除结点的 next 结点的 prev 属性赋值为 null，达到删除头结点的成果。
- 返回删除值。
Vector
Vector 是矢量队列，也是基于动静数组实现，容量能够主动扩容。跟 ArrayList 实现原理一样，然而 Vector 是 线程平安 ，应用 Synchronized 实现线程平安，性能十分差， 已被淘汰，应用 CopyOnWriteArrayList 代替 Vector。
次要属性：
1// 存储理论数据
2protected Object[] elementData;
3// 动静数组的理论大小
4protected int elementCount;
5// 动静数组的扩容系数
6protected int capacityIncrement;
数据结构：动静数组
特色：
- 容许元素为 null；
- 查问效率高、插入、删除效率低，因为须要挪动元素；
- 默认的初始化大小为 10，没有指定增长系数则每次都是扩容一倍，如果扩容后还不够，则间接依据参数长度来扩容；
- 线程平安，性能差（Synchronized），应用 CopyOnWriteArrayList 代替 Vector。
应用场景：多线程环境
为什么是线程平安的，看看上面的几个罕用办法就晓得了。
1 public synchronized void addElement(E obj) {
2 modCount++;
3 ensureCapacityHelper(elementCount + 1);
4 elementData[elementCount++] = obj;
5 }
6 public boolean remove(Object o) {7 return removeElement(o);
8 }
9 public synchronized boolean removeElement(Object obj) {
10 modCount++;
11 int i = indexOf(obj);
12 if (i >= 0) {13 removeElementAt(i);
14 return true;
15 }
16 return false;
17 }
18 public synchronized E get(int index) {19 if (index >= elementCount)
20 throw new ArrayIndexOutOfBoundsException(index);
21
22 return elementData(index);
23 }
24 public synchronized boolean add(E e) {
25 modCount++;
26 ensureCapacityHelper(elementCount + 1);
27 elementData[elementCount++] = e;
28 return true;
29 }这几个罕用办法中，办法都是应用同步锁 synchronized 润饰，所以它是线程平安的。
Stack
Stack 是栈，先进后出 准则，Stack 继承 Vector，也是通过数组实现，线程平安。因为效率比拟低，不举荐应用，能够应用 LinkedList（线程不平安）或者 ConcurrentLinkedDeque（线程平安）来实现先进先出的成果。
数据结构：动静数组
构造函数：只有一个默认 Stack()
特色：先进后出
实现原理：
- Stack 执行 push() 时，将数据推动栈，即把数据追加到数组的开端。
- Stack 执行 peek 时，取出栈顶数据，不删除此数据，即获取数组首个元素。
- Stack 执行 pop 时，取出栈顶数据，在栈顶删除数据，即删除数组首个元素。
- Stack 继承于 Vector，所以 Vector 领有的属性和性能，Stack 都领有，比方 add()、set() 等等。
1public class Stack<E> extends Vector<E> {
2//....
3}
CopyOnWriteArrayList
CopyOnWriteArrayList 是 线程平安 的 ArrayList，写操作（add、set、remove 等等）时，把原数组拷贝一份进去，而后在新数组进行写操作，操作完后，再将原数组援用指向到新数组。CopyOnWriteArrayList 能够代替 Collections.synchronizedList(List list)。这个是在 JUC 包目录下的。外部应用了 AQS 实现的锁。
java.util.concurrent
数据结构：动静数组
特色：
- 线程平安；
- 读多写少，比方缓存；
- 不能保障实时一致性，只能保障最终一致性。
毛病：
- 写操作，须要拷贝数组，比拟耗费内存，如果原数组容量大的状况下，可能触发频繁的 Young GC 或者 Full GC；
- 不能用于实时读的场景，因为读取到数据可能是旧的，能够保障最终一致性。
实现原理：
CopyOnWriteArrayList 写操作加了锁，不然多线程进行写操作时会复制多个正本；读操作没有加锁，所以能够实现并发读，然而可能读到旧的数据，比方正在执行读操作时，同时有多个写操作在进行，遇到这种场景时，就会都到旧数据。
1public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
2 private static final long serialVersionUID = 8673264195747942595L;
3
4 /** The lock protecting all mutators */
5 final transient ReentrantLock lock = new ReentrantLock();
6 // 增加数据
7 public boolean add(E e) {
8 // 应用到了锁机制
9 final ReentrantLock lock = this.lock;
10 lock.lock();
11 try {12 Object[] elements = getArray();
13 int len = elements.length;
14 Object[] newElements = Arrays.copyOf(elements, len + 1);
15 newElements[len] = e;
16 setArray(newElements);
17 return true;
18 } finally {
19 // 开释锁
20 lock.unlock();
21 }
22 }
23 // 移除数据
24 public E remove(int index) {
25 // 锁机制
26 final ReentrantLock lock = this.lock;
27 lock.lock();
28 try {29 Object[] elements = getArray();
30 int len = elements.length;
31 E oldValue = get(elements, index);
32 int numMoved = len - index - 1;
33 if (numMoved == 0)
34 setArray(Arrays.copyOf(elements, len - 1));
35 else {36 Object[] newElements = new Object[len - 1];
37 System.arraycopy(elements, 0, newElements, 0, index);
38 System.arraycopy(elements, index + 1, newElements, index,
39 numMoved);
40 setArray(newElements);
41 }
42 return oldValue;
43 } finally {
44 // 开释锁
45 lock.unlock();
46 }
47 }好的，以上便是明天分享的内容。心愿你有所播种。
对老铁最大激励就是点个 在看 && 转发 在看 || 转发。可二选一。哈哈哈！