ArrayList，
ArrayList，
概述
- 长度可变的数组，底层通过数组实现
- 存放的元素可以为null
- get/set速度快，add/remove需要复制数组，开销与操作的位置有关
- capacity是数组的长度，size是存放的元素的个数
- 没有实现同步，可使用
List list = Collections.synchronizedList(new ArrayList(...));使其同步
字段
// 默认初始化容量为10
private static final int DEFAULT_CAPACITY = 10;
// 使用无参构造器初始化的实例实际上是个静态的空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// ArrayList的元素存储在这个数组缓冲区里，ArrayList的capacity是这个
// 数组的length。空的ArrayList在第一次执行add时，数组长度会被扩展成DEFAULT_CAPACITY
private transient Object[] elementData;
// 元素个数
private int size;
elementData是存放的元素，capacity是这个数组的长度，size是存放的元素的个数。
构造器
Collection接口有这么一个约定，继承它的类应该至少提供两个构造器，一个用来创建空集合的无参构造器，一个可以复制指定集合的构造器。
All general-purpose Collection implementation classes (which typically implement Collection indirectly through one of its subinterfaces) should provide two "standard" constructors: a void (no arguments) constructor, which creates an empty collection, and a constructor with a single argument of type Collection, which creates a new collection with the same elements as its argument. In effect, the latter constructor allows the user to copy any collection, producing an equivalent collection of the desired implementation type. There is no way to enforce this convention (as interfaces cannot contain constructors) but all of the general-purpose Collection implementations in the Java platform libraries comply.
// 设定初始容量的构造器
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
// 无参构造器创建的实例，其实是一个空数组
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
// 创建包含了指定集合的实例。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
ArrayList有三个构造器：一个无参构造器，创建的实例其实是一个空数组{}；一个能指定数组初始容量的构造器，即创建一个Object数组，其长度为initialCapacity，指定初始数组的长度。如果在声明时就大概知道元素的个数，那么使用这个构造器就可以节省数组扩容和复制等的花销。；一个能复制指定集合的构造器，首先将collection转化为数组，再判断其类型是否为Object，如果不是的话，则强制转型为Object类型。至于为什么collection.toArray可能不会得到Object数组，可以参考c.toArray might (incorrectly) not return Object[] (see 6260652)。
方法实现
add/addAll
// 在末尾插入元素
public boolean add(E e) {
// 容量检查
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在elementData的size后一位存储新元素，同时size加1
elementData[size++] = e;
return true;
}
// 在指定位置插入元素
public void add(int index, E element) {
// index检查
rangeCheckForAdd(index);
// 容量检查
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
// 先将指定的集合c转化为数组，后面的操作与add方法差不多
Object[] a = c.toArray();
...
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
// 检验index
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// element扩容
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
// 把原数组中index到结束的元素复制到index+numNew的位置上
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 把要插入的数组复制到elementData的index位上
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
ArrayList有两个add方法，一个是在末尾插入元素，一个是在指定位置插入元素。使用第二种时要先检查指定的index是否小于size且大于0，之后都是容量检查，如果容量不够，就适量扩容。如果是在指定位置插入的话，将本来在index以及之后的元素复制到index+新集合长度后的位置，再把指定的集合转化为数组复制到index的位置。
addAll.png
扩容
private void ensureCapacityInternal(int minCapacity) {
// 如果elementData是一个空数组的话，即在初始化后第一次调用add方法时，默认扩容到DEFAULT_CAPACITY(长度为10)，或者指定的大小
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;
// 新的容量是旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容1.5倍还不够，就使用指定的数值为新的容量
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;
}
remove /removeAll
remove有两个方法，一个删除指定位置的元素，一个是删除指定元素。
public E remove(int index) {
rangeCheck(index);
modCount++;
// 获得要删除的位置的元素
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 如果要删除的不是最后一个元素，就把原数组中index+1位以及以后的元素都向前挪一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 显式地将最后一位赋为null，让GC起作用，同时size减1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
public boolean remove(Object o) {
// 遍历elementData，如果要删除的对象o为null的话，就用==来比较，否则使用equals方法来比较
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 这里的操作和remove()是一样的
fastRemove(index);
return true;
}
} else {
...
}
return false;
}
removeAll与remove(Object o)一样要遍历elementData，它使用contains()方法来判断遍历到的元素是否为要删除的元素。
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 跳过要删除的元素，将要保留的元素放在一起
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
// 如果因为异常中断了遍历，就将未遍历的部分放到已经完成的部分后
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// 将多余的部分显式赋为null，使GC起作用
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
modCount
这个字段用来记录list的修改次数，在增、删、等方法中都有出现过。集合的迭代器使用它来判断遍历lsit时，list是不是被修改了。这种机制被称为fail-fast
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
// 使用iterator获得集合的迭代器时，就将迭代器的expectedModCount 赋值为集合此时的modCount
int expectedModCount = modCount;
// 如果modCount在遍历期间改变了，就抛出异常
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在itr中，调用next、previous、set、add方法都会进行modCount的检查，保证迭代时的单线程操作。
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
// list改变后再执行hasNext时，执行checkForComodification抛出异常
Integer i = (Integer) iterator.next();
System.out.println(i);
if (i == 3) {
// list的modCount+1
list.add(4);
}
}
// output
1
2
3
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at com.how2j.text.Practice.main(Practice.java:22)
相关文章
- 暂无相关文章
用户点评