深入理解ArrayList

谁借莪１个温暖的怀抱￠ 2022-06-10 04:49 231阅读 0赞

# 说明 #

本文是基于JDK7对ArrayList进行总结。通过阅读源码，对ArrayList的实现原理，特点等进行理解和掌握。

# 正文 #

### ArrayList的特点 ###

ArrayList的实现是基于动态数组的，插入数据有序（读取顺序与存放时的顺序一致）且允许重复，允许有空值，但是非线程安全的，适合查找多增删少的场景。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList继承自AbstractList类，实现了List, RandomAccess, Cloneable, java.io.Serializable接口。

### ArrayList的成员变量 ###

private transient Object[] elementData;//从这里可以看出，底层是一个数组
     private int size;//ArrayList的大小，即所含元素的个数
     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//允许数组的最大size

### ArrayList的构造函数 ###

ArrayList一共有三个构造函数  
**指定容量**的构造函数

public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }

**缺省**构造函数

public ArrayList() {
            this(10);//ArrayList默认大小为10
        }

指定一个**集合作为参数**的构造函数

public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            size = elementData.length;
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        }

### ArrayList的add(E e)方法 ###

我们知道了ArrayList的底层是一个数组，当向其添加数据时，如果数组已满，它是怎样确保数据可以正常的添加？

public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }

我们可以看到进入方法时，首先调用了ensureCapacityInternal(size + 1)方法，后面注释可以看到，它是增加modCount的值

**ensureCapacityInternal(int minCapacity)方法**

private void ensureCapacityInternal(int minCapacity) {
            modCount++;
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }

通过本方法我们可以看到，当调用add方法时，modCount值加1，modCount值记录的时ArrayList结构改变的次数。若添加后的元素个数超过数组的长度，就会调用grow(minCapacity)方法

**grow(int minCapacity)方法**

private void grow(int minCapacity) {
            // overflow-conscious code
            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);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);//以新大小复制原数组的拷贝，并改原数组
        }

通过本方法我们就可以知道上述问题的解决办法，ArrayList有自动扩容机制，当底层数组容量满时，容量就会自动扩大为原来的1.5倍

### ArrayList的get(int index)方法 ###

public E get(int index) {
            rangeCheck(index);
    
            return elementData(index);
        }

当以索引查找数据时，先判断索引是否越界，是，抛出IndexOutOfBoundsException异常；否，则直接返回索引对应位置的值  
**rangeCheck(int index)方法**

private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

### ArrayList的remove(int index)方法 ###

remove方法删除数组的元素后，其之后的元素会发生移动，性能开销较大，

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; // Let gc do its work
    
            return oldValue;
        }

从本方法可以看出，数组元素的移动是通过复制完成的，从数组的index+1开始复制到原数组从index开始，将原来index之后的元素全部向前移一位。删除后，将数组最后一位置为null，让垃圾回收器进行回收

我们注意到除了remove(int index)方法，还有一个fastRemove(int index)，与remove（）方法不同的是，这个方法会跳过越界检查并且不会返回删除元素的值

private void fastRemove(int index) {
            modCount++;//没有检查是否越界
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // Let gc do its work
            //没有返回值
        }

那这个方法什么时候使用？ 通常在以元素自身为参数，删除数组中的此元素时使用

public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

### ArrayList的迭代 ###

ArrayList有两种迭代器 Iterator 和 ListIterator  
Iterator可以用于所有集合，Set,List和Map和这些集合的子类型，而ListIterator只能用于List及其子类型。

**两种迭代器的区别，详见**[http://blog.csdn.net/longshengguoji/article/details/41551491][http_blog.csdn.net_longshengguoji_article_details_41551491]

[http_blog.csdn.net_longshengguoji_article_details_41551491]: http://blog.csdn.net/longshengguoji/article/details/41551491