转载

Java基础——ArrayList详解

ArrayList 内部是以动态数组的形式来存储数据的。这里的动态数组不是意味着去改变原有内部生成的数组的长度、而是保留原有数组的引用、将其指向新生成的数组对象、这样会造成数组的长度可变的假象。
ArrayList 具有数组所具有的特性、通过索引支持随机访问、所以通过随机访问ArrayList中的元素效率非常高、但是执行插入、删除时效率比较底下
ArrayList 实现了 Serializable 接口，因此它支持序列化，能够通过序列化传输，实现了 RandomAccess 接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了 Cloneable 接口，能被克隆。
ArrayList 不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用 Collections.synchronizedList(List l) 函数返回一个线程安全的 ArrayList 类，也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。

基础属性

ArrayList部分源码如下：

public class ArrayList<E> 
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable,java.io.Serializable{
        
    private static final int DEFAULT_CAPACITY = 10;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    private transient Object[] elementData;
    
    private int size;

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    protected transient int modCount = 0;
}
复制代码

DEFAULT_CAPACITY：默认初始容量
EMPTY_ELEMENTDATA：一个空数组，方便使用，主要用于带参构造函数初始化和读取序列化对象等
DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于默认大小的空实例的共享空数组实例
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 和EMPTY_ELEMENTDATA 的区别
- 仅仅是为了区别用户带参为0的构造和默认构造的惰性初始模式对象。
- 当用户带参为0的构造，第一次add时，数组容量grow到1。
- 当用户使用默认构造时，第一次add时，容量直接grow到DEFAULT_CAPACITY（10）。
elementData：当前数据对象存放地方，当前对象不参与序列化
size：当前数组中元素的个数
MAX_ARRAY_SIZE:数组最大可分配容量
modCount：集合数组修改次数的标识（由AbstractList继承下来）

构造方法

//方法一
public ArrayList(int initialCapacity)
//方法二
public ArrayList()
//方法三
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可指定
方法二：是默认的构造方法，它将创建一个空数组
方法三：接收一个 Collection 类的实例，将该 Collection 实例转换为 ArrayList 对象

add(E e)

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

向ArrayList集合添加元素，最重要的方法是扩容数组

//方法一
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//方法二
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
//方法三
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);
}
复制代码

方法一：在第一次向ArrayList添加元素时，设置容量扩容到多少
方法二：如果当前数组容量<需要的最小容量，则准备给数组扩容
方法三：扩容方法：
- 扩容原理：
- 获取当前数组容量
- 扩容后新数组容量 newCapacity 为旧数组的1.5倍
- 若值 newCapacity 比传入值 minCapacity 还要小，则使用传入 minCapacity ，若 newCapacity 比设定的最大数组容量大，则使用最大整数值
- 使用 Arrays.copyof(elementData, newCapacity) 进行扩容

于此，add方法走的流程就是：先扩容，再赋值，然后返回true

add(int index, E element)

public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,size - index);
    elementData[index] = element;
    size++;
}
复制代码

向指定位置添加元素：

rangeCheckForAdd

扩容方法总结

ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组。当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，这个操作代价很高，因此最好在创建ArrayList对象时就指定大概的容量大小，减少扩容操作的次数,或者使用LinkedList

ArrayList总结

ArrayList基于数组方式实现，无容量的限制（会扩容）
添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量可以使用trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
线程不安全
add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位
get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）
remove(Object o)需要遍历数组
remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高 contains(E)需要遍历数组

原文 https://juejin.im/post/5f1c4089f265da22d46717f4

正文到此结束