您现在的位置是：首页 > Java

当前栏目

Java - 剖析ArrayList

JAVA 接口数组

2023-03-02 10:58:23 时间

# 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。

猜你喜欢

最长无重复子串
写技术博客的一些心得分享
Java 多线程（七）：线程池
Java 多线程（五）：锁（三）
Java 多线程（四）：锁（二）
Java 多线程（三）：锁（一）
Java 多线程（二）：并发编程的三大特性
线性时间非比较类排序
Java 多线程（一）：基础
合并k个已排序的链表
HDFS 高可用分布式环境搭建
合并两个有序数组
连续子数组的最大和
HDFS 分布式环境搭建
容器盛水问题
大数加法
HDFS 伪分布式环境搭建
设计LRU缓存结构
两数之和
使用单调栈来解决的一些问题

zl程序教程

当前栏目

Java - 剖析ArrayList

相关文章