Java集合 ArrayList原理-白红宇

Java集合 ArrayList原理

阅读量：3966 次

发布时间：2019-05-24

本文共 4853 字，大约阅读时间需要 16 分钟。

Java集合 ArrayList原理

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。

ArrayList 继承了 AbstractList ，并实现了 List 接口。

一、ArrayList 的定义

定义一个ArrayList 数组

//List
   
     objectName = new ArrayList<>();List
    
      list = new ArrayList<>();

E: 泛型数据类型，用于设置 objectName 的数据类型，只能为引用数据类型。objectName 是数组名。
这里定义一个String类型的ArrayList数组示例。

在定义的时候我们会调用ArrayList的构造方法,下面是ArrayList类构造函数的源码

public class ArrayList
   
     extends AbstractList
    
             implements List
     
      , RandomAccess, Cloneable, java.io.Serializable{
       private static final long serialVersionUID = 8683452581122892189L;    /**     * Default initial capacity.     */    private static final int DEFAULT_CAPACITY = 10;    /**     * Shared empty array instance used for empty instances.     */    private static final Object[] EMPTY_ELEMENTDATA = {
   };    /**     * Shared empty array instance used for default sized empty instances. We     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when     * first element is added.     */    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
   };    /**     * The array buffer into which the elements of the ArrayList are stored.     * The capacity of the ArrayList is the length of this array buffer. Any     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA     * will be expanded to DEFAULT_CAPACITY when the first element is added.     */    transient Object[] elementData; // non-private to simplify nested class access    /**     * The size of the ArrayList (the number of elements it contains).     *     * @serial     */    private int size;    /**     * Constructs an empty list with the specified initial capacity.     *     * @param  initialCapacity  the initial capacity of the list     * @throws IllegalArgumentException if the specified initial capacity     *         is negative     */    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);        }    }    /**     * Constructs an empty list with an initial capacity of ten.     */    public ArrayList() {
           this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }

可以看到ArrayList的底层是一个Object[]，添加到ArrayList中的数据保存在了elementData属性中。

调用空的构造函数

List
   
     list = new ArrayList<>();

将一个空数组赋值给了elementData ，这时数组的长度size为0

调用其他构造函数

List
   
     list = new ArrayList<>(10);

根据传入的长度，将一个长度为10的Object数组赋值给elementData

二、ArrayList 的使用

1.添加 add(E element)

源码

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

首先通过 ensureCapacityInternal(size + 1) 来保证底层Object[]数组有足够的空间存放添加的数据，然后将添加的数据存放到数组对应的位置上.

private void ensureCapacityInternal(int minCapacity) {
       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
           minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);    }    ensureExplicitCapacity(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);}

首先确定了Object[]足够存放添加数据的最小容量,然后通过grow方法进行扩容。
扩容规则为“数组当前足够的最小容量 + （数组当前足够的最小容量 / 2）”，即数组当前足够的最小容量 * 1.5

2.设置值 set(int index, E element)

源码

public E set(int index, E element) {
       rangeCheck(index);    E oldValue = elementData(index);    elementData[index] = element;    return oldValue;}

通过传入的数字下标找到对应的位置，替换其中的元素，前提也需要首先判断传入的数组下标是否越界。

3.获取值 get(int index)

源码

public E get(int index) {
       rangeCheck(index);    return elementData(index);}E elementData(int index) {
       return (E) elementData[index];}

通过下标查找，同时需要进行了类型转换，因为数组为Object[]，前提是需要判断传入的数组下标是否越界。

4.删除 remove(int index)

源码

public E remove(int index) {
       rangeCheck(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; // clear to let GC do its work    return oldValue;}