ArrayList解析-一一网

ArrayList的源码只有区区1477行,要分析完一遍不难，所以你不妨花上那么一点点时间去看看，里面有很多值得自己学习的地方的，ArrayList他是一个集合，那么围绕着集合说就增删查改，遍历几个玩法了，那就按照这个顺序，来看看增删查改、遍历这几个操作ArrayList是怎么做的。

看这几个操作前，我们要先明白ArrayList的几个参数的意思

//数组
transient Object[] elementData;

//数组默认大小
private static final int DEFAULT_CAPACITY = 10;

//集合大小
private int size;

//Jvm能给数组分配的最大空间
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

//版本次数
protected transient int modCount = 0;
复制代码

elementsData

这是ArrayList内部维护的一个数组，类型是Object类型的，那么看这个我们可以知道两个信息点：第一，ArrayList内部是数组结构的；第二，类型是Object类型的，那么我们只能传入对象，不能传入int这种，如果你传入int，这种都会进行类型包装的。

DEFAULT_CAPACITY

这是指elementsData数组默认的大小

size

这里指的是集合的大小，不是数组的大小，这点不能搞混了

MAX_ARRAY_SIZE

这里指的是Jvm能给数组分配的最大空间，如果超出了就会报错

modCount

修改了数组的版本次数，每一次增加删除都会进行++，这个参数是在父类AbstractList定义的

构造

首先是创建ArrayList，ArrayList提供了三种构造创建
第一种：判断传入的期望大小是多少，要么设置固定长度的数组，要么设为长度为0的数组，要么就报错(这里传入的是int类型的，所以最大是不会超过Integer.MAX_VALUE的)

 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的数组对象

  public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
复制代码

第三种：根据传入的Collection对象，直接toArray创建出一个数组对象，这里后续就是进行了一些判断，判断传入的Collection是否有值，如果有值，就在判断是否是Object类型的，如果不是转成Object类型，如果传入的Collection没有值，那就直接创建个空的对象数组

   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;
        }
    }
复制代码

ArrayList添加元素是一个亮点，他的扩容机制很有意思，首先我们看这两种添加单个元素的方式(addAll原理和这个一样)，ensureCapacityInternal这个方法就是我们的扩容，这一点先放一下，
第一种方法，就是直接数组的size进行++，然后进行赋值，size++是表示先用，再++，所以我们的下角标都是从0开始的。
第二种方法，添加到某个位置，先来了个判断，这个好理解，然后就是扩容，然后将数组拷贝一下，整体向后移动了一位，然后将当前index的位置进行赋值，大概的做法如下
20201211104203_Page_1_WPS图片.png

 	//第一种   
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	第二种
    public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
复制代码

ensureCapacityInternal这个方法是进行扩容的，当我们第一次添加数据的时候，elementData的大小是空的，所以我们的数组的大小是10；minCapacity这个值表示的是我们期望的大小

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
复制代码

版本计数+1，然后去判断我们期望的值是否大于当前数组的长度，如果大于，那么就表示真要扩容了

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
复制代码

这里才是扩容的真正代码，我直接在代码中进行注释一下;将我们的当前数组大小扩充1.5倍(这里可以记住一个很经典的点，数组越小，扩容后结果越小，数组越大，扩容后结果越大，你品、你细品，是不是很节省资源，数据少的时候给的空间就少，不占空间，数据大的时候一次给你多扩些，也可以避免多次触发扩容)

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //oldCapacity >> 1这里就是oldCapacity*0.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //当前扩容后的长度是否大于我们的期望值，如果不大于，那么就用期望值作为新的长度值
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //增加判断是否超过了jvm能给分配到的最大空间，超出了，就用Integer.MAX_VAlUE作为新的长度值
        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);
    }
复制代码

remove

根据角标删除的，老规矩修改版本次数+1（每次对数组有长度影响的时候都会进行+1的）

    public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        //先获取到我要删除的元素，等会要返回出去的
        E oldValue = (E) elementData[index];
		//计算出我从index开始要有多少个元素要往前移
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //将我要移动的index这个位置+1及后面的所有元素往前拷贝一位去
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
       	//将我要要删除的元素置空，帮助gc回收工作，然后集合的size减少1
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
复制代码

根据对象删除，他需要遍历所有的元素，这里做了个判断，因为我们的集合是可以添加null的，所以他这里会删除掉第一个null ,如果我们删除的不是null，就会去equals,然后删除第一个(所以呀，ArrayList每次执行remove对象的时候只会一个一个删除，这里千万别搞错了，别以为是删除里面所有的匹配的对象，他这里删除了一次就会return出去的)

    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;
    }
复制代码

   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
    }
复制代码

这两个就是直接去获取数组中的元素或者修改数组中的元素

    public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }
复制代码

   public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }
复制代码

遍历

遍历我们可以用fori、foreach、iterator，这里既然是看ArrayList的源码，就说ArrayList提供的iterator吧，适配器都是去实现Iterator接口的，那么ArrayList的也不例外
他有几个核心参数

protected int limit = ArrayList.this.size;//当前集合的size
 //下一个元素的位置		
 int cursor;       // index of next element to return
 //上次迭代时，元素的位置，如果上一次是删除，那么我们的lastRet是-1
 int lastRet = -1; // index of last element returned; -1 if no such
 //迭代过程中期望的版本号，初始化时是我们的版本修改次数
 int expectedModCount = modCount;
复制代码

还有几个核心方法
判断当前的元素位置是否大于了集合大小，每次next的时候cursor都会+1

public boolean hasNext() {
    return cursor < limit;
}
复制代码

比较了两次版本号是否一次，我们期望的版本号与实际数组的版本号是否一致，如果不一致就会抛出异常

@SuppressWarnings("unchecked")
public E next() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    int i = cursor;
    if (i >= limit)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    //每次next的时候都将cursor+1
    cursor = i + 1;
    //返回我们当前的next时的值，然后把它赋值给lastRet
    return (E) elementData[lastRet = i];
}
复制代码

删除的时候和上面一样都对比了版本号，而我们的版本号在每次添加、删除的时候都会进行改变，所以我们在进行遍历的时候，是不能去对list做增加删除操作的，不然就会抛出异常，因为版本号肯定会不一样，而用iterator的删除就不一样了，他会执行完remove方法后，将我们当前的数组最新的版本号重新复制给expectedModCount，以保证两个版本号的一致性
上面讲的需要关联到一个点，不管你是怎么遍历，都不能在遍历的时候直接去对集合做增加删除操作，比如foreach他底层遍历是调用next，并没有改变什么版本号，所以你直接去list.remove后版本号肯定会不一致的，莫忘咯

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    try {
        //执行删除操作
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        //将当前的时候版本号进行同步更改一下
        expectedModCount = modCount;
     	//当前的长度-1
        limit--;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}
复制代码

总结

ArrayList是线程不安全的，我们在里面没有看到加锁的操作，如果想要加锁的，可以使用Collections的synchronizedList；
ArrayList内部是维护了一个数组，每次增加删除都是对数组进行拷贝操作，都是调用System.arraycopy这个进行数组拷贝，而查找与更新都是直接对数组进行赋值或者获取，所以增加删除效率低，因为每次都要执行数据拷贝操作，包括其数据扩容也是执行了拷贝操作的；
ArrayList的扩容机制挺骚的，可以吸取；
ArrayList的数组上下限，定位0-Integer.MAX_VALUE，这不会让开发者无休止的去添加

文章版权归作者所有，未经允许请勿转载。

THE END

代码人生