01_ArrayList核心源码剖析

一、基本原理

1. 数组的长度是固定的，java里面数组都是定长数组，如果不停的往ArrayList里面塞入这个数据，此时元素数量超过了初始大小，此时就会发生一个数组的扩容，就会搞一个更大的数组，把以前的数组拷贝到新的数组里面去
2. 缺点一、这个数组扩容+元素拷贝的过程，相对来说会慢一些. 所以，不要频繁的往arralist里面去塞数据，导致他频繁的数组扩容，避免扩容的时候较差的性能影响了系统的运行
3. 缺点二、数组来实现，数组你要是往数组的中间加一个元素，是不是要把数组中那个新增元素后面的元素全部往后面挪动一位，所以说，如果你是往ArrayList中间插入一个元素，性能比较差，会导致他后面的大量的元素挪动一个位置
4. 优点一、基于数组来实现，非常适合随机读，你可以随机的去读数组中的某个元素，list.get(10)，相当于是在获取第11个元素，这个随机读的性能是比较高的，随机读，list.get(2)，list.get(20)，随机读list里任何一个元素
5. 为什么基于数组的ArrayList随机读写会很快，而插入性能较低，因为数组是基于内存里连续的空间，只要根据Index+offset就可以计算出我们想访问的那个元素在内存中的地址

源码

代码片段一、

public static void main(String[] args) {
    List<String> list = new ArrayList<String>();
    // 代码片段二、
    list.add("zhangsan");
    list.add("lisi");
    list.add("wuwang");
    System.out.println(list.toString());
    System.out.println(list.toString());
    // 代码片段六、
    list.get(2);
    // 代码片段七、这里其实是向集合中的index为1的地方，插入一个新的元素
    list.add(1,"zhaoliu");
}

代码片段二、

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    // 这里是在计算当前元素应该放在list中的index索引，代码片段三、
    // 这里的size其实就是当前集合的大小，这里要和capacity区分开
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将当前元素放入到集合中，index=size++
    elementData[size++] = e;
    return true;
}

代码片段三、

private void ensureCapacityInternal(int minCapacity) {
    // 代码片段四、
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 通过代码片段四，第一次进来，minCapacity的值为10
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;


    // overflow-conscious code
    // 如果minCapacity大于集合现在的大小的话，就会走k扩容逻辑
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

代码片段四、

/**
* elementData:代表当前集合的底层数组
* minCapacity：当前数组的大小+1
* 所以第一次调用list的add()方法的时候，elementData是空的，minCapacity为1
* 返回DEFAULT_CAPACITY，集合的初始化大小 10
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

代码片段五、

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    // 集合现在的大小
    int oldCapacity = elementData.length;
    // 扩容逻辑就是：oldCapacity(老的大小) + oldCapacity/ 2
    // 比如原来大小10，现在扩容，就是10 + 10/2 = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的仓位15大于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);
}

代码片段六、

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    // 如下面代码，如果index超过了size，就会报出来一个数组越界异常
    rangeCheck(index);

    // 返回index下的元素，所以，集合的读是很快的
    return elementData(index);
}

/**
 * Checks if the given index is in range.  If not, throws an appropriate
 * runtime exception.  This method does *not* check if the index is
 * negative: It is always used immediately prior to an array access,
 * which throws an ArrayIndexOutOfBoundsException if index is negative.
 */
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

代码片段七、

/**
* 在指定位置插入一个新的元素，然后指定位置以后的元素进行重新排序
 * Inserts the specified element at the specified position in this
 * list. Shifts the element currently at that position (if any) and
 * any subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
     // 检查index是否越界，越界则抛出角标越界异常
    rangeCheckForAdd(index);

    // 代码片段四中的检查是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 这里的数组拷贝，然后index后面的元素向后移动
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    // 将新的元素放入到指定index中
    elementData[index] = element;
    size++;
}

/**
 * A version of rangeCheck used by add and addAll.
 */
private void rangeCheckForAdd(int index) {
    // 检查index是否越界
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

三、总结

1. 其实对于大部分Java的程序员来说，ArrayList的基本原理都没啥问题，但是我们为什么还要继续分析ArrayList的源码呢，主要是，随着我们工作年限的增加，在去面试的话，基本上都是往死里问，所以对于基础的集合，我们还是很有必要来分析一下他的源码
2. 我们仅仅是研究一下核心源码，如果对ArrzyList中1500行左右的源码全部剖析的话，首先我们肯定记不住这么多，其次还可能忽略核心功能，如果对于核心功能已经了解的话，其他的API其实都不难的