集合框架操作，精解四大集合框架
集合框架操作，精解四大集合框架MapQueue学过Java的都知道Java有四大集合框架，JDK版本1.8ListSet
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 是基于动态数组实现，容量能自动增长的集合。随机访问效率高，随机插入、随机删除效率低。线程不安全，多线程环境下可以使用 Collections.synchronizedList(list) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
动态数组，是指当数组容量不足以存放新的元素时，会创建新的数组，然后把原数组中的内容复制到新数组。
主要属性：
1//存储实际数据，使用transient修饰，序列化的时不会被保存
2transientObject[]elementData;
3//元素的数量，即容量。
4privateintsize;
数据结构：动态数组
特征：
- 允许元素为 null；
- 查询效率高、插入、删除效率低，因为大量 copy 原来元素；
- 线程不安全。
使用场景：
- 需要快速随机访问元素
- 单线程环境
常用方法介绍
add(element) 流程：添加元素
1privatestaticfinalintDEFAULT_CAPACITY=10;
2//添加的数据e放在list的后面
3publicbooleanadd(Ee){
4ensureCapacityInternal(size 1);
5elementData[size ]=e;
6returntrue;
7}
8privatevoidensureCapacityInternal(intminCapacity){
9ensureExplicitCapacity(calculateCapacity(elementData minCapacity));
10}
11privatestaticintcalculateCapacity(Object[]elementData intminCapacity){
12if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
13returnMath.max(DEFAULT_CAPACITY minCapacity);
14}
15returnminCapacity;
16}
- 判断当前数组是否为空，如果是则创建长度为 10（默认）的数组，因为 new ArrayList 的时没有初始化；
- 判断是否需要扩容，如果当前数组的长度加 1（即 size 1）后是否大于当前数组长度，则进行扩容 grow()；
- 最后在数组末尾添加元素，并 size 1。
grow() 流程：扩容
1privatevoidgrow(intminCapacity){
2//overflow-consciouscode
3intoldCapacity=elementData.length;
4intnewCapacity=oldCapacity (oldCapacity>>1);
5if(newCapacity-minCapacity<0)
6newCapacity=minCapacity;
7if(newCapacity-MAX_ARRAY_SIZE>0)
8newCapacity=hugeCapacity(minCapacity);
9//minCapacityisusuallyclosetosize sothisisawin:
10elementData=Arrays.copyOf(elementData newCapacity);
11}
- 创建新数组，长度扩大为原数组的 1.5 倍（oldCapacity >> 1就是相当于10>>1==10/2=5，二进制位运算）；
- 如果扩大 1.5 倍还是不够，则根据实际长度来扩容，比如 addAll() 场景；
- 将原数组的数据使用 System.arraycopy（native 方法）复制到新数组中。
add(index element) 流程：向指定下标添加元素
1publicvoidadd(intindex Eelement){
2rangeCheckForAdd(index);
3
4ensureCapacityInternal(size 1);//IncrementsmodCount!!
5System.arraycopy(elementData index elementData index 1
6size-index);
7elementData[index]=element;
8size ;
9}
10privatevoidrangeCheckForAdd(intindex){
11if(index>size||index<0)
12thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
13}
- 检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 <=2，否则报 IndexOutOfBoundsException 异常；
- 扩容检查；
- 通过拷贝方式，把数组位置为 index 至 size-1 的元素都往后移动一位，腾出位置之后放入元素，并 size 1。
set(index element) 流程：设置新值，返回旧值
1publicEset(intindex Eelement){
2rangeCheck(index);
3
4EoldValue=elementData(index);
5elementData[index]=element;
6returnoldValue;
7}
8privatevoidrangeCheck(intindex){
9if(index>=size)
10thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
11}
- 检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 小于<2，下标是从0开始的，size=2说明下标只有0和1；
- 保留被覆盖的值，因为最后需要返回旧的值；
- 新元素覆盖位置为 index 的旧元素，返回旧值。
get(index) 流程：通过下标获取list中的数据
1publicEget(intindex){
2rangeCheck(index);
3returnelementData(index);
4}
- 判断下标有没有越界；
- 直接通过数组下标来获取数组中对应的元素，get 的时间复杂度是 O(1)。
remove(index) 流程：按照下标移除lsit中的数据
1publicEremove(intindex){
2rangeCheck(index);
3modCount ;
4EoldValue=elementData(index);
5intnumMoved=size-index-1;
6if(numMoved>0)
7System.arraycopy(elementData index 1 elementData index
8numMoved);
9elementData[--size]=null;//cleartoletGCdoitswork
10returnoldValue;
11}
- 检查指定位置是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 < 2；
- 保留要删除的值，因为最后需要返回旧的值；
- 计算出需要移动元素个数，再通过拷贝使数组内位置为 index 1 到 size-1 的元素往前移动一位，把数组最后一个元素设置为 null（精辟小技巧），返回旧值。
remove(object) 流程：
1publicbooleanremove(Objecto){
2if(o==null){
3for(intindex=0;index<size;index )
4if(elementData[index]==null){
5fastRemove(index);
6returntrue;
7}
8}else{
9for(intindex=0;index<size;index )
10if(o.equals(elementData[index])){
11fastRemove(index);
12returntrue;
13}
14}
15returnfalse;
16}
17privatevoidfastRemove(intindex){
18modCount ;
19intnumMoved=size-index-1;
20if(numMoved>0){
21//数组拷贝
22System.arraycopy(elementData index 1 elementData index
23numMoved);
24}
25//方便GC
26elementData[--size]=null;
27}
- 遍历数组，比较obejct是否存在于数组中；
- 计算出需要移动元素个数，再通过拷贝使数组内位置为 index 1 到 size-1 的元素往前移动一位，把数组最后一个元素设置为 null（精辟小技巧）。
总结：
- new ArrayList 创建对象时，如果没有指定集合容量则初始化为 0；如果有指定，则按照指定的大小初始化；
- 扩容时，先将集合扩大 1.5 倍，如果还是不够，则根据实际长度来扩容，保证都能存储所有数据，比如 addAll() 场景。
- 如果新扩容后数组长度大于（Integer.MAX_VALUE-8），则抛出 OutOfMemoryError。
- 建议在使用的时候，先评估一下要存多少数据，然后就可以大致或者准确地给ArrayList指定大小，这样就会避免不断多次扩容对系统带来的开销。
LinkedList 是可以在任何位置进行插入和移除操作的有序集合，它是基于双向链表实现的，线程不安全。LinkedList 功能比较强大，可以实现栈、队列或双向队列。
主要属性：
1//链表长度
2transientintsize=0;
3//头部节点
4transientNode<E>first;
5//尾部节点
6transientNode<E>last;
7
8/**
9*静态内部类，存储数据的节点
10*前驱结点、后继结点，那证明至少是双向链表
11*/
12privatestaticclassNode<E>{
13//自身结点
14Eitem;
15//下一个节点
16Node<E>next;
17//上一个节点
18Node<E>prev;
19}
数据结构：双向链表
特征：
- 允许元素为 null；
- 插入和删除效率高，查询效率低；
- 顺序访问会非常高效，而随机访问效率（比如 get 方法）比较低；
- 既能实现栈 Stack（后进先出），也能实现队列（先进先出） 也能实现双向队列，因为提供了 xxxFirst()、xxxLast() 等方法；
- 线程不安全。
使用场景：
- 需要快速插入，删除元素
- 按照顺序访问其中的元素
- 单线程环境
add() 流程：
1publicbooleanadd(Ee){
2linkLast(e);
3returntrue;
4}
5voidlinkLast(Ee){
6finalNode<E>l=last;
7finalNode<E>newNode=newNode<>(l e null);
8last=newNode;
9if(l==null)
10first=newNode;
11else
12l.next=newNode;
13size ;
14modCount ;
15}
- 创建一个新结点，结点元素 e为传入参数，前继节点 prev 为“当前链表 last 结点”，后继节点 next 为 null；
- 判断当前链表 last 结点是否为空，如果是则把新建结点作为头结点，如果不是则把新结点作为 last 结点。
- 最后返回 true。
get(index) 流程：
1publicEget(intindex){
2checkElementIndex(index);
3returnnode(index).item;
4}
5/**
6*Returnsthe(non-null)Nodeatthespecifiedelementindex.
7*/
8Node<E>node(intindex){
9if(index<(size>>1)){
10Node<E>x=first;
11for(inti=0;i<index;i )
12x=x.next;
13returnx;
14}else{
15Node<E>x=last;
16for(inti=size-1;i>index;i--)
17x=x.prev;
18returnx;
19}
20}
21privatevoidcheckElementIndex(intindex){
22if(!isElementIndex(index))
23thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
24}
25privatebooleanisElementIndex(intindex){
26returnindex>=0&&index<size;
27}
- 检查 index 是否在数组范围内，假如数组长度是 2，则 index 必须 >=0 并且 < 2；
- index 小于“双向链表长度的 1/2”则从头开始往后遍历查找，否则从链表末尾开始向前遍历查找。
remove() 流程：
1publicEremove(intindex){
2checkElementIndex(index);
3returnunlink(node(index));
4}
5privatevoidcheckElementIndex(intindex){
6if(!isElementIndex(index))
7thrownewIndexOutOfBoundsException(outOfBoundsMsg(index));
8}
- 判断 first 结点是否为空，如果是则报 NoSuchElementException 异常；
- 如果不为空，则把待删除结点的 next 结点的 prev 属性赋值为 null，达到删除头结点的效果。
- 返回删除值。
Vector 是矢量队列，也是基于动态数组实现，容量可以自动扩容。跟 ArrayList 实现原理一样，但是 Vector 是线程安全，使用 Synchronized 实现线程安全，性能非常差，已被淘汰，使用 CopyOnWriteArrayList 替代 Vector。
主要属性：
1//存储实际数据
2protectedObject[]elementData;
3//动态数组的实际大小
4protectedintelementCount;
5//动态数组的扩容系数
6protectedintcapacityIncrement;
数据结构：动态数组
特征：
- 允许元素为 null；
- 查询效率高、插入、删除效率低，因为需要移动元素；
- 默认的初始化大小为 10，没有指定增长系数则每次都是扩容一倍，如果扩容后还不够，则直接根据参数长度来扩容；
- 线程安全，性能差（Synchronized），使用 CopyOnWriteArrayList 替代 Vector。
使用场景：多线程环境
为什么是线程安全的，看看下面的几个常用方法就知道了。
1publicsynchronizedvoidaddElement(Eobj){
2modCount ;
3ensureCapacityHelper(elementCount 1);
4elementData[elementCount ]=obj;
5}
6publicbooleanremove(Objecto){
7returnremoveElement(o);
8}
9publicsynchronizedbooleanremoveElement(Objectobj){
10modCount ;
11inti=indexOf(obj);
12if(i>=0){
13removeElementAt(i);
14returntrue;
15}
16returnfalse;
17}
18publicsynchronizedEget(intindex){
19if(index>=elementCount)
20thrownewArrayIndexOutOfBoundsException(index);
21
22returnelementData(index);
23}
24publicsynchronizedbooleanadd(Ee){
25modCount ;
26ensureCapacityHelper(elementCount 1);
27elementData[elementCount ]=e;
28returntrue;
29}
这几个常用方法中，方法都是使用同步锁synchronized修饰，所以它是线程安全的。
StackStack 是栈，先进后出原则，Stack 继承 Vector，也是通过数组实现，线程安全。因为效率比较低，不推荐使用，可以使用 LinkedList（线程不安全）或者 ConcurrentLinkedDeque（线程安全）来实现先进先出的效果。
数据结构：动态数组
构造函数：只有一个默认 Stack()
特征：先进后出
实现原理：
- Stack 执行 push() 时，将数据推进栈，即把数据追加到数组的末尾。
- Stack 执行 peek 时，取出栈顶数据，不删除此数据，即获取数组首个元素。
- Stack 执行 pop 时，取出栈顶数据，在栈顶删除数据，即删除数组首个元素。
- Stack 继承于 Vector，所以 Vector 拥有的属性和功能，Stack 都拥有，比如 add()、set() 等等。
1publicclassStack<E>extendsVector<E>{
2//....
3}
CopyOnWriteArrayList
CopyOnWriteArrayList 是线程安全的 ArrayList，写操作（add、set、remove 等等）时，把原数组拷贝一份出来，然后在新数组进行写操作，操作完后，再将原数组引用指向到新数组。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。这个是在JUC包目录下的。内部使用了AQS实现的锁。
java.util.concurrent
数据结构：动态数组
特征：
- 线程安全；
- 读多写少，比如缓存；
- 不能保证实时一致性，只能保证最终一致性。
缺点：
- 写操作，需要拷贝数组，比较消耗内存，如果原数组容量大的情况下，可能触发频繁的 Young GC 或者 Full GC；
- 不能用于实时读的场景，因为读取到数据可能是旧的，可以保证最终一致性。
实现原理：
CopyOnWriteArrayList 写操作加了锁，不然多线程进行写操作时会复制多个副本；读操作没有加锁，所以可以实现并发读，但是可能读到旧的数据，比如正在执行读操作时，同时有多个写操作在进行，遇到这种场景时，就会都到旧数据。
1publicclassCopyOnWriteArrayList<E>implementsList<E> RandomAccess Cloneable java.io.Serializable{
2privatestaticfinallongserialVersionUID=8673264195747942595L;
3
4/**Thelockprotectingallmutators*/
5finaltransientReentrantLocklock=newReentrantLock();
6//添加数据
7publicbooleanadd(Ee){
8//使用到了锁机制
9finalReentrantLocklock=this.lock;
10lock.lock();
11try{
12Object[]elements=getArray();
13intlen=elements.length;
14Object[]newElements=Arrays.copyOf(elements len 1);
15newElements[len]=e;
16setArray(newElements);
17returntrue;
18}finally{
19//释放锁
20lock.unlock();
21}
22}
23//移除数据
24publicEremove(intindex){
25//锁机制
26finalReentrantLocklock=this.lock;
27lock.lock();
28try{
29Object[]elements=getArray();
30intlen=elements.length;
31EoldValue=get(elements index);
32intnumMoved=len-index-1;
33if(numMoved==0)
34setArray(Arrays.copyOf(elements len-1));
35else{
36Object[]newElements=newObject[len-1];
37System.arraycopy(elements 0 newElements 0 index);
38System.arraycopy(elements index 1 newElements index
39numMoved);
40setArray(newElements);
41}
42returnoldValue;
43}finally{
44//释放锁
45lock.unlock();
46}
47}
好的，以上便是今天分享的内容。希望你有所收获。
对老铁最大鼓励就是点个在看&&转发 再看||转发。可二选一。哈哈哈！！！
