ArrayList源码

get

/**
     * 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) {
    //检查下标是否越界,如果越界则抛出java.lang.IndexOutOfBoundsException: Index: 10, Size: 2
    //但并不会检查下标是否为负数，如果为负数，则会在数组取值时抛出异常java.lang.ArrayIndexOutOfBoundsException: -1
    rangeCheck(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));
    }

// Positional Access Operations

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        //泛型会在运行时被擦除，但get方法取出的仍可以自动转换为泛型类型
        return (E) elementData[index];
    }

泛型会在运行时被擦除，但get方法取出的仍可以自动转换为泛型类型

public class Test {
public static void main(String[] args) {
	ArrayList<Date> list=new ArrayList<Date>();
	list.add(new Date());
	Date myDate=list.get(0);
}
    
//字节码
public static void main(java.lang.String[]);
Code:
0: new #16 // class java/util/ArrayList
3: dup
4: invokespecial #18 // Method java/util/ArrayList."<init
:()V
7: astore_1
8: aload_1
9: new #19 // class java/util/Date
12: dup
13: invokespecial #21 // Method java/util/Date."<init>":()
 
16: invokevirtual #22 // Method java/util/ArrayList.add:(L
va/lang/Object;)Z
19: pop
20: aload_1
21: iconst_0
22: invokevirtual #26 // Method java/util/ArrayList.get:(I
java/lang/Object;
25: checkcast #19 // class java/util/Date
28: astore_2
29: return

看第22 ，它调用的是ArrayList.get()方法，方法返回值是Object，说明类型擦除了。然后第25，它做了一个checkcast操作，即检查类型#19， 在在上面找#19引用的类型，他是
9: new #19 // class java/util/Date
是一个Date类型，即做Date类型的强转。
所以不是在get方法里强转的，是在你调用的地方强转的。

List<Integer> list = new ArrayList<>();
list.add(101);
//通过反射调用方法，在运行时泛型被擦除，绕开编译时的泛型检查
list.getClass().getMethod("add", Object.class).invoke(list,"test");
for (int i = 0; i < list.size(); i++) {
    //说明返回回来的数据是Object类型，强制类型转换是在调用的地方强转的
    System.out.println(list.get(i));	//OK
}

附关于checkcast的解释：

checkcast checks that the top item on the operand stack (a reference to an object or array) can be cast to a given type. For example, if you write in Java:

return ((String)obj);

then the Java compiler will generate something like:

aload_1 ; push -obj- onto the stack
checkcast java/lang/String ; check its a String
areturn ; return it

checkcast is actually a shortand for writing Java code like:

if (! (obj == null || obj instanceof )) {
throw new ClassCastException();
}
// if this point is reached, then object is either null, or an instance of
// or one of its superclasses.

add(E e)

/**
     * 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) {
        //判断添加需要最小容量size+1是否足够
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }


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

扩容

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 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;
        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);
    }

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

总结：

1. 对空间进行检查，确定最少需要的容量
2. 确定是否需要扩容，如果需要则调用grow(int minCapacity)方法
3. 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半
4. 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity
5. 对扩容后的容量进行判断，如果大于允许的最大容量MAX_ARRAY_SIZE，则将容量再次调整为MAX_ARRAY_SIZE。至此扩容操作结束
6. 执行elementData = Arrays.copyOf(elementData, newCapacity);

add( int index, E element)

时间复杂度为O(n)

    /**
     * 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) {
        //下标越界检查
        rangeCheckForAdd(index);

        //确保容量，和add(E e)相同
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将下标index以及index右边的元素往右移一位
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        //将指定的index位置赋值为element
        elementData[index] = element;
        //实际容量+1
        size++;
    }

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

总结：

1. 越界检查
2. 空间检查，如果有需要进行扩容
3. 将下标index以及index右边的元素往右移一位
4. 插入元素

remove(int index)

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {	
        //检查下标是否越界
        rangeCheck(index);

        //结构性修改次数+1
        modCount++;
        E oldValue = elementData(index);

        //需要移动元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //size减一，然后将索引为size-1处的元素置为null。为了让GC起作用，必须显式的为最后一个位置赋null值
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

总结：

1. 检查索引是否越界。
2. 将索引大于index的元素左移一位（左移后，该删除的元素就被覆盖了，相当于被删除了）。
3. 将索引为size-1处的元素置为null（为了让GC起作用，如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收）。

set(int index, E element)

    /**
     * Replaces the element at the specified position in this list with
     * the specified element.
     *
     * @param index index of the element to replace
     * @param element element to be stored at the specified position
     * @return the element previously at the specified position
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E set(int index, E element) {
        //检查下标是否越界
        rangeCheck(index);

        //记录被替换元素
        E oldValue = elementData(index);
        //替换元素
        elementData[index] = element;
        return oldValue;
    }

ArrayList源码

原文：https://www.cnblogs.com/leduoi/p/13532126.html