Java集合List ArrayList，LinkedList和Vector底层实现

文章目录概览Collection1.Set2.List3.QueueListArrayList基本属性构造器add方法和扩容rove方法线程问题CoyOnWriteArrayListLinkedListNode结点基本属性构造器add方法rove方法Vector基本属性构造器Vector的扩容
概览
容器主要包括Collection和Ma两种，Collection存储着对象的集合，而Ma存储着键值对（两个对象）的映射表。
本章介绍的主要是List
Collection1.Set
TeSet：基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如HashSet，HashSet查找的时间复杂度为O(1)，TeSet则为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起作用的)
transientObject[]elentData;
默认的初始容量
rivatestaticfinalintDEFAULT_CAPACITY=10;
ArrayList的大小（它是元素个数）
rivateintsize;
数组的最大长度
rivatestaticfinalintMAX_ARRAY_SIZE=2147483639;构造器
无参构造器
开始创建出时，该数组的长度是1，而size是0，当进行第一次的add时，elentData将会被“复制”为长度为10的默认值；
使用默认构造函器创建，则默认对象内容是该值DEFAULTCAPACITY_EMPTY_ELEMENTDATA
rivatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};
构造一个初始容量为10的空列表
ubcArrayList(){
this.elentData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}int参数的构造器
构造一个具有指定初始容量的空列表，如果传入的参数大于等于0，那么就直接使用参数数值进行初始化，如果参数值小于0，那么直接直接抛出异常；
ubcArrayList(intinitialCaacity){
if(initialCaacity>0){
this.elentData=newObject[initialCaacity];
}elseif(initialCaacity==0){
this.elentData=EMPTY_ELEMENTDATA;
}else{
townewIllegalArgumentExcetion("IllegalCaacity:"+
initialCaacity);
}
}Collection参数的构造器
构造一个包含指定集合的元素的列表，其顺序由集合的迭代器返回；
将Collection<?extendsE>c中保存的数据，首先转换成数组形式（toArray()方法），然后判断当前数组长度是否为0，如果为0则替换为空数组（EMPTY_ELEMENTDATA）；否则先判断是否为Object数组类型，然后进行数据拷贝；
ubcArrayList(Collection<?extendsE>c){
elentData=c.toArray();
if((size=elentData.length)!=0){
if(elentData.getClass()!=Object[].class)
elentData=Arrays.coyOf(elentData,size,Object[].class);
}else{
this.elentData=EMPTY_ELEMENTDATA;
}
}方法Arrays.coyOf
它新建了一个数组并且将原数组的内容拷贝到长度为newLength的新数组中，并且返回该新数组；
ubcstatic<T,U>T[]coyOf(U[]original,intnewLength,Class<?extendsT[]>newTye){
先判断类型是否正确，如果正确则直接创建一个Object数组，长度为传入的长度newLength
T[]coy=((Object)newTye==(Object)Object[].class)
?(T[])newObject[newLength]
否则，执行使用反射创建一个对应的数组
:(T[])Array.newInstance(newTye.getComonentTye(),newLength);
Syst.arraycoy(original,0,coy,0,
Math.min(original.length,newLength));
turncoy;
}方法Syst.arraycoy
它就是从指定的源数组将元素中复制到目标数组，复制从指定的位置开始，到设定的复制长度结束，然后从目标数组的指定起始位置依次插入；
src源数组
srcPos源数组要复制的起始位置
dest要赋值到的目标数组
destPos目标数组放置的起始位置
length复制的长度
使用了native关键字，说明调用的是CC++其他语言写的底层函数
ubcstaticnativevoidarraycoy(Objectsrc,intsrcPos,
Objectdest,intdestPos,
intlength);
add方法和扩容
booleanadd(Ee)方法
ubcbooleanadd(Ee){
由于添加一个元素，因此先size+1判断数组的容量是否够用
ensuCaacityInternal(size+1);
上述判断或者扩容完成后，进行赋值，并且长度size++
elentData[size++]=e;
turntrue;
}
确保数组内部容量
rivatevoidensuCaacityInternal(intminCaacity){
如果使用的是无参构造器，那么第一次添加一个值后
会判断目前数组的地址是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA的地址
if(elentData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
如果是，比较传入的minCaacity和DEFAULT_CAPACITY的值，无参构造时，肯定设置为DEFAULT_CAPACITY
如果再次扩容那么，下此minCaacity就是size+1的值
minCaacity=Math.max(DEFAULT_CAPACITY,minCaacity);
}
确认实际容量，将选择好的数组容量传入
ensuExcitCaacity(minCaacity);
}
rivatevoidensuExcitCaacity(intminCaacity){
modCount++;
如果传入的数组容量minCaacity大于原本的长度elentData.length就会扩容
if(minCaacity-elentData.length>0)
传入扩容的长度
grow(minCaacity);
}
rivatevoidgrow(intminCaacity){
获取原本的容量
intoldCaacity=elentData.length;
计算新的容量数值（右移一位代表oldCaacity2）
右移的值加上原来的数值就是新的容量值，即1.5*oldCaacity
扩容为原来容量的1.5倍
intnewCaacity=oldCaacity+(oldCaacity>>1);
if(newCaacity-minCaacity<0)
newCaacity=minCaacity;
if(newCaacity-MAX_ARRAY_SIZE>0)
newCaacity=hugeCaacity(minCaacity);
使用数组工具类并传入新的长度以及数组的地址进行复制扩容
elentData=Arrays.coyOf(elentData,newCaacity);
}add总结add元素时，先确定数组是否能够继续存储元素；
如果是第一次add元素，那么将数组长度默认值赋值给当前数组长度，并进行扩容；
扩容时将会扩容为原来容量的1.5倍；
扩容成功后将元素再添加进数组中并发会true。
voidadd(intindex,Eelent)方法
该方法和第一个方法其实都类似，只不过该方法可以确定插入的索引；
ubcvoidadd(intindex,Eelent){
判断插入的索引位置是否正确
rangeCheckForAdd(index);
确保容量（或扩容）
ensuCaacityInternal(size+1);
对源数组进行复制处理（位移），从index+1到size-index
即向后移动位于当前位置和后面的元素
Syst.arraycoy(elentData,index,elentData,index+1,
size-index);
在指定的位置赋值
elentData[index]=elent;
size++;
}booleanaddAll(intindex,Collection<?extendsE>c)方法
addAll方法首先传过来的Collection集合转换为数组，然后做扩容处理，接着使用Syst.arraycoy把转换后的数组复制到列表尾部；rove方法
Erove(intindex)方法
根据索引删除元素，并返回删除的元素；
ubcErove(intindex){
检查传入的索引是否正确
rangeCheck(index);
modCount++;
获取要删除的元素值
EoldValue=elentData(index);
判断是否删除的是最后一个元素，如果不是，则将删除位置后的元素向左移numMoved个位置
intnumMoved=size-index-1;
if(numMoved>0)
从index+1开始移动元素到数组的index位置，即，将删除的元素直接覆盖
Syst.arraycoy(elentData,index+1,elentData,index,
numMoved);
直接将删除的元素置为nl，并且等待垃圾收集器收集
size减一
elentData[--size]=nl;cleartoletGCdoitswork
返回删除的元素值
turnoldValue;
}
判断索引是否正确，错误时抛出IndexOutOfBoundsExcetion异常
rivatevoidrangeCheck(intindex){
if(index>=size)
townewIndexOutOfBoundsExcetion(outOfBoundsMsg(index));
}
由于是数组，直接根据索引获取元素值即可
EelentData(intindex){
turn(E)elentData[index];
}rove总结先判断删除的索引是否正确；
获取到将要删除的元素；
通过数组的赋值将删除的元素覆盖，并且将数组的最后一位置为nl。
线程问题
ArrayList是线程不安全的集合；
示例：
ubcclassListTest{
ubcstaticvoidmain(String[]args){
ArrayList<String>st=newArrayList<>();
for(inti=1;i<=3;i++){
newTead(()->{
st.add(UUID.randomUUID().toString().substring(0,8));
Syst.out.rintln(st);
},String.valueOf(i)).start();
}
}
}上述代码运行结果如下，而且每次运行的结果“类型”可能都不同
[nl,697f0ec8,b502b230]
[nl,697f0ec8,b502b230]
[nl,697f0ec8,b502b230]如果再将线程数量调大，会发现有如下结果：
[nl,c3d3c6ae,34f4af7e,9aa99807,04816aec]
...
atjava.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
atjava.util.ArrayList$Itr.next(ArrayList.java:851)[nl,c3d3c6ae,34f4af7e,9aa99807,04816aec]
atjava.util.AbstractCollection.toString(AbstractCollection.java:461)
atjava.lang.String.valueOf(String.java:2994)
atjava.io.PrintStam.rintln(PrintStam.java:821)
atListTest.lambda$0(ListTest.java:11)
atjava.lang.Tead.run(Tead.java:745)
java.util.ConcurntModificationExcetion[nl,c3d3c6ae,34f4af7e,9aa99807,04816aec]
...
atjava.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
atjava.util.ArrayList$Itr.next(ArrayList.java:851)[nl,c3d3c6ae,34f4af7e,9aa99807,04816aec]
atjava.util.AbstractCollection.toString(AbstractCollection.java:461)
atjava.lang.String.valueOf(String.java:2994)
atjava.io.PrintStam.rintln(PrintStam.java:821)
atListTest.lambda$0(ListTest.java:11)
atjava.lang.Tead.run(Tead.java:745)
java.util.ConcurntModificationExcetion出现异常
java.util.ConcurntModificationExcetion，并发修改异常
导致原因
并发情况下多线程对集合进行增，删，改等操作，从而使给集合出现修改错误；
解决方案使用Vector代替；
使用Collections.synconizedList()；
使用JUC的CoyOnWriteArrayList；
CoyOnWriteArrayList
booleanadd(Ee)方法
ubcbooleanadd(Ee){
对修改的内容加锁
finalReentrantLocklock=this.lock;
lock.lock();
try{
getArray()方法直接获取到原本的数组地址并赋值给elents
Object[]elents=getArray();
获取数组长度
intlen=elents.length;
直接进行复制的时候将容量加一，不用继续去扩容
Object[]newElents=Arrays.coyOf(elents,len+1);
存储元素e
newElents[len]=e;
将添加完毕的数组再次赋值给原本的数组
setArray(newElents);
turntrue;
}finally{
释放锁
lock.unlock();
}
}适用场景
CoyOnWriteArrayList在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。
但是CoyOnWriteArrayList有其缺陷：内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。所以CoyOnWriteArrayList不适合内存敏感以及对实时性要求很高的场景。
总结
CoyOnWrite容器，即写时复制；往一个容器添加元素的时候，不直接往当前容器Object[]添加，而是先将当前的容器Object[]进行coy复制，复制出一个新的容器Object[]newElents，然后在新的容器Object[]newElents中添加元素，添加完毕后再将原容器的引用指向新的容器，也就是setArray(newElents)；这样的好处就是可以对CoyOnWrite容器进行并发的读取而不需要加锁，因为当前容器不会添加任何元素。因此，CoyOnWrite容器也是一种读写分离的思想。LinkedList
LinkedList的底层是通过双向链表来实现的，LinkedList对于添加和删除较快，而查询元素较慢，并且也是线程不安全的；单链表结构与顺序存储结构的对比：
存储分配方式：
顺序存储结构：用一段连续的存储单元依次存储线性表的数据元素；
单链表：用一组任意的存储单元存放线性表的元素。
时间性能：
查找：
顺序存储结构O(1);
单链表O(n)。
插入和删除：
顺序存储结构需要平均移动表长一半的元素为O(n)；
单链表仅为O(1)。
空间性能：
顺序存储结构需要预先分配存储空间，若分大，浪费，若分小，容易溢出；
单链表不需要预先分配存储空间，只要有才分配，元素个数不受限制。Node结点
rivatestaticclassNode<E>{
每个结点存储的元素值
Eit;
当前结点的后继
Node<E>next;
当前节点的前驱
Node<E>v;
Node构造器，每次创建Node时，都要传入这三个值
Node(Node<E>v,Eelent,Node<E>next){
this.it=elent;
this.next=next;
this.v=v;
}
}
双向链表，头和尾各有first和last指针；基本属性
链表中存放的元素个数，初始为0
transientintsize=0;
头节点
transientNode<E>first;
尾节点
transientNode<E>last;
构造器
无参构造器
ubcLinkedList(){}创建一个空的链表；
Collection参数的构造器
ubcLinkedList(Collection<?extendsE>c){
this();
addAll(c);
}构造一个包含指定集合的元素的列表，其顺序由集合的迭代器返回；
booleanaddAll(Collection<?extendsE>c)方法，将传入的指定的集合中的所有元源添加到该链表中；add方法
booleanadd(Ee)方法
ubcbooleanadd(Ee){
直接调用nkLast方法进行尾插
nkLast(e);
turntrue;
}
voidnkLast(Ee){
获取出last尾指针（类似“备份”）
finalNode<E>l=last;
*
将传入的元素e，使用Node的有参构造器创建一个新的结点newNode，
该节点的前驱是上一步获取的last指针（l指针），后继为nl，
*
finalNode<E>newNode=newNode<>(l,e,nl);
使得尾指针last指向上步创建的新的结点newNode
last=newNode;
如果l指针为nl，说明是第一次添加元素，first和last都为nl
if(l==nl)
由于第一次添加元素，则让first指针也指向新创建的结点newNode
first=newNode;
else
否则，就让获取出last指针的l指针的后继指向newNode结点
l.next=newNode;
长度+1
size++;
modCount++;
}add总结add方法使用的是尾插法进行添加操作的；
都会先获取一个维护last尾指针的l指针；
将获取的l指针用作新创建结点的前驱（v），由于是尾插则新结点的后继是nl；
重新赋值last尾指针，让其指向新的结点元素；
判断l指针是否为空（第一次操作时为空链表，last和first指针都指向nl）；
不为空时，就让l指针的后继next指向新结点，将前后两个结点“串联”起来。
voidaddFirst(Ee)方法
ubcvoidaddFirst(Ee){
nkFirst(e);
}
rivatevoidnkFirst(Ee){
和尾插法类似，先获取出first指针
finalNode<E>f=first;f
创建新的结点元素，因为头插法，前驱为nl，后继就是上步获取的f指针（first指针）
finalNode<E>newNode=newNode<>(nl,e,f);
让first指针指向新的结点元素
first=newNode;
判断是否为空，如果为空说明第一次添加
if(f==nl)
让last指针也指向新结点
last=newNode;
else
否则，就让
f.v=newNode;
size++;
modCount++;
}上述的两个添加方法，最不能理解的就是前驱和后继的指向问题。尾插法来说，在创建新的结点时其新结点的前驱是l指针（也可以说是链表原本的最后一个结点），如何让新添加的元素和之前的尾元素关联起来呢？
新结点的前驱是上个元素的结点，因此直接让l.next指向新结点元素即可（虽然last指针已经指向新结点元素，但是备份的l指针不仅保存在新结点的前驱中，同时也是上一个尾结点）。rove方法
Erove()方法
ubcErove(){
turnroveFirst();
}
ubcEroveFirst(){
获取头指针first
finalNode<E>f=first;
只要头指针不为空，说明存在元素，否则抛出异常
if(f==nl)
townewNoSuchElentExcetion();
进行删除
turnunnkFirst(f);
}
rivateEunnkFirst(Node<E>f){
获取出要删除的结点中的元素elent
finalEelent=f.it;
获取要删除结点的后继，也就是下一个节点
finalNode<E>next=f.next;
下面两步手动置为nl，让GC能够更快的清理无指向的空结点
f.it=nl;
f.next=nl;helGC
让头指针first指向之前获取出的头结点的下一个结点元素
first=next;
如果下一个结点元素为nl，说明删除的就是链表中的最后一个元素，所以让尾指针也置为nl
if(next==nl)
last=nl;
else
否则，让新的头结点的前驱置为nl（断开与之前头结点的最后联系）
next.v=nl;
长度-1
size--;
modCount++;
turnelent;
}rove总结先获取头指针first；
让next结点指向要删除结点的后继结点；
使要删除的结点的元素和后继都置为nl；
接着让头指针first指向next结点；
判断删除的是否是最后一个元素，如果是则让last指针也指向nl；
否则，让next结点的前驱，也就是现在的头结点的前驱置为nl；EroveLast()方法和EroveFirst()类似；Vector
Vector是List的另外一个实现类，完全支持List的全部功能，Vector是一个比较古老的集合，JDK1.0就已经存在，它的底层和ArrayList一样，也是一个Object数组；Vector与ArrayList的主要是区别是，Vector是线程安全的，但是性能比ArrayList要低；基本属性
存储元素的数组
rotectedObject[]elentData;
记录数组的元素个数
rotectedintelentCount;
数组的增长系数
rotectedintcaacityIncnt;
构造器
ubcVector(){
默认容量为10
this(10);
}
ubcVector(intinitialCaacity){
this(initialCaacity,0);
}
传入初始容量和数组的增长系数
ubcVector(intinitialCaacity,intcaacityIncnt){
suer();
if(initialCaacity<0)
townewIllegalArgumentExcetion("IllegalCaacity:"+
initialCaacity);
this.elentData=newObject[initialCaacity];
this.caacityIncnt=caacityIncnt;
}
将指定的集合元素转化为Vector
ubcVector(Collection<?extendsE>c){
elentData=c.toArray();
elentCount=elentData.length;
c.toArraymight(incorctly)notturnObject[](see6260652)
if(elentData.getClass()!=Object[].class)
elentData=Arrays.coyOf(elentData,elentCount,Object[].class);
}
Vector的扩容
其实Vector和ArrayList的add，rove方法大致都类似，Vectoradd元素（ensuCaacityHeler方法）时，都要调用该方法来确保足够的容量，代码如下:
rivatevoidgrow(intminCaacity){
overflow-conscious
intoldCaacity=elentData.length;
根据caacityIncnt进行判断，caacityIncnt>0增加caacityIncnt个容量，否则扩容为之前的2倍
intnewCaacity=oldCaacity+((caacityIncnt>0)?
caacityIncnt:oldCaacity);
if(newCaacity-minCaacity<0)
newCaacity=minCaacity;
if(newCaacity-MAX_ARRAY_SIZE>0)
newCaacity=hugeCaacity(minCaacity);
也是利用Arrays.coyOf进行数组的复制
elentData=Arrays.coyOf(elentData,newCaacity);
}