Java容器框架分析(二)——ArrayList源码解析

2017/2/21 posted in  Java  

ArrayList简介

ArrayList实现了List接口,是顺序容器(即元素存放的顺序和加入列表的顺序相同),允许放入null元素,底层通过数组实现。该实现除了没有实现多线程同步之外,其余跟Vector大致相同,即ArrayList是线程不安全的。
每个ArrayList都一个容量(Capacity)属性,表示底层数组的实际大小,容器内存储元素的个数不大于当前的容量。当向容器中添加元素时,如果容量不足,容器会自动增大底层数组的大小。前面已经提过,Java 泛型只是编译器提供的语法糖,所以这里的数组是一个 Object 数组,以便能够容纳任何类型的对象。
size(), isEmpty(), get(), set() 方法均能在常数时间内完成,add() 方法的时间开销跟插入位置有关,addAll() 方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。
为追求效率,ArrayList 没有实现同步(synchronized),如果需要多个线程并发访问,用户可以手动同步,也可使用 Vector 替代。

常用方法剖析

set(int index, E element)

set()方法可以直接设定某个下标对应的元素。既然ArrayList的底层是数组实现的,set()方法的实现也就变得极为简单,直接赋值即可,复杂度为O(1)

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置,复制的仅仅是引用
    return oldValue;
}

get(int index)

get()方法可以获取指定下标对应的对象,唯一需要注意的是由于底层数组是Object[],得到元素后需要进行类型转换,复杂度为O(1)

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

add(E element)和add(int index,E element)

跟C++的vector不同,ArrayList没有push_back()方法,对应的方法是add(E e),ArrayList也没有insert()方法,对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素,这可能会导致 capacity 不足,因此在添加元素之前,都需要进行剩余空间检查,如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

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);//扩展空间并复制
}

由于Java GC自动管理了内存,这里也就不需要考虑源数组释放的问题。

空间的问题解决之后,插入就变得非常简单了。

add(int index,E e)需要先对元素进行移动,然后完成插入,该方法时间复杂度为O(n)

addAll()

addAll()方法可以一次添加多个元素,根据插入的起始位置不同也用两个版本:一个是在末尾添加addAll(Collection<? extends E> c);一个是从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法。对应的实现方式和上述的add方法类似,在插入之前,需要对容量进行判断,如果需要则自动扩容,如果从指定位置插入,还需要先对数组元素进行移动。

remove()

remove方法可以删除列表中的元素,其也有两个版本:一个是remove(int index)删除指定位置的元素;一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必选显示的为最后一个位置赋null值。

public E remove(int index) {
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除该位置的引用,让GC起作用
    return oldValue;
}

关于Java GC 这里需要特别说明一下,有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被 GC 的依据是是否还有引用指向它,上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。

使用技巧

关于List的容量,可以在一开始就给定一个比较合理的值,避免内存复制所带来的不必要的时间开销。

转载声明

本文转载自:https://github.com/CarpenterLee/JCFInternals
作者:CarpenterLee