ArrayList: 底层使用数组来存储列表的元素，例如 a[i] = element。
- 可重复且允许插入 null 值；
- 数组默认初始容量值为10，往后每次容量不足时扩容50%，实际调用 System.arraycopy() 方法实现；
- 建议预估并设置初始化容量值，可有效避免多次进行扩容带来的性能问题。
数组的优/劣势
- 优势：随机访问 get/set 元素速度最快，仅需要O(1)的时间复杂度。
- 劣势：remove/search 元素速度较慢，达到O(n)的时间复杂度。
主要成员变量
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // 非私有是为了简化嵌套类的访问，调试访问
private int size;
// 其余略过...
// 此处存在一个细节，即初始化时 elementData 为空数组；
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
}
add 方法及扩容剖析
使用该方法将元素添加至列表末尾，详见如下：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 容量不足时进行扩容处理，Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 默认初始时，将进行扩容为 DEFAULT_CAPACITY=10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 结构变更次数+1
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 真正进行扩容的方法
}
// 实际进行扩容的方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 容量增大为原来的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity); // 底层使用 System.arraycopy()
}
get 方法剖析
该方法可实现根据数组下标获取列表中的元素，详见如下：
public E get(int index) {
rangeCheck(index); // 判断是否越界
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index]; // 直接根据数组下标获取元素
}
ArrayList 为什么是非线程安全的？
众所周知，ArrayList 是非线程安全的，接下来将探索 ArrayList 为什么是非线程安全的。先看看如下代码：
// 添加元素的方法
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e; // size++ 是出现非线程安全的地方之一
return true;
}
其中 size++ 是非原子操作，可拆分为以下两个部分：
- n = size + 1； // 先加1
- size = n；// 再赋值
假设现在有两个线程：thread-a 和 thread-b，并出现以下执行顺序时(假设 size 初始值为1)，则会发生不正确的行为：
1. thread-a：n = size + 1
2. thread-b：n = size + 1；
3. thread-b: size = n;
4. thread-a: size = n; // 此时size并不是期望的值3，而是等于2
此时就会出现非线程安全情况，其他情况就不一一列举，留给读者探索。
线程安全的List
- Vector：方法的实现方式与 ArrayList 基本相同，底层使用 synchronized 修饰方法，降低了效率。
- Collections.synchronizedList(new ArrayList(...))：官方文档推荐方式，底层实现使用 synchronized(mutex) 方式。
ArrayList VS LinkedList
- ArrayList 基于动态数组，LinkedList 基于链表的数据结构；
- ArrayList 随机访问 set/get 速度快，LinkedList 随机访问速度较慢，需要从表头开始遍历；
- LinkedList 插入和删除操作速度快，ArrayList 插入和删除操作速度较慢；
- LinkedList 可作为队列来使用。
网友评论