ArrayList浅析 - 969251639/study GitHub Wiki
ArrayList是个基于数组实现的集合容器，默认大小为10
private static final int DEFAULT_CAPACITY = 10;
可以在构造函数中传入容器的大小
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
可以看到内部是通过elementData这个私有属性来保存数据
transient Object[] elementData;//transient表示
这里建议尽可能的在创建时初始化好大小否则会创建一个为空的数组出来
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
还有一个int类型的私有属性存储大小
private int size;
接下来浅析一些常用的方法的分析
- 判断容器是否为空
public boolean isEmpty() {
return size == 0;
}
很简单，直接根据size大小进行判断即可
- 是否包含指定的对象
public boolean contains(Object o) {
return indexOf(o) >= 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;
}
可以看到内部是一个一个对象的比较（通过equals方法），比较简单
- 转换成数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
可以看到底层是先创建一个Object类型的数组，然后调用底层的System.arraycopy方法将集合的内容copy到该数组后返回
- 获取
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
内部实现也比较简单，先边界检查，然后返回内部数组中的指定下标的内容
- 添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add方法第一步需要先判断是否能满足添加条件以及是否需要扩容，若可以的话则将数组中的下一个内容指向新增元素。这里最重要的是ensureCapacityInternal方法的分析
（1）如果是空数组，则返回至少10个大小的数组
（2）修改次数加1（modCount属性）
（3）判断是否需要扩容，需要则将旧的容器复制到新的容器中
- 移除元素
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;
}
遍历集合，判断是否是待删除元素（null用==，否则用equals），若是则调用fastRemove后返回
private void fastRemove(int index) {
modCount++;
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
}
这里要注意的是调用remove会触发arraycopy，即将原有集合copy一份，并拿掉带删除的那部分，故ArrayList的删除效率较差原因
- 迭代器
public Iterator<E> iterator() {
return new Itr();
}
Itr是个内部私有类
private class Itr implements Iterator<E>
通过实现Iterator接口来实现，这里要注意的是在对迭代器做操作的时候需要检查modCount属性的修改比较，也就是checkForComodification方法
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
这个内部类有个expectedModCount的私有属性
int expectedModCount = modCount;
用来在做迭代的时候就不要去update容器（可以查看在做update方法的时候都会修改这个值，比如remove方法，add方法等），所以下面的代码就会报错（防止多线程出错，毕竟ArrayList非线程安全）
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
for(String s : list) {
if(s.equals("3")) {
list.remove(s);
}
}
}
增强for循环内部使用迭代器来操作，在迭代器遍历过程中调用了list.remove方法，导致modcount+1了，与expectedModCount不等（创建迭代器时初始化好了）
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:886)
at java.util.ArrayList$Itr.next(ArrayList.java:836)
可以改成下面方式来做remove
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
list.add("5");
// for(String s : list) {
// if(s.equals("3")) {
// list.remove(s);
// }
// }
Iterator<String> iter = list.iterator();
while(iter.hasNext()) {
String s = iter.next();
if(s.equals("3")) {
iter.remove();
}
}
}