文章目录

• • ArrayList源码分析
  • • 1、底层原理
    • 2、构造方法
    • 3、增 - - add方法
    • 4、删 - - remove方法
    • 5、查 - - get 方法
    • 6、改 - - set方法
    • 7、clone方法
    • 8、扩容
    • 总结

ArrayList源码分析

1、底层原理

底层：基于数组

实现List接口实现增删查改操作，实现RandomAccess随机访问接口，实现Cloneable接口重写clone方法，实现序列化接口：可转化为字节流存储（序列化），也可反序列化。

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

/**
* 默认数组长度
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 空数组（带参构造时，传入参数`initialCapacity` == 0
* 将该空数组赋值给elementData，即此时elementData数组为空）
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空数组（无参构造时赋值给elementData，即数组默认为空）
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* arraylist基于该数组进行增删等操作
*/
transient Object[] elementData; 

/**
* 数组元素的个数
*/
private int size;

2、构造方法

1、无参构造方法

public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//将数组赋值为空
   //第一次添加数据时会将数组长度设置为默认长度10
}

2、带参构造方法 – 传入数组长度

public ArrayList(int initialCapacity) {
   if (initialCapacity > 0) {
       this.elementData = new Object[initialCapacity];//创建一个数组
   } else if (initialCapacity == 0) {
       this.elementData = EMPTY_ELEMENTDATA;//将数组赋值为空
   } else {//传入参数不合法
       throw new IllegalArgumentException("Illegal Capacity: "+
                                          initialCapacity);
   }
}

3、带参构造方法 – 传入一组数据

public ArrayList(Collection<? extends E> c) {
   elementData = c.toArray();//转为数组并赋值
   if ((size = elementData.length) != 0) {
       // 返回的不是Object类型数组时
       if (elementData.getClass() != Object[].class)
           elementData = Arrays.copyOf(elementData, size, Object[].class);//拷贝
   } else {//无数据
       this.elementData = EMPTY_ELEMENTDATA;//将数组赋值为空
   }
}

3、增 - - add方法

• 直接添加数据

public boolean add(E e) {
   ensureCapacityInternal(size + 1);//判断是否需要扩容  
   elementData[size++] = e;//添加数据
   return true;
}
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);//返回默认长度10
    }
   return minCapacity;//数组不为空，说明不是第一次添加数据
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)//说明当前数组已满，无法再添加数据，需要扩容
         grow(minCapacity);
}

• 将数据插入指定位置

public void add(int index, E element) {
   rangeCheckForAdd(index);//判断index是否合法

   ensureCapacityInternal(size + 1);  // 判断是否需要扩容
   System.arraycopy(elementData, index, elementData, index + 1,
                    size - index);//从指定位置开始的其他数据向后移一位
   elementData[index] = element;//添加在指定位置
   size++;
}

private void rangeCheckForAdd(int index) {
   if (index > size || index < 0)
       throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4、删 - - remove方法

删除指定位置的数据

public E remove(int index) {
   rangeCheck(index);//检查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; // 说明删除的是最后一个元素 直接置为null gc清除即可

   return oldValue;//返回旧值
}

5、查 - - get 方法

public E get(int index) {
   rangeCheck(index);//检查合法性

   return elementData(index);//直接返回
}

• indexOf 方法

从以下代码可知，arraylist支持查询null

public int indexOf(Object o) {//o第一次出现的位置
   if (o == null) {
       for (int i = 0; i < size; i++)
           if (elementData[i]==null)
               return i;
   } else {
       for (int i = 0; i < size; i++)
           if (o.equals(elementData[i]))
               return i;
   }
   return -1;
}

public int lastIndexOf(Object o) {//o最后一次出现的位置
   if (o == null) {
       for (int i = size-1; i >= 0; i--)
           if (elementData[i]==null)
               return i;
   } else {
       for (int i = size-1; i >= 0; i--)
           if (o.equals(elementData[i]))
               return i;
   }
   return -1;
}

6、改 - - set方法

修改指定位置的值

public E set(int index, E element) {
   rangeCheck(index);//检查index的合法性

   E oldValue = elementData(index);
   elementData[index] = element;
   return oldValue;//返回旧值
}

7、clone方法

ArrayList实现cloneable接口重写clone方法，即直接克隆一个拥有一模一样的数据（地址不同

public Object clone() {
   try {
       ArrayList<?> v = (ArrayList<?>) super.clone();
       v.elementData = Arrays.copyOf(elementData, size);
       v.modCount = 0;
       return v;
   } catch (CloneNotSupportedException e) {
       throw new InternalError(e);
   }
}

8、扩容

一般来说，会扩容为原数组的1.5倍

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//数组最大长度

private void grow(int minCapacity) {
   int oldCapacity = elementData.length;
   int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为原来的1.5倍
   if (newCapacity - minCapacity < 0)
       //若minCapacity为2，数组长度为1，扩容后 ，新数组长度还是1，比minCapacity小
       newCapacity = minCapacity;
   if (newCapacity - MAX_ARRAY_SIZE > 0)//新数组长度大于最大长度
       newCapacity = hugeCapacity(minCapacity);//赋值为Integer.MAX_VALUE
   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;
   }

总结

ArrayList适用于查询更改操作，增删操作会相对麻烦，可能需要移动元素，效率为O(n)。

线程不安全，与hashmap相似使用modCount来记录有数据更改的操作，来判断是否并发操作，导致前后数据不同，抛出ConcurrentModificationException并发更改异常。

private void checkForComodification() {
    if (this.modCount != l.modCount)
        throw new ConcurrentModificationException();
}

若需保证线程安全，改用CopyOnWriteArrayList