Java集合-ArrayList源码解析

ArrayList 源码解析底层数据结构

// transient 表示不会被序列化
transient Object[] elementData; // non-private to simplify nested class access


private int size;

构造方法无参构造方法

    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    public ArrayList() {
        //采用默认大小的空间，其实也是0，那么添加元素也会触发扩容，所以最好指定大小就是这个原因
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

设置初始化容器大小

    
    private static final Object[] EMPTY_ELEMENTDATA = {};


    
    public ArrayList(int initialCapacity) {

        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //传入大小为0的时候，则使用默认定义的空数组，即和上面的无参构造差不多
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //参数不合法，抛异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

其它继承了List类的转化为ArrayList

    
    public ArrayList(Collection c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

自动扩容机制

添加元素方法

    
    public boolean add(E e) {
      	//初步确认扩容大小
        ensureCapacityInternal(size + 1);  // Increments modCount!!
      	//先赋值，再自增
        elementData[size++] = e;
        return true;
    }

初步确认扩容大小

如果为无参构造器，且第一次添加元素，那么扩容会使用默认大小，即minCapacity会被设置成DEFAULT_CAPACITY(10)
如果为有参构造器（构造器参数无论是否大于10），且第一次添加元素，这里也会同上面的情况一样，使用DEFAULT_CAPACITY(10)，但是下面的函数ensureExplicitCapacity()会判断是否需要扩容，最后的结果是不会扩容。（所以为什么阿里规范使用ArrayList的时候最好设置好大概所需的容量）

		
    
    private static final int DEFAULT_CAPACITY = 10;

		//初步校验是否需要扩容（这个的目的是为了防止多次触发后面多次扩容，直接就扩容到10，节约开支）
    private void ensureCapacityInternal(int minCapacity) {
      	// 存储数据的数组为空才为真
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          	//判断默认容量大小和最小所需比较，取最大值，(所以第一次扩容大小默认是默认值DEFAULT_CAPACITY=10，右侧的minCapacity为1)
            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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

		
    private void grow(int minCapacity) {
        // overflow-conscious code 旧数组长度
        int oldCapacity = elementData.length;
      
      	// 计算新扩容大小
      	// 1.5倍扩容来自于oldCapacity向右位移一位 即是： oldCapacity + (oldCapacity/2)，得到新的长度（扩容后的长度;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
      
      	// 判断计算的新扩容的大小是否合理
      	// 第一次扩容的时候，newCapacity是小于minCapacity的，所以还是用扩容前所需要的最小长度
        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);
    }

空间不够处理

		
    public void ensureCapacity(int minCapacity) {
      	//如果elementData不为空则返回0，否则返回DEFAULT_CAPACITY（10）
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
      
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

手动扩容

   
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

测试代码

import org.junit.Test;

import java.util.ArrayList;


public class ArrayListCode {
    
    @Test
    public void baseUseArrayList() {
        ArrayList arrayList = new ArrayList();
        for (int i = 0; i < 10; i++) {
            arrayList.add(i);
        }
        for (int i = 11; i < 15; i++) {
            arrayList.add(i);
        }
        arrayList.add(100);
        arrayList.add(null);

        //初始化大小
        ArrayList arrayList2 = new ArrayList(8);

        arrayList2.ensureCapacity(10);

        for (int i = 0; i < 8; i++) {
            arrayList2.add(i);
        }
        for (int i = 9; i < 15; i++) {
            arrayList2.add(i);
        }
        arrayList2.add(100);
        arrayList2.add(200);
        arrayList2.add(null);
    }
}

add(), addAll()

跟C++ 的vector不同，ArrayList没有push_back()方法，对应的方法是add(E e)，ArrayList也没有insert()方法，对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

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

    
    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++;
    }

add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。

addAll()方法能够一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的addAll(Collection c)方法，一个是从指定位置开始插入的addAll(int index, Collection c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。

    
    public boolean addAll(Collection c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

    
    public boolean addAll(int index, Collection c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

set()

既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

remove()

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。

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; //清除该位置的引用，让GC起作用
    return oldValue;
}

关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

trimToSize()

ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下:

    
    public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

indexOf(), lastIndexOf()

获取元素的第一次出现的index:

    public int indexOf(Object 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;
    }

获取元素的最后一次出现的index:

    
    public int lastIndexOf(Object 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;
    }

Fail-Fast机制:

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

Java集合-ArrayList源码解析

Java相关栏目本月热门文章