类继承关系
- public class ArrayList<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList 继承 AbstractList, 也实现了 List 和 RandomAccess(一个空接口, 也就是标记接口.),Cloneable(可被克隆), Serializable 接口.
类属性
- // 默认容量
- private static final int DEFAULT_CAPACITY = 10;
- // 空对象数组(initialCapacity == 0 时返回)
- private static final Object[] EMPTY_ELEMENTDATA = {};
- // 调用无参构造方法, 返回的是该数组
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- // 元素数组, 保存添加到 ArrayList 中的元素
- transient Object[] elementData;
- //ArrayList 大小
- private int size;
elementData 是 transient 修饰, 所以 elementData 不能被序列化. 但是 ArrayList 又是可以被序列化的, 这是为何?
因为 ArrayList 有两个方法 writeObject,readObject 用于序列化和反序列化. elementData 是 transient 修饰是为了避免 ArrayList 扩容 (1.5 倍) 导致的空间浪费
序列化的时候 elementData 的数据会被写到 ObjectOutputStream 中
- private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException{
- // Write out element count, and any hidden stuff
- int expectedModCount = modCount;
- s.defaultWriteObject();
- // Write out size as capacity for behavioural compatibility with clone()
- s.writeInt(size);
- // Write out all elements in the proper order.
- for (int i=0; i<size; i++) {
- s.writeObject(elementData[i]);
- }
- if (modCount != expectedModCount) {
- throw new ConcurrentModificationException();
- }
- }
反序列化的时候会从 ObjectInputStream 读取出来
- private void readObject(java.io.ObjectInputStream s)
- throws java.io.IOException, ClassNotFoundException {
- elementData = EMPTY_ELEMENTDATA;
- // Read in size, and any hidden stuff
- s.defaultReadObject();
- // Read in capacity
- s.readInt(); // ignored
- if (size> 0) {
- // be like clone(), allocate array based upon size not capacity
- ensureCapacityInternal(size);
- Object[] a = elementData;
- // Read in all elements in the proper order.
- for (int i=0; i<size; i++) {
- a[i] = s.readObject();
- }
- }
- }
构造函数
指定容量
- 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);
- }
- }
默认
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- ArrayList(Collection<? extends E> c)
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray();
- if ((size = elementData.length) != 0) {
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- } else {
- // 空对象数组
- this.elementData = EMPTY_ELEMENTDATA;
- }
- }
ArrayList 如何扩容
- public boolean add(E e) {
- // 确保 elementData 数组的大小
- ensureCapacityInternal(size + 1);
- // 在结尾处添加元素
- elementData[size++] = e;
- return true;
- }
上面是 add(E e)方法的源码, 在添加元素前会调用 ensureCapacityInternal(size + 1); 确保 elementData 数组的大小.
- private void ensureCapacityInternal(int minCapacity) {
- // 判断元素数组是否为空数组
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- //minCapacity 最少 = DEFAULT_CAPACITY=10
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
其中 ensureCapacityInternal 的源码片段首先判断 elementData 是否为无参构造器的空数组, 如果是的话, Math.max()取较大值赋值给 minCapacity, 最小是 10(默认容量). 然后, 调用 ensureExplicitCapacity:
- private void ensureExplicitCapacity(int minCapacity) {
- // List 结构性修改加 1
- modCount++;
- //minCapacity 大于 elementData 数组长度
- if (minCapacity - elementData.length> 0)
- // 增长
- grow(minCapacity);
- }
ensureExplicitCapacity 中 modCount 记录 List 结构性变化次数(结构性变化, 在迭代的过程中可能会造成错误结果).
紧接着, 如果 minCapacity 大于 elementData 数组长度则调用 grow(minCapacity)增长函数
- private void grow(int minCapacity) {
- // overflow-conscious code
- int oldCapacity = elementData.length;
- //oldCapacity>> 1 右移一位, 这里相当于扩容 1.5 倍
- 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);
- }
上面的扩容方法中 oldCapacity>> 1 表明 elementData.length 右移一位, 扩容后的容量为原始容量的 1.5 倍
主要函数
remove()函数
- public E remove(int index) {
- rangeCheck(index);
- modCount++;
- E oldValue = elementData(index);
- // 需要移动的元素个数
- int numMoved = size - index - 1;
- // 删除的不是最后一个元素
- if (numMoved> 0)
- //index 后的元素都向前移动一位
- System.arraycopy(elementData, index+1, elementData, index, numMoved);
- //size 减一, 释放引用, 方便垃圾回收器进行垃圾回收
- elementData[--size] = null; // clear to let GC do its work
- return oldValue;
- }
remove(int index)方法会先计算需要移动的元素个数, index 后的元素都向前移动一位(调用 System.arraycopy 方法移动), 然后 size 减一, 赋值为 null 释放引用, 方便垃圾回收器进行垃圾回收.
单线程环境下, 正确的删除元素, 应该使用 iterator()迭代器删除元素.
例如要删除集合中的 "a"
- Iterator<String> iterator = list.iterator();
- while (iterator.hasNext()){
- if ("a".equals(iterator.next())) {
- iterator.remove();
- }
- }
或者使用 lambda 表达式
list.removeIf("x"::equals);
set()函数, 会替换新值, 返回旧值.
- public E set(int index, E element) {
- // 检查索引
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- // 返回旧值
- return oldValue;
- }
get()函数, 获取元素
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
ArrayList 性能相关
在能够确定 ArrayList 容量大小的情况下尽量预估容量, 调用构造器 public ArrayList(int initialCapacity)指定大小, 避免因为自动扩容带来的性能开销.
使用 trimToSize()使 ArrayList 的内部数组大小减少为实际大小, 以此节省空间
- public void trimToSize() {
- modCount++;
- if (size < elementData.length) {
- elementData = (size == 0)
- ? EMPTY_ELEMENTDATA
- : Arrays.copyOf(elementData, size);
- }
- }
来源: http://www.bubuko.com/infodetail-3078695.html