# ArrayList详解

## ArrayList概念

​	ArrayList其实是一个数组，数组是一种线性表数据结构，使用一组连续的内存空间来存储同一种数据类型；特点：

​	1：增删慢，每次删除元素都要更改数组长度，拷贝和移动元素位置；（为了保证数据的连续性）

​	2：查询快，可以根据地址+索引的方式快速获取对应位置上的元素；

​	内存寻址：计算机在分配内存的时候，会给每个内存单元都分配了一个地址，然后通过地址来访问数据；比如new int[5]; 计算机会给数组分配一块连续的内存空间，并且得到这个内存空间的起始位置，比如从0-4；，所以如果要通过地址来访问数据的时候，计算机有一个寻址公式来到得到其地址；

## ArrayList类

```
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
```

### Serializable 标记性接口

不实现这个类的接口将不会使用任何状态序列化或反序列化，可序列化类的所有子类型都是可以序列化的；比如 你写了个people类，他是可序列化的，那么people的子类也是可以序列化的；

而且这个序列化的接口是没有方法或者字段的，仅仅是标识可串行序列化的语义；仅仅一个标记是什么意思？就是啥都没有，点进该类看看就知道了，说白了 ，你的名字有意义没？是不是感觉也没多块肉，也没少块肉，但是别人一叫你，你就知道是叫你，所以名字的意义是什么呢？

那么序列化有什么作用呢？

序列化：将对象得数据写入到文件（写对象）

反序列化：将对象数据从文件中读取出来

不使用就会无法写入数据，写入到文件中；

### Cloneable 标记性接口

克隆就是可以创建一份新的完全一样的数据拷贝，如果不实现这个接口，克隆的时候会出问题；CloneNotSupprotedException

源码分析：clone方法其实调用的native层的clone，（super.Clone）的时候，调用的是object对象的clone方法；

拷贝分为以下两种方式：

浅拷贝：基本数据类型可以达到复制，引用数据类型则不可以；比如Animail类里有一个bird类，那么就会出问题，原因在于克隆的时候，其属性bird仅仅是拷贝了一份引用，因此当bird值改变时，被克隆的对象属性bird也会跟随改变；

使用浅拷贝的时候，该类需要实现Cloneable接口，并且实现clone()方法；

深拷贝：主类的基本数据类型和引用数据类型都可以进行拷贝，但需要注意的是，主类中的引用类型数据需要重写clone方法；然后在主类中修改clone方法；具体的代码请参考本节课项目代码中的com.mnarraylist.copy包；

### RandomAccess 标记性接口

该接口主要由List实现，用来表示支持快速随机访问；这个接口的目的是为了让一些通用的算法可以更改行为；比如随机访问列表或者顺序访问列表的时候能够提供更好的性能；

```
for(int i=0;i=list.size();i++){
	list.get(i) // 这种方式就是典型的随机访问列表，因为我们可以根据i来指定我们需要访问具体的某个索引上的值；
}
```

随机访问列表的速度要比顺序访问的速度要快

```
Iterator<String> it = list.iterator();
while (it.hasNext()){
    it.next();// 这种方式就是典型的顺序访问，因为它的访问顺序是一个接着一个；
}
```

具体的测试代码请参考项目代码中的com.mnarraylist.random;

RandomAccess总结：如果你实现了这个接口，那么在进行随机访问的时候，速度会变得更快；如果你没有实现这个类，随机访问的速度不会变快；比如LinkedList就没有实现这个接口，那么它的顺序访问速度比随机访问速度要快；根据这个知识点，以后遇到要循环集合的时候，就可以想一下，这个集合是否使用实现了RandomAccess，如果实现了则使用随机访问的方式进行迭代，不然则使用顺序访问的方式； 

### AbstractList 抽象类

该类提供了List接口的骨架实现，以最小化实现由“随机存取”数据存储（如阵列）支持的此接口所需的工作量，对于顺序访问数据（例如链表列表），应该使用AbstractSequentialList优先；

要实现一个不可修改的列表，开发者只需要拓展这个类并提供get(int)和size()方法实现；

要实现可修改的列表，开发者必须覆盖set(int,E)方法（否则将抛出UnsupportedOprationException），如果列表可变大小，开发者必须覆盖add(int,E)和remove(int)方法。

根据Collection接口规范中的建议，开发者通常情况下应该提供一个无参以及集合构造函数；

而且程序员不必提供迭代器实现，迭代器和列表迭代器由此类实现；

（以上皆来自JDK官方对于AbstractList定义）

通俗的解释：AbstractList针对List集合做了一些通用的定义，如果你要自定义List，该List的行为与AbstractList中的功能重合，则不必自己实现，然后根据自己的需求去重写AbstractList其他的方法；

## ArrayList源码解析

### 构造函数

```
public ArrayList() { // 无参构造
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        // 当我们调用ArrayList时，会创建一个空数组（Object类型）
}
```

```
public ArrayList(int initialCapacity) {// 有参构造
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];  //创建你传进来大小的数组
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA; // 如果传进来的是0，则默认是个空数组
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
```

```
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();   // 将集合转成数组 （toArray方法本质上是创建了一个新的数组，新数组的长度一定和集合的size一样）
    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.  // 将空数组赋值给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}
// 知识点：c.toArray()调用的其实也是Arrays.copyOf方法，而这个方法的底层逻辑都是调用
// System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
// original：源数组  0：源数组起始位置 copy：目标数组，0：目的数组的起始位置；Math.min(original.length, newLength)：要复制的数组元素数量；
// 另外这种方式的拷贝属于浅拷贝；
```

### add(E e)

add方法基本的源码调用阶段如下：

```
public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 扩容之后，将值放在size++的索引上
        elementData[size++] = e;
        return true;
    }

 private void ensureCapacityInternal(int minCapacity) {
 // 判断elementData是否等于空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 如果相等，最小的capacity就等于传进来的参数与默认的（10）中最大的数；相当于如果你添加的是第一个数，那么这个时候要需要扩容
        // 扩容的时候相当于加10；
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;  //实际修改数组的次数
        // 假设第一次调用这个方法，minCapacity会等于系统给的默认值10，你的elementData.length为0，必然走扩容；
        // 当你第二次调用的时候，minCapacity等于数组的实际数据长度（比如你添加了2次，那么这个数为2），而elementData.length等于第一次的10，所以不会走扩		// 容数组；
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);  // 扩容数组
    }
    
    private void grow(int minCapacity) {
        // 将初始化之后的elementData的长度赋值给oldCapacity
        int oldCapacity = elementData.length;
        // 新数组长度等于老数组长度加上老数组右移1位；这边扩容相当于是原容量的1.5倍；
        int newCapacity = oldCapacity + (oldCapacity >> 1); // >> 右移几位可以简单的认为是除以2的几次幂； << 左移可简单认为乘以2的几次幂；
        if (newCapacity - minCapacity < 0)//如果新数组的长度减去传进来的长度（10）小于0，就说明这次想要的扩容没意义；
            newCapacity = minCapacity;//新数组的长度就等于传进来的（10）；
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//如果新数组的长度-最大的值还大于0，就给它一个Integer里面最大的值；
        // 然后进行拷贝
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
```

### add(int index, E element)

```
public void add(int index, E element) {
        if (index > size || index < 0) // 判断插入数据的时候是否越界
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            // 跟之前走的方法一样；
        ensureCapacityInternal(size + 1);  
        // original：源数组  0：源数组起始位置 copy：目标数组，0：目的数组的起始位置；Math.min(original.length, newLength)：要复制的数组元素数量；
        // 从elementData进行拷贝；从传入的索引开始（比如1）；拷贝到原来的数组；拷贝到位置加1的地方；拷贝的长度为总元素的长度减去传进来的索引位置；
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将添加进来的元素放到指定的索引上
        elementData[index] = element;
        size++;
    }
```

### addAll(Collection<? extends E> c)

```
public boolean addAll(Collection<? extends E> c) {
//将传进来的集合转成数组
    Object[] a = c.toArray();
    // 得到数组的长度
    int numNew = a.length;
    // 走一下是否扩容的代码
    ensureCapacityInternal(size + numNew);  // Increments modCount
    //拷贝
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    // 返回是否拷贝成功，如果你传进来的数组长度为0，这里返回的是false；
    return numNew != 0;
}
```

### addAll(int index, Collection<? extends E> c)

```
public boolean addAll(int index, Collection<? extends E> c) {
// 校验索引
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

// 要移动元素的个数  （目标源的长度减去传进来的索引）
    int numMoved = size - index;
    if (numMoved > 0)
    	// 使用arrayCopy进行移动
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);
	
    // 真正将数据源（刚传进来的数组）添加到目的
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}
```

### E set(int index, E element)

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

### E get(int index)

```
public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	// 直接获取
    return (E) elementData[index];
}
```

### Iterator<E> iterator()

```
public Iterator<E> iterator() {
	// 创建一个对象
    return new Itr();
}
private class Itr implements Iterator<E> {
        
        protected int limit = ArrayList.this.size;

        int cursor;       // 游标 指向下一个应该被返回的索引 默认值为0
        int lastRet = -1; // 前一个记录 默认值-1
        // 将实际修改次数赋值给期望修改次数
        int expectedModCount = modCount;

        public boolean hasNext() {
        // 如果当前游标小于limit（list的长度）则说明还有；
            return cursor < limit;
        }
		public E next() {
            if (modCount != expectedModCount)//如果实际修改的次数不等于预期修改的次数；错误叫：并发修改异常
                throw new ConcurrentModificationException();
                // 将游标赋值给i
            int i = cursor;
            if (i >= limit) //大于则抛出异常
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;//获取arraylist中的elementData数组
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;//游标+1
            return (E) elementData[lastRet = i];//从数组中取出元素并返回
        }
    }
```

### list.remove(Object  o)

```
public boolean remove(Object o) {
    if (o == null) {// 判断是否为null，为null就删除
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
    // 处理不为null的情况
        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);
        // 将删除的元素置为null，让GC回收 --size 等于size-1
        elementData[--size] = null; // clear to let GC do its work
}
```

### iterator.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;
        limit--;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}
```

### clear()

```
public void clear() {
    modCount++;
		
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
	// 全部置为nul，让GC好回收，size直接赋值为0
    size = 0;
}
```

### contains(Object o)

```
public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
    // 也是循环对比数据
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
```

### isEmpty()

```
public boolean isEmpty() {
    return size == 0;
}
```



问题：

ArrayList频繁扩容导致性能低下如何优化？

答：原因：主要是因为每次都是1.5倍的扩容，第一次默认是10；所以如果数据够大，扩容的次数就会增加；可以通过创建ArrayList的时候直接指定数组长度；

优化删除方式，数组在删除数据的时候会进行数据的迁移，如果频繁删除，可以前期先使用某种方式记录下来，然后集中在一起进行删除；

System.arraycopy是属于深拷贝还是浅拷贝？

答：浅拷贝

如果拷贝的是一个二维数组，拷贝之后修改新的数组是否会影响之前的数据？（数组中的数据都是基本类型）

答：会影响，因为数组是引用类型，拷贝底层是浅拷贝，所以只会复制引用；

ArrayList是否线程安全？

答：线程不安全，如果多个线程要进行访问，可使用同步关键字；也可以使用Vector来替代List，它内部实现了线程安全；但Vector的速度相对来说比较慢；



