ArrayList内部实现原理

• 初始化
• • 添加元素add
  • 扩容
  • 移除元素Remove

初始化

无参构造初始化

transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
           

说明当new ArrayList<>()时只是给内部属性赋了员工Object类型的空数组

有参构造初始化 当是数值类型时

private static final Object[] EMPTY_ELEMENTDATA = {};
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);
        }
    }
           

会先判断传入的值是否大于0，大于0就把实例化一个大小为参数值得数组，等于就赋值为空数组，否则抛出异常

有参构造初始化 当是数值类型时

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
           

先把集合转换为数组，然后判断数组的值大小是否大于0，大于0后，判断传入的类型是否为Object.class,这里的判断toArray方法返回的不一定是Object类型，因为数组也有自己.class类型如

String [] m  = new String[0];//这里的class是Ljava.lang.String
Object [] n  = new Object[0];//这里的class是Ljava.lang.Object
           

两者完全不一样，还因为子类重写父类toArray方法的时候，不修改返回值类型的前提下，子类返回了什么类型，具体得到的是子类的返回值类型，而不会上转成父类的返回值类型,所以当类型不是Ljava.lang.Object需要调用方法重新转换为Ljava.lang.Object的类型

添加元素add

直接添加元素

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 初始化容量
        elementData[size++] = e;//赋值并记录size
        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);
    }
           

ensureCapacityInternal是容量的初始化，方法中判断数据如果为空数组，设置容量为默认10或者比10更小的值，然后ensureExplicitCapacity方法判断需不需扩容，当扩容的最小容量大于当前实际的容量大小 这里用减法是因为： a<b 和 a-b<0 计算机中不同，因为数字用的是有限位的补码，也正是因此才会有考虑溢出的代码

添加到指定下表位置的元素

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

rangeCheckForAdd方法判断下传入的下标是否小于0或大于容量的size，判断下标值是否符合范围内；然后进行容量的初始化，system.arraycopy就是移动元素后移一位，然后index下标的值就为空，然后把添加的值进行赋值

扩容

grow方法

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.5倍扩容，新扩容后的容量小于最小容量，新容量就为最小容量minCapacity，如果新容量比限制最大的容量MAX_ARRAY_SIZE （Integer.MAX_VALUE - 8）大，就比较最小容量是不是比限制最大的容量大，大于取最大容量，小于取最小容量， ArraysopyOf(elementData, newCapacity)进行重新赋值

移除元素Remove

移除指定值

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(index);
                    return true;
                }
        }
        return false;
    }
           

移除指定值会先遍历数组，然后找到指定值的下标，然后调用fastRemove(index)进行移除

private void fastRemove(int 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
    }
           

modCount记录当前对象的次数，numMoved 是计算移除数据后需要移动的元素个数，移动的个数大于0，说明指定的删除的元素不是最好一个元素，就需要移动后面的元素往前移动一位，这里就存在一个问题，遍历元素删除元素时，删除元素，后面元素会移动，造成下一个元素无法遍历到，造成数据错误，所有用for循环删除元素不可取的

elementData[–size] = null;是清除引用，为了让GC能够回收对象。

一开始不明白为什么需要modCount记录当前对象的修改的次数

final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
           

这个方法说明为什么要记录修改次数，当集合遍历时，防止其他线程对数组进行操作，如果修改次数不一致，说明集合已经被其他线程修改，然后抛出异常ConcurrentModificationException。

以上纯属个人见解，有什么问题可以指出来