JDK源码阅读—1.ArrayList

1.全局变量

// 存放数据的Object类型数组
transient Object[] elementData;

// 数组的默认容量
private static final int DEFAULT_CAPACITY = 10;

// 空数组 在使用其他构造方法使用此数组进行初始化
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空数组在使用默认构造方法时会初始elementData为此数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 所允许的数组最大容量，最大容量为Integer最大值减8的原因：
// 1.避免内存溢出，减少出错概率
// 2.因为部分虚拟机会在存储对象头信息，减少的8字节实际就是对象头信息所需要的内存
// 对象头包括两部分信息：Mark Word（标记字段）和 Klass Pointer（类型指针）。 该存储其实只会在部 
// 分虚拟机中才被使用。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

2.构造方法

1.默认构造方法

 public ArrayList() {
     // 集合在初始化时会直接将数组初始话为一个空数组，使用懒加载机制，在集合真正使用时才会计算容量
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

2.指定容量

/**
     * 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) {
            // 如果给定的初始容量大于0,会直接按照给定的容量初始化一个Object类型数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 如果给定容量等于0，则初始化一个空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 如果小于0，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

3.指定集合

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 在子子类重写父类方法的时候，在不修改返回值的前提下，子类返回了什么类型就是什么类型，
           // 不会向上转换为父类的返回值类型，所以这里得到的类型可能不为Object类型，
            // 比如一个Integer类型的ArrayList，在调用toArray方法时，返回值就是Integer类          
           // 型，而不是Object类型
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3.常用方法

1.add(E e) 添加元素

public boolean add(E e) {
        // 添加之前进行扩容操作，将当前数组元素个数+1，作为当前所需的最小容量
        // 扩容方法在下面
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将元素添加到数组尾部
        elementData[size++] = e;
        return true;
}

// 1.确认最小容量 ensureCapacityInternal(minCapacity)
private void ensureCapacityInternal(int minCapacity) {
        // 判断当前数组是否为默认构造方法构造出来空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 在默认容量10和minCapacity中找出一个最大值当作最小容量
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
}

// 2.真正扩容操作 ensureExplicitCapacity(minCapacity)
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        // 判断是否需要扩容，如果当前所需要的容量，已经大于数组的长度，则进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

// 3.扩容方法 grow(int minCapacity)
private void grow(int minCapacity) {
        // overflow-conscious code
        // 当前数组的长度
        int oldCapacity = elementData.length;
        // 将原始容量右移一位，也就是将原始容量除以2，然后再加上原始容量。将得出来的结果当作            // 新容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 判断新容量是否小于minCapacity，如果小于，则将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);
}

// 4.大容量扩容方法 hugeCapacity(minCapacity)
private static int hugeCapacity(int minCapacity) {
        // 判断所需容量是否小于0，如果小于0说明发生了内存溢出
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        // 判断所需容量是否大于所允许的最大值，如果大于则将Integer最大值作为数组长度
        // 如果小于或等于则将所允许的最大值作为数组最大长度
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
}

2.add(int index, E element) 在执行位置插入元素

 public void add(int index, E element) {
        // 检测要插入的下表是否超过数组长度
        rangeCheckForAdd(index);
        // 扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将原数组在index位置以后的元素全部复制到index+1的位置，这样index位置的元素
        // 就会空出来
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将新元素赋值到index的位置
        elementData[index] = element;
        size++;
 }

3.addAll(Collection<? extends E> c) 将集合内的元素全部添加到当前集合中

public boolean addAll(Collection<? extends E> 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;
}

4.addAll(int index, Collection<? extends E> c) 在指定位置插入新集合

public boolean addAll(int index, Collection<? extends E> c) {
        // 检测下标是否越界
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        // 扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        // 计算原数组中要往后移动的下标数量，例：
        // 假设原数组为Object[] a = {1,2,3,4,5},要添加的数组为Object[] b = {7,8};
        // 现在要在下标2的位置将b数组插入到a数组中，首先要将a中的3,4,5元素复制到a的后面
        // 复制后的数组为a = {1,2,3,4,3,4,5},复制的起始位置就是size - index,5-2 = 3,
        // 3就是元素复制过来的起始位置,然后在将b数组复制到a的2,3元素上面,最终结果就是
        // {1,2,7,8,3,4,5}
        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;
}

5.indexOf(Object o) 查找指定元素在集合中第一次出现的下标

 public int indexOf(Object o) {
        // 判断给定的元素是否为空,如果为空直接判断是否有元素为空
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            // 遍历集合,如果此下标位置的元素和给定元素相同则返回下标值，否则返回-1
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
 }

6.lastIndexOf(Object o) 从集合尾部开始查

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

7.get(int index) 返回指定下标的元素

 public E get(int index) {
        // 检测下标有无越界
        rangeCheck(index);
        // 返回集合中的此下标的元素
        return elementData(index);
 }

8.remove(int index) 移除指定下标的元素

 public E remove(int index) {
        // 检测下表有无越界
        rangeCheck(index);

        modCount++;
        // 取出此下标位置的元素用来返回
        E oldValue = elementData(index);
     
        // 计算需要复制的元素数量，例：
        // 假设数组为Object[] a = {1,2,3,4,5}, index为2,也就是说要移除元素3,
        // 那么元素3右边的元素全部都要往左移动一个下标,那么要复制的元素个数就是
        // 5-2-1 = 2,将元素4,5复制从index的位置开始复制，复制后的数组为a = {1,2,4,5,5}
        // 最后将末尾元素置空
        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;
 }

9.remove(Object o) 移除数组第一个和给定元素相同的元素

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    // 此方法实际是找出元素所在下标,fastRemove才是真正的删除方法
                    // 方法在下面
                    fastRemove(index);
                    return true;
                }
        }
        return false;
}

// fastRemove(int index)
    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed
     */
    private void fastRemove(int index) {
        // 下面方法实际和remove(inde index)内部一样
        modCount++;
        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
    }

10.clear() 清空元素方法

 public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
 }

11.removeAll(Collection<?> c) 移除包含在给定集合中的所有元素

 public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
 }

// 1.直接看batchRemove 批量删除
/**
 * complement 为false时代表删除与给定集合中相同的元素,
 * 为true时，代表保留与给定集合中相同的元素
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
        // 将集合中的数组赋值转换为局部变量操作，提高效率
        final Object[] elementData = this.elementData;
        // r为循环次数,w为elementData最终的元素数量
        int r = 0, w = 0;
        // 集合有没有进行删除操作
        boolean modified = false;
        try {
            for (; r < size; r++)
                // 循环判断找出原数组内和给定数组内相同的元素，
                if (c.contains(elementData[r]) == complement)
                    // 将不相等的元素放入到elementData中
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            // 只有当try中出现异常才会出现r!=size的情况，当出现异常时，将从r开始往后的元素
            // 全部复制到w起始的位置，这样就会将需要删除的元素给覆盖调，最后将集合中需要保留的            
           // 元素个数计算出来
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            // 判断数组内现有的元素数量是否和原数组的集合数量相同，如果相同，说明没有必要进行删除操作
            if (w != size) {
                // clear to let GC do its work
                // 循环以元素个数为循环起始值，将后面的元素全部清空，
                // 以为w代表数组内元素个数，大于w的下标也就是需要删除的元素
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
}

12.removeRange(int fromIndex, int toIndex) 移除给定下标范围内的元素

/**
 * 这是一个用protected修饰的方法，只能通过子类去调用 
 */
protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        // 计算要移动元素的个数
        // 假如size = 5，fromIndex = 1 toIndex = 3,那么需要toIndex后面的元素都要移动
        // 因为不包含toIndex本身的元素，所以需要移动的元素就是2个元素
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
}