ArrayList动态数组，是怎么实现动态的？-五八三

简介

ArrayList是一个动态数组，可以通过泛型来决定数据中存放的元素类型

怎么实现的动态

之所以是动态数组，是因为在使用无参构造函数创建ArrayList之后，默认为空数组

public ArrayList() {  
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;  
}

在你每次去add一个元素的时候，通过ensureCapacityInternal方法去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求

public boolean add(E e) {
	// size为当前数据存放元素的数量
    ensureCapacityInternal(size + 1);
    // elementData为ArrayList内部存放数据的数组
    elementData[size++] = e;  
    return true;
}

private void ensureCapacityInternal(int minCapacity) { 
	// 判断数组是否为空，为空则将最小容量设置为默认值10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {  
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  
    }  
	// 判断当前容量是否满足最小容量
    ensureExplicitCapacity(minCapacity);  
}

private void ensureExplicitCapacity(int minCapacity) {
	// modCount用于记录修改次数，作用于fast-fail机制
	// 如果在迭代的时候发现modCount被修改了，则会抛出异常来避免可能会出现的不确定行为
    modCount++;  
  
    // 如果当前容量小于最小容量，则进行扩容
    if (minCapacity - elementData.length > 0)  
        grow(minCapacity);  
}

private void grow(int minCapacity) {  
    int oldCapacity = elementData.length;  
    // 计算新的容量，扩大为原容量的1.5倍, oldCapacity >> 1 运算表示右移一位，也就是相当于除以二并取整
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)  
        newCapacity = minCapacity; 
    // 如果新容量超过了数组的最大容量,调用hugeCapacity方法来获取一个更大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)  
        newCapacity = hugeCapacity(minCapacity);  
    // 拷贝原数组，将原数组的元素复制到新数组中 
    elementData = Arrays.copyOf(elementData, newCapacity);  
}

private static int hugeCapacity(int minCapacity) {  
    if (minCapacity < 0) 
        throw new OutOfMemoryError();
	// 如果最小容量大于最大容量，则将容量设置为Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?  
        Integer.MAX_VALUE :  
        MAX_ARRAY_SIZE;  
}

从上面的源码解释可以看到，如果新建数据没有给定初始值，ArrayList是每次在进行add操作的时候去进行扩容的，扩容则会涉及到Arrays.copyOf深拷贝，会造成内存和性能的消耗，所以在生产项目中，推荐大家尽量在创建ArrayList对象的时候就指定其容量。

Fast-Fail机制

大家肯定注意到了上面提到的通过modCount实现的Fast-Fail机制

Fast-Fail是一种机制，用于检测在迭代过程中是否有其他线程对集合进行了修改。当一个线程在迭代 ArrayList 时，如果其他线程对 ArrayList 进行了结构性修改（如添加、删除元素），那么迭代器会立即抛出 ConcurrentModificationException 异常，以避免出现不确定的行为。
例子：

public class Example1 {  
    public static void main(String[] args) {  
        ArrayList<String> list = new ArrayList<>(3);  
        list.add("qwe");  
        list.add("asd");  
        list.add("zxc");  
  
        Iterator<String> iterator = list.iterator();  
        while (iterator.hasNext()){  
            String next = iterator.next();  
            System.out.println(next);  
            list.remove(next);  
        }  
    }  
}

输出：
qwe
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at com.example.lepractice.collection.Example1.main(Example1.java:21)