ArrayList源码解读

• • **ArrayList源码解读**
  • • • **方法解析**
      • • **增加:add(),addAll()**
        • **扩容**
        • **获取元素（索引）**
        • **删除：remove()**
        • **修改:set()**
      • **自己实现一个简单的ArrayList**
      • **总结**

public class ArrayList extends AbstractList
        implements List, RandomAccess, Cloneable, java.io.Serializable
{
	
    private static final int DEFAULT_CAPACITY = 10;

   
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    
    transient Object[] elementData; 

    
    private int size;
    
    
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    
    
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //指定该ArrayList容量为0时，返回该空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
 }

public boolean add(E e) {
    //确保数组大小足够，不够需要扩容（期望容量=size+1）
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //直接赋值，线程不安全的
    //注：这里没有非空判断，因此可以加入null
    elementData[size++] = e;
    // 这里虽然是boolean，但一般只会返回true
    return true;
}

public boolean addAll(Collection c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // 确保容量充足，整个过程只会扩容一次（期望容量=size+a.length)
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 直接将要加入的集合拷贝到elementData后面即可
    // 注：Arrays.copyOf适用于1-->2的拷贝,而sys..适用于对原数组或指定数组的操作
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    // 只有要增加的集合为空时，返回false
    return numNew != 0;
}

private void ensureCapacityInternal(int minCapacity) {
        //第一步如果原数组为空,那么长度为10,要不然就加一
        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);
 }
 
 
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //增加到原容量的1.5倍,(oldCapacity >> 1)向前移一位，相当于除2，这里用位运算更快
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩容后的值 < 我们的期望值，就以期望值进行扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 通过复制进行扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
 }

总结：

1. 新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
2. 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，即原来容量的 1.5 倍。
3. ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。 源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组下界不能小于 0，上界不能大于 Integer 的最大值
4. 扩容完成之后，赋值是非常简单的，直接往数组上添加元素即可：elementData [size++] = e。也正是通过这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的

扩容是通过这行代码来实现的：Arrays.copyOf(elementData, newCapacity);，这行代码描述的本质是数组之间的拷贝，扩容是会先新建一个符合我们预期容量的新数组，然后把老数组的数据拷贝过去，我们通过 System.arraycopy 方法进行拷贝。

 
 public E get(int index) {
     rangeCheck(index);
     return elementData(index);
 }

 
 public E remove(int index) {
        rangeCheck(index);

        modCount++;
        E oldValue = elementData(index);
        //该index之后的长度
        int numMoved = size - index - 1;
        //将index之后的数据往前移一位
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
 }
    
 
 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++;
        // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去
        // 减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起
        int numMoved = size - index - 1;
        if (numMoved > 0)
        // 从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
        //数组最后一个位置赋值 null，帮助 GC
        elementData[--size] = null;
}

• 修改:set()

public E set(int index, E element) {
    //判断索引是否越界   
    rangeCheck(index);
    //获取旧索引的元素，用于返回
    E oldValue = elementData(index);
    //然后将索引对应位置指向新参数
    elementData[index] = element;
    return oldValue;
}

public class myArrayList{
    //ArrayList底层采用数组存放
    private Object[] elementData;
    //默认数组容量
    private static final int DEFAULT_CAPACITY = 10;
    //记录实际ArrayList大小
    private int size;

    public myArrayList(int initialCapacity){
        if(initialCapacity<0){
            throw new IllegalArgumentException("初始容量不能小于10");
        }
        this.elementData=new Object[initialCapacity];
    }
    //默认值为10
    public myArrayList(){
        this(DEFAULT_CAPACITY);
    }

    //获取数组大小
    public int getSize(){
        return size;
    }

    //判断数组是否为空
    public boolean isEmpty(){
        return size==0;
    }

//    //在数组中间插入一个元素
//    public void add(int index,E e){
//        if(index<0||index>size){
//            throw new IllegalArgumentException("添加失败，下标应该大于等于0或者小于数组大小");
//        }
//        if(size==elementData.length){
//            throw new IllegalArgumentException("添加失败，数组满了");
//        }
//
//        for(int i=size-1;i>=index;i--){
//            elementData[i+1]=elementData[i];
//        }
//        elementData[index]=e;
//        size++;
//    }
//    //在数组结尾添加元素
//    public void add(E e){
//        add(size,e);
//    }
//    //在数组首部添加元素
//    public void addFirst(E e){
//        add(0,e);
//    }
    public void add(E e) {
        // 1.判断实际存放的数据容量是否大于elementData容量
        ensureExplicitCapacity(size + 1);
        // 2.使用下标进行赋值
        elementData[size++] = e;
    }

    public void add(int index, Object object) {
        //1.容量检查，如需要扩容则进行扩容。
        ensureExplicitCapacity(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = object;
        size++;
    }

    //minCapacity为扩容时最少需要的容量
    private void ensureExplicitCapacity(int minCapacity) {
        if (size == elementData.length) {
            //获取当前数组的容量
            int oldCapacity = elementData.length;
            //需要扩容的容量。新容量=当前容量+当前容量/2,即将当前容量增加一半
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("添加失败");
        }
        elementData[index] = e;
    }

    //查找元素e的下标
    public int find(E e){
        for(int i=0;isize){
            throw new IllegalArgumentException("下标错误");
        }
        return (E) elementData[index];
    }
    // 判断是否含有元素
    public boolean contains(E e){
        for(int i=0;isize){
            throw new IllegalArgumentException("删除失败，下标错误");
        }
        E o = (E) elementData[index];
        for(int i=index+1;i list = new myArrayList<>();

        System.out.println(list.isEmpty());

        list.add(1);
        list.add(2);
        list.add(1);
        list.add(2);
        list.add(1);

        System.out.println("删除前");
        for(int i=0;i 
总结 
面试时关于 ArrayList 要说的事
 
如果有人问你 ArrayList 知多少，可以从这几个方面出发：
 
1.ArrayList 的底层是基于数组进行的，进行随机位置的插入和删除、以及扩容时性能很差，但进行随机的读和取时速度却很快。
 
2.接着可以从源码的角度分析 add、remove、set、get、数组扩容拷贝的过程场景。
 
3.最后也是特别重要的一点，就是要积极掌握主动性，延伸出 linkedList 的特点、源码、两者间的对比等。
 
注：当需要动态数组时我们通常使用 ArrayList 而不是使用类似的 vector，这里有一点说明一下，就是尽管 Vector 的方法都是线程安全的，但其在单线程下需要花费的时间更多，而 ArrayList 尽管不是线程安全的，但其花费的时间很少。
 
}
 ``