Java - 剖析ArrayList

蔚落 2022-05-25 03:59 190阅读 0赞

# Java - 剖析ArrayList #

--------------------

# 一、基本用法 #

ArrayList 是一个泛型容器，在新建 ArrayList 的时候需要实例化泛型参数，如下：

ArrayList<Integer> intList = new ArrayList<Integer>();
    ArrayList<String> strList = new ArrayList<String>();

在 ArrayList 中常用的方法如下：

public boolean add(E e) // 添加元素到末尾
    public boolean isEmpty() //判断是否为空
    public int size() //获取元素个数
    public E get(int index) //访问指定位置的元素
    public int indexOf(Object o) // 查找指定元素，如果找到返回索引位置，否则返回-1
    public int lastIndexOf(Object o) // 从后往前找
    public boolean contains(Object o) // 是否判断指定元素，判断依据是调用 equals 方法
    public E remove(int index) // 删除指定位置的元素，返回值为删除的元素
    //删除指定对象，只删除第一个相同的对象，返回值为被删对象
    //如果o为null，则删除值为null的元素
    public boolean remove(Object o)
    public void clear() // 清空所有元素
    // 在指定位置插入元素， index 为0表示插入到最前面，index为ArrayList的长度则表示插入到最后面
    public void add(int index, E element)
    public E set(int index, E element) // 修改指定位置的元素内容

# 二、基本原理 #

ArrayList内部有一个数组 elementData， 在一般情况下会有一些预留口那件，同时又一个整数 size 记录实际的元素个数。

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */
    transient Object[] elementData; // non-private to simplify nested class access
    /** * The size of the ArrayList (the number of elements it contains). * * @serial */
    private int size;

该类的方法内部操作的基本都是这个数组和这个整数， 其中 elementData 会跟着实际元素的个数增多而重新分配，而size使用记录实际的元素个数。

接下来查看 `add` 方法的实现，其代码为：

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

首先调用`ensureCapacityInternal`方法来确保数组容量是足够的，其实现为：

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

首先调用`calculateCapacity`用于返回现在需要的最小容量，接下来进入`ensureExplicitCapacity`方法判断现有容量是否足够，如果不够则调用 `grow` 方法，对数组进行扩容，其实现为：

/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }
    
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

从`oldCapacity >> 1`可以看出是对原有数组容量除以2，因此每一次扩容都是原有容量的 1.5 倍。如果发现扩展1.5倍之后还是不够， 则直接扩容为`minCapacity`，与此同时还会对扩容的数量进行边界判断，在合法之后对数据元素进行拷贝，其中`MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8`。

接下来我们查看`remove`方法的实现

/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (subtracts one from their * indices). * * @param index the index of the element to be removed * @return the element that was removed from the list * @throws IndexOutOfBoundsException {@inheritDoc} */
    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; // clear to let GC do its work
    
        return oldValue;
    }

首先对边界进行检查，获取元素。然后计算需要移动的元素的个数，从index之后的元素均需要移动，之后调用`System.arraycopy`方法进行元素的移动。 在元素移动完成之后，使用`elementData[--size] = null`，将 size - 1的同时将最后一个元素设置为 null，使得不再引用原有对象，这样就便于垃圾回收。

# 三、ArrayList实现的接口 #

ArrayList实现了三个主要的接口：

*  Collection
 *  List
 *  RandomAccess

## 3.1 Collection ##

Collection表示一个数据集合，数据间没有位置或顺序的概念，接口定义为：

public interface Collection<E> extends Iterable<E> { 
        int size();
        boolean isEmpty();
        boolean contains(Object o);
        Iterator<E> iterator();
        Object[] toArray();
        <T> T[] toArray(T[] a);
        boolean add(E e);
        boolean remove(Object o);
        boolean containsAll(Collection<?> c);
        boolean addAll(Collection<? extends E> c);
        boolean removeAll(Collection<?> c);
        boolean retainAll(Collection<?> c);
        void clear();
        boolean equals(Object o);
        int hashCode();
    }

Java 8对Collection接口添加了几个默认方法，包括removeIf、stream、spliterator等，具体可参见API文档。

## 3.2 List ##

List表示有顺序或位置的数据集合，它扩展了Collection，增加的主要方法有（Java 7）：

boolean addAll(int index, Collection<? extends E> c);
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    int indexOf(Object o);
    int lastIndexOf(Object o);
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    List<E> subList(int fromIndex, int toIndex);

## 3.3 RandomAccess ##

RandomAccess的定义为：

public interface RandomAccess {
    }

这种没有任何代码的接口在Java中被称为标记接口，用于声明类的一种属性。

实现了RandomAccess接口的类表示可以随机访问，可随机访问就是具备类似数组那样的特性，数据在内存是连续存放的，根据索引值就可以直接定位到具体的元素，访问效率很高。

比如，Collections类中有一个方法binarySearch，在List中进行二分查找，它的实现代码就根据list是否实现了RandomAccess而采用不同的实现机制，如下所示：

public static <T>
    int binarySearch(List<? extends Comparable<? super T>> list, T key) {
        if(list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
            return Collections.indexedBinarySearch(list, key);
        else
            return Collections.iteratorBinarySearch(list, key);
    }

# 四、总结 #

ArrayList，它的特点是内部采用动态数组实现，有以下的特点：

1.  可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O（1）
2.  除非数组已排序，否则按照内容查找元素效率比较低，具体是O（N），N为数组内容长度，也就是说，性能与数组长度成正比。
3.  加元素的效率还可以，重新分配和复制数组的开销被平摊了，具体来说，添加N个元素的效率为O（N）。
4.  插入和删除元素的效率比较低，因为需要移动元素，具体为O（N）。

需要说明的是，ArrayList不是线程安全的。此外，需要了解的是，还有一个类Vector，它是Java最早实现的容器类之一，也实现了List接口，基本原理与ArrayList类似，内部使用synchronized实现了线程安全，不需要线程安全的情况下，推荐使用ArrayList。