/**
* ArrayList详解及Vector简介
*/
public class TestArrayList2 {
public static void main(String[] args) {
/* ArrayList源码
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//泛型类<E> 实现List<E>
private static final int DEFAULT_CAPACITY = 10;
//默认容量10 当第一次添加元素时如果一次性添加数量小于等于10会将容器的容量capacity变为10
private static final Object[] EMPTY_ELEMENTDATA = {};
//空_元素数据
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//默认容量_空_元素数据 空数组 new ArrayList()无参时会将容器的数组设定为{}
transient Object[] elementData;
//elementData元素数据 Object[]数组 用于存放容器中的元素
private int size;
//.size()返回的size 容器中元素的数量
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);
}
}
//有参构造器 initial最初的 设定容器初始大小size为initialCapacity
//当参数==0时将elementData赋值为EMPTY_ELEMENTDATA
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//无参构造器 将elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList(Collection<? extends E> c) {
Object[] a = c.toArray();
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
elementData = EMPTY_ELEMENTDATA;
}
}
//将容器c传参给构造器 将this.size设为容器c的元素数 将this.elementData设为容器c的数组 如果c不是ArrayList类将数组转换为Object[]再赋值给elementData
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
//trim修剪 将elementData中的元素拷贝至新的数组[size] 修剪掉数组中null未使用的索引 将数组的长度改为存放的元素总数size
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//size最大值为int最大值-8
public int size() {
return size;
}
//.size()方法返回size值
public boolean isEmpty() {
return size == 0;
}
//当size为0时判断容器为空
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//从前往后遍历elementData 查找第一个和参数o相同的元素 如果参数是null则返回elementData中第一个null 不存在返回-1
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//indexOf()不返回-1即容器中存在和参数o相同的元素
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
//for循环从末位size-1往前查找
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
//elementData是容器的存放元素的数组 size是元素真实的总数 数组中元素是从index0往后顺序存入的 当数组没有存满时数组中后面的位为空
//Arrays.copyOf()创建一个新的数组 大小为size容器的元素真实总数 将elementData从[0]-[size-1]即所有元素拷贝到新数组中返回 返回类型为Object[]不是泛型
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
//将容器中的元素拷贝到和形参a一致的数组类型的数组中返回 如果a的长度小于size则返回一个新的数组T[size] 否则将元素拷贝到a中 从index0位开始 比size长时将[size]位设为null 返回a
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//返回索引位的元素 先判断index在不在size范围内
E elementData(int index) {return (E) elementData[index];}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//替换元素 返回被替换元素
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
//添加元素 先确保ensure 容量 如果elementData数组的长度不足会进行扩容
//将e赋值给[size]位 size++ size反映容器中元素的数量 每次增减元素size都会改变相应的数量
//add(E e)是增加一个元素的方法 所以将size+1传参进ensureCapacityInternal()方法中判断是否需要扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//minCapacity为需要的容器空间 calculateCapacity(elementData, minCapacity)方法如下
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//calculate计算 如果容器由无参构造器生成，在初始化后没有添加元素即elementData依然等于默认容量空{}，将默认容量10和需要的容器空间比较选最大值返回 即初次添加元素后容器的size最小为10
//如果容器内已存在元素则返回所需空间的值 返回值作为参数传给ensureExplicitCapacity()方法如下
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//explicit明确的 modCount修改计数 如果所需空间比当前elementData的长度大则需要扩容grow 方法如下
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
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);
}
//先预设将数组的长度变为1.5倍 如果满足所需空间则扩容1.5 如果不满足则将空间扩容至所需空间的大小 扩容会生成新的数组并将原数组拷贝过来
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//和add(E)基本相同 将从index位开始的元素拷贝到index+1位开始的位置 长度size-index即后移元素的总数 拷贝后将新元素赋值给index位
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
//将被删除的元素返回 判断index位后面还有元素则将后面元素从index+1位开始拷贝至index位开始 将--size即原最后一个元素位赋null size减小
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
//for遍历数组直到size位之前 当匹配到第一个相同元素时删除并返回true 所以只能删除第一个 fastRemove()方法不返回boolean
public void clear() {
modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//遍历数组全设为null size设为0
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
//和add()类似 如果所需空间大于数组的长度会扩容 拷贝原数组内容至新的数组中 再将形参c的数组拷贝到size位开始的位置即this容器的末尾
//返回值是判断形参c容器是否为空
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
//多了一个步骤判断index位及后面是否有元素 将index位及后面的元素拷贝到index+numNew开始的位置
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
//removeAll和retainAll都通过batchRemove()执行
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
//Objects.requireNonNull()判断c为null则抛异常 否则返回c batchRemove()方法如下
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
//r读 w写
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
//遍历判断this中的元素是否存在于c中 complement补充/交集
//如果取交集retainAll时complement为true 需要contains()为true 即当前元素在c中存在(true)==取交集(true) 执行拷贝
elementData[w++] = elementData[r];
//如果取差集removeAll complement为false 需要contains()为false即当前元素在c中不存在 false==false 才执行拷贝
} finally {
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
//如果执行过程中出现异常导致没有完成数组的遍历 会将剩余的部分拷贝至已完成部分的末尾来结束方法
}
if (w != size) {
// clear to let GC do its work 当索引位赋null 原元素/对象不再被调用后会被垃圾回收GC
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
//w即符合要求的元素数 将符合的元素顺序放在数组的前面 将后面的位置全部赋null 完成交集或者差集
}
}
return modified;
}
*/
}
}
/*
Vector为List接口的实现类 基础用法和ArrayList相同 vector矢量
ArrayList线程不安全 效率高
Vector线程安全 效率低
类似StringBuilder和StringBuffer的区别
List<String> v = new Vector<>();同样通过List接口引用
Vector<>()源码：
protected Object[] elementData;同样使用elementData数组存储元素
protected int elementCount;用于表示元素总数 作用同size
public Vector() {this(10);}无参构造器直接初始size为10
private void grow(int minCapacity) {
// 扩容
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
//Vector容器的空间是2倍扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
*/