Java源码解读系列(一):ArrayList

dxyadc 2020-02-24

本文简单介绍了 ArrayList,并对扩容,添加,删除操作的源代码做分析。能力有限,欢迎指正。

ArrayList是什么?

ArrayList 就是数组列表,主要用来装载数据。底层实现是数组 Object[] elementData,当我们装载的是基本数据类型 int, long, boolean, shot...的时候我们只能存储他们对应的包装类型。

与它类似的是 LinkedList,和 LinkedList 相比,它的查找和访问元素的速度较快,但新增,删除的速度较慢。

线程安全吗?

线程不安全。

正常使用场景中,ArrayList 都是用来查询,不会涉及太频繁的增删,如果涉及频繁的增删,可以使用 LinkedList。如果需要线程安全就使用 Vector

VectorArrayList 的线程安全版本,实现方式就是在所有方法加上synchronized,性能较差。

如何扩容?

因为数组的大小是固定,当容量超出了现有数组的大小,就需要进行扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 每次扩大原有容量的一半
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果扩大一半后还是无法满足,则使用minCapacity
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果超过最大size,则获取最大容量的数组
    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);
}

为什么说ArrayList插入效率低?

原因有两点:

  1. 新增就要检测容量够不够,如果不够就需要扩容
  2. 尾部新增比较快,如果是在数组头部或者中部新增就会慢很多,因为要把后面的元素全部往后移一位
  3. 把元素往后移一位使用的是复制 System.arraycopy(),它是native方法(java定义了接口,其他语言进行实现),所以比较快
/**
 * 添加在尾部
 */
public boolean add(E e) {
    // 检查容量
    ensureCapacityInternal(size + 1);
    // 添加在尾部
    elementData[size++] = e;
    return true;
}

/**
 * 按指定位置添加
 */
public void add(int index, E element) {
    // 检查index
    rangeCheckForAdd(index);

    // 检查容量
    ensureCapacityInternal(size + 1);
    // index后面的元素全部往后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
    elementData[index] = element;
    size++;
}

删除元素效率如何?

效率和新增差不多,都是要移动元素,但是不需要检查容量和扩容。

public E remove(int index) {
    // 检查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;
}

适合做队列吗?

非常不适合。

队列是FIFO,在尾巴进,头部出,出的时候需要移动后面所有数据,效率很低。链表比较适合做队列。

new ArrayList<>(18) 会不会初始化数组大小?

不会初始化数组大小!!!

这是Java Bug。

而且将构造函数与initialCapcity结合使用,然后使用set()方法会抛出异常。

public static void main(String[] args) {
    ArrayList<Integer> a = new ArrayList<>(12);
    System.out.println(a.size());
    a.set(3, 3);
}
Java源码解读系列(一):ArrayList

总结

  1. 底层实现是数组 Object[] elementData
  2. 查找和访问元素的速度较快,但新增,删除的速度较慢
  3. 线程不安全
  4. 每次扩容原有数组大小的一半

相关推荐