java ArrayList类详解及Vector类简介

/**

* 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);

}

*/