文章目录
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