转载

java的ArrayList源码解析（初级）

默认初始化容量（未指定容量，并且要在调用add方法时才会用）
当ArrayList初始化时显示指定容量为0时的初始化数据
当ArrayList初始化时未显示指定容量时的初始化数据
ArrayList中存取数据的数组
数组中实际存储数据的大小
ArrayList中数组容量的最大值

构造方法

ArrayList有三个构造方法；

初始化时显示指定容量

当显示指定容量为0时，使用 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);
        }
    }
复制代码

初始化时未指定容量

未显示指定数组容量时，使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ;

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

将其他集合类转为ArrayList

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

常用的方法

add()方法

向ArrayList中添加元素；add方法有两种方式

直接添加数据，不指定位置

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
复制代码

该方法直接将数据存储到了数组的末尾，并且 size 会自增1，在增加数据之前会调用 ensureCapacityInternal 方法对数组容量进行校验，也就是自动扩容；扩容留到后边讲；

添加数据，并指定数据存储的位置

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 检查 index 是否越界，然后就是 ensureCapacityInternal 方法进行扩容校验，然后在调用 System.arraycopy 方法对原数组进行复制，将数组从下标为index到结尾的所有数据整体向后移一位，这个方法是很耗费内存的（我百度看到的博客基本上都是这么说的），这时候下标为 index 的那段空间就为空了，然后再将 element 插入数组中的指定位置；

System.arraycopy 方法图如下：

remove()方法

删除ArrayList中的元素；remove方法也有两种方式

根据下标删除

public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
        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;
    }
复制代码

rangeCheck 方法检查 index 是否越界;可以看出最后就是调用 System.arraycopy 方法来复制数组，将下标之后的所有元素向前移一位，然后 size 再自减;并且清空最后的元素，最后返回删除的元素；

传入元素删除数据

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

根据传入的数据来删除数组中的元素：

1. 当传入需要删除的元素为空时，首先会查找到第一个元素为`null`的下标，然后调用`fastRemove`方法删除元素；其中`fastRemove`方法与`remove(int index)`方法是一样的，只是没有返回值，这里就不贴代码了；
          2. 当传入`Object`不为`null`时，会循环数组，找到`o.equals(elementData[index])`为true时的元素的第一个下标，然后调用`fastRemove`来删除元素
复制代码

注意，都是删除的第一个相同的元素，后面的就不会管了；

现象：在才开始使用 ArrayList 的时候，用 for 循环来删除 ArrayList 中符合某一规则的元素，如果两个相同元素在连续的位置上，会出现不能全部删除现象，其实这是对 ArrayList 的 remove 方法的源码不熟了；

remove 方法是将数组复制了一遍，产生了新的数组，这时数组里面元素的下标都改变了，这时 for 循环并没有改变接着向后循环，所以相邻的一个元素就无法删除；

get()方法

获取ArrayList中的元素

就一种方式；根据下标获取元素

public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
复制代码

先调用 rangeCheck 检查下标是否越界,在获取元素

set()方法

修改ArrayList中额元素；

也是就一种方式：根据传入的下标及元素来修改

public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
复制代码

首先调用 rangeCheck 检查下标是否越界，获取下标元素值，然后再用传入的元素替换掉原来的元素；最后返回原来的元素；

size()方法

public int size() {
        return size;
    }
复制代码

获取ArrayList中实际使用的容量；不是数组容量；

数组容量自动增长

我们在使用ArrayList的时候都是调用add方法来添加元素，但是我们知道ArrayList是使用的数组来存储元素，而数组是有长度，为什么我们使用add方法可以一直添加元素且不会报错？

代码如下：

// 1
    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    //2
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //3
    private void grow(int minCapacity) {
        // overflow-conscious code
        //3.1
        int oldCapacity = elementData.length;
        //3.2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //3.3
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //3.4
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //3.5
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
复制代码

扩容使用到了四个方法

ensureCapacityInternal 方法主要是判断如果当前ArrayList是默认未指定容量的初始化时，然后选取 minCapacity 与 DEFAULT_CAPACITY 中的最大值赋予 minCapacity ，再传入下一个方法；
ensureExplicitCapacity 方法接受 minCapacity 参数，判断下标是否超过当前数组的容量，如果超过则调用 grow 方法，未超过则不调用；
grow 方法就是扩容的主要方法，选取扩容的值；

3.1 首先获取原来数组的长度 oldCapacity ;

3.2 进行扩容计算，代码中使用了位运算，增加的那部分为 oldCapacity 向右移一位的值，其实就是一半；

3.3 判断扩容后是否满足 minCapacity 值

3.4 判断扩容后的 newCapacity 是否超过ArrayList允许的最大值，如果超过就用最大值替换

3.5 调用 Arrays.copyOf 对数组进行扩容;

迭代器

代码如下：

//1
    public Iterator<E> iterator() {
        return new Itr();
    }
    //2
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;
        public boolean hasNext() {
            return cursor != size;
        }
        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();
            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
       
    }
复制代码

主要说 Itr 类中的三个变量及三个方法

三个变量：

cursor
lastRet
expectedModCount

三个方法：

hasNext 方法，判断 cursor 是否与size相等；就相当于判断下标是否越界；
next方法 ：获取下标为 cursor 的元素，且 cursor 自增1
remove 方法：调用了 ArrayList 中的 remove 方法删除下标为 lastRet 的元素，且 cursor 变为 lastRet 的值，这就解决了两个连续元素不能删除的现象了；