ArrayList底层原理与源码分析

ArrayList

一句话概括：ArrayList就是一个动态数组，底层用Object数组来承载数据，支持自动扩缩容，随机访问速度快，但是增删速度慢，因为增删的过程中需要把操作节点后的数据整体进行挪动

1. 继承关系

类定义

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

继承关系图
在这里插入图片描述

2. 成员属性

/**
 * ArrayList默认的容量为10个Object元素
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * 空数组
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 也是个空数组
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 真正承载数据的地方，用transient修饰是为了防止它被序列化
 * 因为ArrayList重写了readObject和writeObject方法，
 * 这两个方法会从elementData取数据和写入数据，所以没必要再把elementData序列一次
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList中包含的元素数量
 */
private int size;

3. 构造函数

无参构造

public ArrayList() {
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是上面的空数组
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

有参构造

public ArrayList(Collection<? extends E> c) {
    //把传入的集合转为数组
    Object[] a = c.toArray();
    if ((size = a.length) != 0) {
        if (c.getClass() == ArrayList.class) {
            //如果传入的c是一个ArrayList。直接把它赋给elementData
            elementData = a;
        } else {
            //创建一个新Object数组，并把传入的集合中的数据复制到新数组
            elementData = Arrays.copyOf(a, size, Object[].class);
        }
    } else {
        // replace with empty array.
        elementData = EMPTY_ELEMENTDATA;
    }
}

4. add方法

/**
 * 新增元素操作
*/
public boolean add(E e) {
    /** 确定是否需要扩容，如果需要，则进行扩容操作*/
    ensureCapacityInternal(size + 1);  // Increments modCount!!

   //放进数组后a自增为1
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal方法

//计算容量是否满足minCapacity
private void ensureCapacityInternal(int minCapacity) {
    // eg1：第一次新增元素，calculateCapacity方法返回值为DEFAULT_CAPACITY=10
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity方法

/**
 * 计算ArrayList的容量
 * 如果elementData数组中没有已存储的元素，则返回默认值10
 * 否则，返回minCapacity。
 * @param elementData 底层存储ArrayList元素的数组
 * @param minCapacity ArrayList中的元素个数
 * @return
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //第一次新增元素，elementData={} minCapacity=1
	if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
		// 取需要的最小容量和默认容量的最大值
		return Math.max(DEFAULT_CAPACITY, minCapacity);
	}
	return minCapacity;
}

ensureExplicitCapacity方法

/**
 * 确保明确的ArrayList的容量
 * @param minCapacity ArrayList所需的最小容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    //修改次数加1
	modCount++;
	/** 如果所需的最小容量大于elementData数组的容量，则进行扩容操作 */
	if (minCapacity - elementData.length > 0) {
		grow(minCapacity);
	}
}

5. add方法指定索引

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

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //会先把指定索引上的元素后移一位，从index开始整体后移一位
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

5. grow方法

面试点：int newCapacity = oldCapacity + (oldCapacity >> 1) 右移一位就相当于除以2，也就是新长度等于旧长度加上旧长度的一半

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * 扩容操作
 *
 * @param minCapacity 所需要的最小扩容量
 */
// eg1：第一次新增元素，minCapacity=10，即：需要将elementData的0长度扩容为10长度。
private void grow(int minCapacity) {

	/** 原有数组elementData的长度*/
	int oldCapacity = elementData.length; // eg1：oldCapacity=0

	/**
	 * A >> 1 等于 A/2
	 * eg: 3 >> 1 = 3/2 = 1
	 *     4 >> 1 = 4/2 = 2
	 * ------------------------
	 * A << 1 等于 A*2
	 * eg: 3 << 1 = 3*2 = 6
	 *     4 << 1 = 4*2 = 8
	 *
	 * 000100 >> 1 = 000010
	 * 000100 << 1 = 001000
	 */
	/** 新增oldCapacity的一半整数长度作为newCapacity的额外增长长度 */
    //右移一位就相当于除以2
	int newCapacity = oldCapacity + (oldCapacity >> 1); // eg1：newCapacity=0+(0>>1)=0

	/** 新的长度newCapacity依然无法满足需要的最小扩容量minCapacity，则新的扩容长度为minCapacity */
	if (newCapacity - minCapacity < 0) {
		// eg1：newCapacity=10
		newCapacity = minCapacity;
	}

	/** 新的扩容长度newCapacity超出了最大的数组长度MAX_ARRAY_SIZE */
	if (newCapacity - MAX_ARRAY_SIZE > 0) {
        //返回
		newCapacity = hugeCapacity(minCapacity);
	}

	/** 扩展数组长度为newCapacity，并且将旧数组中的元素赋值到新的数组中 */
	// eg1：newCapacity=10， 扩容elementData的length=10
    //Arrays.copyOf会创建并返回一个新数组
	elementData = Arrays.copyOf(elementData, newCapacity);
}

hugeCapacity方法

/**
 *
 * 要分配的数组的最大大小。一些vm在数组中保留一些头字。
 * 尝试分配较大的数组可能会导致OutOfMemory错误：请求的数组大小超过了虚拟机限制
 */
// MAX_ARRAY_SIZE=2147483639=01111111 11111111 11111111 11110111
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static int hugeCapacity(int minCapacity) {
	if (minCapacity < 0) { // overflow 说明超出了Integer的范围，发生溢出了
		throw new OutOfMemoryError();
	}
    //如果容量超过Integer.MAX_VALUE - 8，就直接把长度变成Integer.MAX_VALUE
	return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

6. get方法

public E get(int index) {
    //检查索引是否超出最大长度
    rangeCheck(index);
    //直接取出数组中索引对应位置的值
    return elementData(index);
}

7. remove方法

重点关注：

获得需要移动元素的个数计算：int numMoved = size - index - 1;

通知jvm将之前的最后一位元素进行垃圾回收

从需要删除的index后一位开始到末尾的这部分数据，整体都向前移动一个元素

System.arraycopy(elementData, index + 1, elementData, index, numMoved);

/**
* 删除元素
*/
// eg1：elementData中保存了{"a1","a2","a3","a4"}，删除第一个元素，即：index=0
public E remove(int index) {
   /** 校验传入的参数index是否超出了数组的最大下标，如果超出，则抛出：IndexOutOfBoundsException异常*/
   rangeCheck(index);

   /** 集合的修改次数加1 */
   modCount++;

   // eg1：String oldValue="a1"
   /** 获得index下标对应的旧值oldValue */
   E oldValue = elementData(index);

   // eg1：numMoved=4-0-1=3
   /** 获得需要移动元素的个数 */
   int numMoved = size - index - 1;
   if (numMoved > 0) {
   	/** 从需要删除的index后一位开始到末尾的这部分数据，整体都向前移动一个元素。*/
   	System.arraycopy(elementData, index + 1, elementData, index, numMoved);
   }
   /** 通知jvm将之前的最后一位元素进行垃圾回收 */
   elementData[--size] = null; // clear to let GC do its work

   /** 返回已被删除的元素 */
   return oldValue;
}

8. 面试点

ArrayList与LinkedList的区别？

ArrayList的随机访问查找速度快，但增删速度较慢，LinkedList查找需要从头到尾或者从尾到头遍历查找，速度较慢，但是他的新增，删除的速度较快
ArrayList需要一份连续的内存空间，LinkedList不需要连续的内存空间（特别地，当创建一个ArrayList集合的时候，连续的内存空间必须要大于等于创建的容量）
两者都是线程不安全的

ArrayList怎么实现自动扩容的

每次添加元素之前都先判断下ArrayList的成员变量size+1之后有没有超过elementData数组长度，如果超过了，就会触发扩容，新长度等于旧长度加上旧长度的一半，通过右移实现：int newCapacity = oldCapacity + (oldCapacity >> 1)然后通过Arrays.copyOf把数组中的元素复制到新数组中elementData = Arrays.copyOf(elementData, newCapacity);

ArrayList与Vector区别

Vector类的所有方法都是同步的，线程安全的，ArrayList是线程不安全的

9. System.arraycopy()和Arrays.copyOf()

9.1 System.arraycopy()

是本地方法，作用是把源数组从指定开始位置，复制到指定开始位置的目标数组

 public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

src - 源数组。

srcPos - 源数组中的起始位置。

dest - 目标数组。

destPos - 目标数据中的起始位置。

length - 要复制的数组元素的数量

9.2 Arrays.copyOf()

copyOf()内部调用了System.arraycopy()方法，会创建一个新数组，把旧数组的数据复制到新数组返回

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

该方法对应不同的数据类型都有各自的重载方法

original - 要复制的数组

newLength - 要返回的新数组的长度

newType - 要返回的数组的类型

9.3 区别：

System.arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
Arrays.copyOf()是系统自动在内部新建一个数组，调用arraycopy()将original内容复制到copy中去，并且长度为newLength。返回copy; 即将原数组拷贝到一个长度为newLength的新数组中，并返回该数组
Array.copyOf()可以看作是受限的System.arraycopy(),它主要是用来将原数组全部拷贝到一个新长度的数组，适用于数组扩容

公司注册

公司变更

其他服务

代理记账

税务申报

财务咨询

社保开户

社保托管

商标注册

商标其他服务

食品流通许可证

进出口许可证