Skip to content

类图:

ArrayList

使用数组实现的集合

支持随机访问

数据结构

java
// 用于存放数据
transient Object[] elementData;
// 元素实际数量
private int size;

Vector

线程安全版 ArrayList

通过在所有操作上加 syncronized 关键字保证线程安全,效率低,不推荐使用

LinkedList

底层使用链表实现

数据结构:

java
// 元素数量
transient int size = 0;
// 头节点
transient Node<E> first;
// 尾结点
transient Node<E> last;

常见问题

ArrayList 扩容倍数

扩容为原容量的 1.5 倍

java
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 容量扩为 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);
}

fail-fast 机制

错误检测机制,当某个线程对集合进行结构上的改变的操作时,不允许其他线程对其读写操作,否则会触发 fail-fast 机制,抛出 ConcurrentModificationException 异常

比如迭代器遍历集合中的元素,遍历前保存 modCount 临时变量为 expectedmodCount,其他线程改变集合结构时执行 modCount++,遍历结束对比 modCount 与 expectedmodCount 的值,发现不相等,则触发 fail-fast

List 的遍历

  1. 基于计数器的 for 循环遍历,适合支持随机访问的 List 如 ArrayList
  2. 使用迭代器 iterator 遍历
  3. foreach 循环遍历,内部使用 iterator 实现,代码简洁,但不能删除、替换元素

ArrayList 与 LinkedList 优缺点对比

ArrayList:

  • 支持随机访问,查找快
  • 顺序添加效率高
  • 删除、插入元素效率低,因为要移动元素(实际为数组元素复制)

LinkedList:

  • 不支持随机访问
  • 非头尾部插入、删除元素快(只需修改引用)
  • 节点除了存储元素还要存储指针,比 ArrayList 更占内存

为什么 ArrayList 中 Object[] elementData 用 transient 修饰

ArrayList 实现了 java.io.Serializable 接口并重写了 writeObject() 和 readObject() 方法,使用 transient 为了防止直接序列化 elementData 中的所有元素,因为部分可能是空,而是走 writeObject 序列化实际数量的元素,提高效率节省空间

关于 subList

subList 返回的是 java.util.ArrayList.SubList 实例,并且数据指向的是原 List 的 Object[] elementData,相当于原 List 的视图,修改原 List 或 SubList 任一个,另一个的数据也会改变,如果两边并发修改,可能触发 fail-fast

JDK 在 java.util 包中提供了常用集合实现:

  • List 有序集合
  • Map 键值对
  • Set 去重集合,使用 Map 实现
  • Queue 队列

类图