java高级-ArrayList

# ArrayList原理

[视频地址](https://www.bilibili.com/video/BV1gE411A7H8/)

在本套课程中，我们将全面深度剖析ArrayList原理，包含底层数据结构、扩容机制、性能分析、底层源码解析、以及各种和ArrayList相关的面试题等。让我们不仅是学习ArrayList基本应用，而且通过底层原理分析让大家更深层次的理解ArrayList，甚至在某些性能方面会颠覆我们对于它的认知,同时在面试方面会给我们带来更大优势。

## 学习目标

- ArrayList集合底层数据结构介绍
- ArrayList继承关系
- ArrayList源码分析
- 面试题讲解
- 自定义ArrayList

## ArrayList集合底层数据结构介绍

ArrayList是由动态再分配的Object[]数组作为底层结构，可设置null值，是非线程安全的。

### ArrayList集合介绍

List 接口的可调整大小的数组实现。

数组:一旦初始化长度就不可以发生改变。

### 数组结构介绍

增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
    查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。

## ArrayList 继承关系

### Serializable 标记接口

略。

### Cloneable 标记接口

#### 浅拷贝

基本数据类型可以完全复制，引用数据类型则不可以。

to add code

#### 深拷贝

to add code

### RandomAccess 标记接口

随机访问和顺序访问

顺序访问（通过迭代器）：链表在内存中不是按顺序存放的，而是通过指针连在一起，为了访问某一元素，必须从链头开始顺着指针才能找到某一个元素。

随机访问（通过索引）：数组在内存中是按顺序存放的，可以通过下标直接定位到某一个元素存放的位置。

鼓励通用列表算法在使用时，检查给定列表是否为 instanceof RandomList，若是，则使用如下方式遍历：

```java
    for (int i = 0, n = list.size(); i < n; i++) {
        list.get(i);
    }
```

否则，使用迭代器方式遍历：

```java
    for (Iterator i = list.iterator(); i.hasNext();) {
        i.next();
    }
```

### AbstractList 抽象类

## ArrayList源码分析

### 构造方法

- `ArrayList()` 构造一个初始容量为十的空列表。
- `ArrayList(int initialCapacity)` 构造具有指定初始容量的空列表。
- `ArrayList(Collection<? extends E> c)` 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。

注意点：

- 通过ArrayList()构造方法创建集合对象`并未构造一个初始容量为十的空列表`，仅仅将DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址赋值给elementData。
- 根据ArrayList(int initialCapacity)构造方法创建一个长度为initialCapacity的数组。
- 根据ArrayList(Collection<? extends E> c)构造方法创建指一个长度为c.size()的数组。

### 添加方法

- `public boolean add(E e)` 将指定的元素追加到此列表的末尾。
- `public void add(int index, E element)` 在此列表中的指定位置插入指定的元素。
- `public boolean addAll(Collection<? extends E> c)` 按指定集合的Iterator返回的顺序将指定集合中的所有元素追加到此列表的末尾。
- `public boolean addAll(int index, Collection<? extends E> c)` 将指定集合中的所有元素插入到此列表中，从指定的位置开始。

注意点：

- 添加方法（可能）会导致ArrayList底层数组扩容，扩容规律为从0到10、再每次变成1.5倍。
- add(int index, E element)和addAll(int index, Collection<? extends E> c)会导致数组元素移动，移动的元素是从index开始到size-1，每个元素都往后移动1或c.size()个元素。

### 删除方法

- `public E remove(int index)`  根据索引删除元素
- `public boolean remove(Object o)`  根据元素删除元素

注意点：

- `remove(int index)`会导致数组元素移动，移动的元素是从index+1开始到size-1，每个元素都往前移动1个元素。
- 删除方法不会导致ArrayList底层数组扩容。

### 修改方法

- `public E set(int index, E element)` 根据索引修改集合元素

注意点：

- `set(int index, E element)`会不导致数组元素移动。
- 修改方法不会导致ArrayList底层数组扩容。

### 获取方法

- `public E get(int index)` 根据索引获取元素

注意点：

- `get(int index)`会不导致数组元素移动。
- `get(int index)`查询速度很快，因为可以直接定位元素。
- 修改方法不会导致ArrayList底层数组扩容。

### toString()方法

toString()方法中使用了迭代器方法`iterator()`。

### 迭代器方法

- `public Iterator<E> iterator()` 普通迭代器

问题：已知集合List<String> list = new ArrayList<>()里面有三个元素："hello"、"world"、"java"，使用迭代器遍历集合看有没有"PHP"这个元素，如果有，就使用集合对象删除该元素。

错误代码如下：

```java
    @Test
    public void testRemove() {
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");

Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("java")) {
                // 注意此行，若"java"不是倒数第二个元素，则会抛出ConcurrentModificationException
                list.remove("java");
            }
        }
        System.out.println(list);
    }
```

如上错误代码中，使用Iterator遍历数据时，却使用list来删除数据，会抛出ConcurrentModificationException，如下为正确代码：

```java
    @Test
    public void testRemoveViaIterator() {
        List<String> list = new ArrayList<>();
        list.add("hello");
        list.add("world");
        list.add("java");

Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String s = it.next();
            if(s.equals("java")) {
                // 注意此行
                it.remove();
            }
        }
        System.out.println(list);
    }
```

结论:

- 迭代器remove()方法底层调用的还是集合自身的remove方法删除元素。
- 之所以不会产生并发修改异常，是因为在迭代器的remove()方法中会再次将 集合时机修改次数赋值给预期修改次数。
- 当删除ArrayList中倒数第二个元素时，不会出现ConcurrentModificationException。

### 清空方法

- `public void clear()` 清空集合所有数据

注意点：

- 将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉。
- clear()方法不会导致ArrayList底层数组扩容。

### 包含方法

- `public boolean contains(Object o)` 判断集合是否包含指定元素

注意点：

- contains(Object o)方法会调用indexOf(Object o)。

### 判断集合是否为空

- `public boolean isEmpty()`

## 常见面试题

### ArrayList是如何扩容的？

第一次扩容10，以后每次都是原容量的1.5倍。

### ArrayList频繁扩容导致添加性能急剧下降，如何处理？

在特定场景中，如果可以明确知道会有多少个元素，可以使用ArrayList(int initialCapacity)构造方法来直接指定元素个数，避免扩容。

### ArrayList添加或删除元素一定比LinkedList慢么？

ArrayList 添加元素时（可能）会导致扩容和数据复制，删除元素时会导致据复制，但是在ArrayList底层不是每次删除元素都需要扩容，因此在这个方面相对于链表来说数组的性能更好。

LinkedList 添加和删除元素之所以效率并不高，其原理在于底层先需要对整个集合进行折半的动作，然后又需要对集合进行遍历一次，这些操作导致效率变低。

### ArrayList是线程安全的吗？

ArrayList不是线程安全的。

示例程序（可以创建一个Thread子类，将ArrayList作为构造方法传进来，在run()中对ArrayList进行添加数据。再创建测试方法，创建50个线程，看最终ArrayList中是否有50个元素。）

需要线程安全怎么办?

方式一: 使用Collections.synchronizedList(list) 
方式二：使用synchronized加锁锁住对list的操作

#### 如何复制某个ArrayList到另一个ArrayList中？

- 使用clone()方法
- 使用ArrayList构造方法
- 使用addAll方法

#### ArrayList 和 LinkList区别？

##### ArrayList

- 基于动态数组的数据结构
- 对于随机访问的get和set，ArrayList要优于LinkedList
- 对于随机操作的add和remove ，ArrayList不一定比LinkedList慢(ArrayList底层由于是动态数组，因此并不是每次add和remove的时候都需要创建新数组)

##### LinkedList

- 基于链表的数据结构
- 对于顺序操作，LinkedList不一定比ArrayList慢
- 对于随机操作，LinkedList效率明显较低

ArrayList使用在查询比较多，但是插入和删除比较少的情况，而LinkedList用在查询比较少而插入删除比较多的情况

### ArrayList类中会抛出如下异常：

- IndexOutOfBoundsException
- NullPointerException
- CloneNotSupportedException
- IllegalArgumentException
- ConcurrentModificationException

### CopyOnWriteArrayList

用于读多写少的场景。

在add()/remove()/set()/clear()/sort()/subList()时会加锁。

## 自定义ArrayList

详见代码。