关于java:精解四大集合框架List核心知识总结

关注“Java 后端技术全栈”**

回复“面试”获取全套面试材料

Java 汇合框架早也是个老话题了，明天次要是总结一下对于 Java 中的汇合框架 List 的外围知识点。必定有人会问，这篇写的是 List 那接下来就还有三篇？是的，java 汇合框架一共会有四篇。心愿通过这个系列能让你全面的 get 到 Java 汇合框架的外围知识点。

目标

更心愿通过这个系列的文章有所播种，不仅能够用于工作中，也能够用于面试中。

Java 汇合 是一个存储雷同类型数据的容器，相似数组，汇合能够不指定长度，然而数组必须指定长度。汇合类次要从 Collection 和 Map 两个根接口派生进去，比方罕用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。包目录：java.util

学过 Java 的都晓得 Java 有四大汇合框架，JDK 版本 1.8

1. List
2. Set
3. Queue
4. Map

罕用汇合 UML 类图

上面展现罕用的汇合框架（上面图中的两种线：虚线为实现，实线为继承）

ArrayList

ArrayList 是基于 动静数组 实现，容量能主动增长的汇合。随机拜访效率高 ，随机插入、随机删除效率低。 线程不平安，多线程环境下能够应用 Collections.synchronizedList(list) 函数返回一个线程平安的 ArrayList 类，也能够应用 concurrent 并发包下的 CopyOnWriteArrayList 类。

动静数组，是指当数组容量不足以寄存新的元素时，会创立新的数组，而后把原数组中的内容复制到新数组。

次要属性：

1// 存储理论数据，应用 transient 润饰，序列化的时不会被保留
2transient Object[] elementData;
3// 元素的数量，即容量。4private int size;

数据结构：动静数组

特色：

1. 容许元素为 null；
2. 查问效率高、插入、删除效率低，因为大量 copy 原来元素；
3. 线程不平安。

应用场景：

1. 须要疾速随机拜访元素
2. 单线程环境

罕用办法介绍

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    }

1. 判断以后数组是否为空，如果是则创立长度为 10（默认）的数组，因为 new ArrayList 的时没有初始化；
2. 判断是否须要扩容，如果以后数组的长度加 1（即 size+1）后是否大于以后数组长度，则进行扩容 grow()；
3. 最初在数组开端增加元素，并 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. 创立新数组，长度扩充为原数组的 1.5 倍（oldCapacity >> 1 就是相当于 10>>1==10/2=5，二进制位运算）；
2. 如果扩充 1.5 倍还是不够，则依据理论长度来扩容，比方 addAll() 场景；
3. 将原数组的数据应用 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    }

1. 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 <=2，否则报 IndexOutOfBoundsException 异样；
2. 扩容查看；
3. 通过拷贝形式，把数组地位为 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    }

1. 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 小于 <2，下标是从 0 开始的，size= 2 阐明下标只有 0 和 1；
2. 保留被笼罩的值，因为最初须要返回旧的值；
3. 新元素笼罩地位为 index 的旧元素，返回旧值。

get(index) 流程：通过下标获取 list 中的数据

1    public E get(int index) {2        rangeCheck(index);
3        return elementData(index);
4    }

1. 判断下标有没有越界；
2. 间接通过数组下标来获取数组中对应的元素，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    }

1. 查看指定地位是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 < 2；
2. 保留要删除的值，因为最初须要返回旧的值；
3. 计算出须要挪动元素个数，再通过拷贝使数组内地位为 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    }

1. 遍历数组，比拟 obejct 是否存在于数组中；
2. 计算出须要挪动元素个数，再通过拷贝使数组内地位为 index+1 到 size-1 的元素往前挪动一位，把数组最初一个元素设置为 null（精辟小技巧）。

总结：

1. new ArrayList 创建对象时，如果没有指定汇合容量则初始化为 0；如果有指定，则依照指定的大小初始化；
2. 扩容时，先将汇合扩充 1.5 倍，如果还是不够，则依据理论长度来扩容，保障都能存储所有数据，比方 addAll() 场景。
3. 如果新扩容后数组长度大于（Integer.MAX_VALUE-8），则抛出 OutOfMemoryError。
4. 倡议在应用的时候，先评估一下要存多少数据，而后就能够大抵或者精确的给 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}

数据结构：双向链表

特色：

1. 容许元素为 null；
2. 插入和删除效率高，查问效率低；
3. 程序拜访会十分高效，而随机拜访效率（比方 get 办法）比拟低；
4. 既能实现栈 Stack（后进先出），也能实现队列（先进先出）, 也能实现双向队列，因为提供了 xxxFirst()、xxxLast() 等办法；
5. 线程不平安。

应用场景：

1. 须要疾速插入，删除元素
2. 依照程序拜访其中的元素
3. 单线程环境

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    }

1. 创立一个新结点，结点元素 e 为传入参数，前继节点 prev 为“以后链表 last 结点”，后继节点 next 为 null；
2. 判断以后链表 last 结点是否为空，如果是则把新建结点作为头结点，如果不是则把新结点作为 last 结点。
3. 最初返回 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    }

1. 查看 index 是否在数组范畴内，如果数组长度是 2，则 index 必须 >=0 并且 < 2；
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    }

1. 判断 first 结点是否为空，如果是则报 NoSuchElementException 异样；
2. 如果不为空，则把待删除结点的 next 结点的 prev 属性赋值为 null，达到删除头结点的成果。
3. 返回删除值。

Vector

Vector 是矢量队列，也是基于动静数组实现，容量能够主动扩容。跟 ArrayList 实现原理一样，然而 Vector 是 线程平安 ，应用 Synchronized 实现线程平安，性能十分差， 已被淘汰，应用 CopyOnWriteArrayList 代替 Vector。

次要属性：

1// 存储理论数据
2protected Object[] elementData;
3// 动静数组的理论大小
4protected int elementCount;
5// 动静数组的扩容系数
6protected int capacityIncrement;

数据结构：动静数组

特色：

1. 容许元素为 null；
2. 查问效率高、插入、删除效率低，因为须要挪动元素；
3. 默认的初始化大小为 10，没有指定增长系数则每次都是扩容一倍，如果扩容后还不够，则间接依据参数长度来扩容；
4. 线程平安，性能差（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()

特色：先进后出

实现原理：

1. Stack 执行 push() 时，将数据推动栈，即把数据追加到数组的开端。
2. Stack 执行 peek 时，取出栈顶数据，不删除此数据，即获取数组首个元素。
3. Stack 执行 pop 时，取出栈顶数据，在栈顶删除数据，即删除数组首个元素。
4. 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

数据结构：动静数组

特色：

1. 线程平安；
2. 读多写少，比方缓存；
3. 不能保障实时一致性，只能保障最终一致性。

毛病：

1. 写操作，须要拷贝数组，比拟耗费内存，如果原数组容量大的状况下，可能触发频繁的 Young GC 或者 Full GC；
2. 不能用于实时读的场景，因为读取到数据可能是旧的，能够保障最终一致性。

实现原理：

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    }

好的，以上便是明天分享的内容。心愿你有所播种。

对老铁最大激励就是点个 在看 && 转发 在看 || 转发。可二选一。哈哈哈！