ArrayList

以数组实现。节约空间，但数组有容量限制。超出限制时会增加50%容量，用System.arraycopy()复制到新的数组，因此最好能给出数组大小的预估值。默认第一次插入元素时创建大小为10的数组。
  按照数组索引访问元素：get(int index)/set(int index)的性能很高，这是数组的优势。直接在数组末尾加入元素：add(e)的性能也高，但如果按索引插入、删除元素：add(i,e)、remove(i)、remove(e)，则要用System.arraycopy()来移动部分受影响的元素，性能就变差了，这是数组的劣势。
  ArrayList不是线程安全的，只能在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List list)方法返回一个线程安全的ArrayList对象，也可以使用concurrent并发包下的CopyOnWriteArrayList类。
  ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上根据源码我们知道就是通过索引序号进行快速访问，实现了Cloneable接口，能被克隆。

概念

  1. ArrayList扩容后的大小等于扩容前大小的1.5倍
  2. 扩容后将一直保存高水位线, 并不会因为remove而释放. 需要手动调用trimToSize()释放
  3. 默认最小初始化大小为10个

优缺点:

优点:

  • 遍历速度快

    论遍历ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。

缺点

  • 扩容效率差

    当ArrayList很大的时候，这样扩容还是挺浪费空间的，甚至会导致内存不足抛出OutOfMemoryError。扩容的时候还需要对数组进行拷贝，这个也挺费时的。所以我们使用的时候要竭力避免扩容，提供一个初始估计容量参数，以免扩容对性能带来较大影响。

重要参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
// 容器默认初始化大小
private static final int DEFAULT_CAPACITY = 10;
// 一个空对象
private static final Object[] EMPTY_ELEMENTDATA = {};
// 一个空对象，如果使用默认构造函数创建ArrayList，则默认对象内容是该值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// ArrayList存放对象的容器，后面的添加、删除等操作都是基于该属性来进行操作
transient Object[] elementData;
// 当前列表已使用的长度
private int size;
// 数组最大长度（2147483639），这里为什么是Integer.MAX_VALUE - 8是因为有些虚拟机在数组中保留了一些头部信息，防止内存溢出
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 修改次数用于 Fail-Fast 机制
protected transient int modCount = 0;

重要操作

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
// 默认构造函数, 将默认空对象数组赋值
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

// 自定义大小
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
      // 开辟数组空间
      this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
      // 大小为0赋值空对象
      this.elementData = EMPTY_ELEMENTDATA;
    } else {
      throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
    }
}
 
// 集合初始化
public ArrayList(Collection<? extends E> c) {
    // 一般toArray会生成新的对象
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
      // 如果生成的非数组将进行转换成数组形式
      if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
      // replace with empty array.
      this.elementData = EMPTY_ELEMENTDATA;
    }
}

get

1
2
3
4
5
6
7
8
9
 
public E get(int index) {
  // 越界检查
  rangeCheck(index);
  return elementData(index);
}
// 直接返回数据
E elementData(int index) {
  return (E) elementData[index];
}

set

1
2
3
4
5
6
7
8
 
public E set(int index, E element) {
  // 越界检查
  rangeCheck(index);
  E oldValue = elementData(index);
  // 返回旧数据赋值新数据	
  elementData[index] = element;
  return oldValue;
}

add

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
public boolean add(E e) {
  // 进行扩容操作(会触发 Fail-Fast 机制)
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}

public void add(int index, E element) {
  rangeCheckForAdd(index);

  ensureCapacityInternal(size + 1);  // Increments modCount!!
  // 调用底层数组拷贝, 在index处向后迁移 (如果在中间插入将需要进行数组copy移动)
  System.arraycopy(elementData, index, elementData, index + 1,
                   size - index);
  elementData[index] = element;
  size++;
}

remove

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
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);
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

trimToSize 释放空间

1
2
3
4
5
6
7
8
 
public void trimToSize() {
  modCount++;
  if (size < elementData.length) {
    elementData = (size == 0)
    	? EMPTY_ELEMENTDATA
    	: Arrays.copyOf(elementData, size);
  }
}

扩容机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
// ---------- 扩容操作
// ① 扩容
private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// ② 计算扩容
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 生成最小10位的数组
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
// ③ 明确扩容(修改modCount, 开启 Fail-Fast)
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倍 即:  原大小 + 原大小/2
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 计算新扩容大小满足输入的最小扩容大小
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  // 超过最大大小
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    // 溢出报错. 超过按照Integer最大值赋值
    newCapacity = hugeCapacity(minCapacity);
  // 调用底层创建新数组进行数组拷贝
  elementData = Arrays.copyOf(elementData, newCapacity);
}
 上一篇