Java-集合之ArrayList_extends arraylist

源码解读

从源码中我们可以看到ArrayList是在util包下的一个类，ArrayList继承了AbstratList类，实现了List<E>接口等。
也就是说ArrayList<E>拥有AbstratList的数据属性和行为，并实现了List<E>(底层由数组实现的有序集合),RandomAccess(支持快速随机访问)，Cloneable(浅度克隆)，Serializable(可序列化)

ArrayList的继承与实现关系

可以使用UML图表进行渲染。 Mermaid. 例如下面产生的一个序列图：

ArrayList的成员变量

一 serialVersionUID:（序列号版本ID，确保序列化的对象正确）
二 DEFAULT_CAPACITY: 从注释可以看到是默认初始容量为10
三 EMPTY_ELEMENTDATAL: 一个空的对象数组
四 DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 一个默认容量大小的空的对象数组，在第一次添加元素的时候。
五 elementData: 根据注释我们可以理解为任何一个对象数组等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA为他创建一个容量为DEFAULT_CAPACITY（也就是10）的EMPTY_ELEMENTDATA:（空的对象数组），在第一次添加元素的时候。
六 size: 为elementData的元素个数，注: elementData.length()是指可添加元素的最大容量

注：以上三和四都是空的数组，那么他们的区别是什么呢？在介绍完构造方法后进行说明。

ArrayList的构造方法-无参构造

package com.hzx.test;

import java.util.ArrayList;

public class ListTest {
    public static void main(String[] args) {

        ArrayList<Object> arrayList = new ArrayList<>();

    }
}
1
2
3
4
5
6
7
8
9
10
11

debug进入源代码，可以我们看到调用的是以下方法

将当前数组设置为默认容量为10的空对象数组。注：虽然注释上时说新建一个默认容量为10的空对象数组，实际容量是在第一次添加元素的时候被赋值的。

现在我们验证一下我们理解是否有误，通过反射获取ArrayList的私有成员变量

package com.qlk.insurance;

import java.lang.reflect.Field;
import java.util.ArrayList;

public class ListTest {
    public static void main(String[] args) {

        ArrayList<Object> arrayListsSize = new ArrayList<>();
        arrayListsSize.add("a");
        System.out.println("arrayListsSize实际长度为：" + arrayListsSize.size());
        int capacity = getCapacity(arrayListsSize);
        System.out.println("arrayListsSize最大容量为：" + capacity);

    }

    /**
     * 利用反射获取集合最大容量
     * @param list
     * @return 集合最大容量
     */
    public static int getCapacity(ArrayList<?> list) {

        //获取class对象
        Class<? extends ArrayList> listClass = ArrayList.class;

        try {
            //获取对象本身的属性成员elementData
            Field field = listClass.getDeclaredField("elementData");

            //临时改变访问权限，访问对象的私有方法，成员变量的值
            field.setAccessible(true);

            //将类型转换一下，我们这里已经知道集合实际是一个对象数组
            Object[] elementData = (Object[]) field.get(list);

            //获取对象当前可用最大容量
            return elementData.length;

        } catch (NoSuchFieldException e) {
            e.printStackTrace();
            return -1;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

验证成功，理解正确。

ArrayList的构造方法-有参构造（指定容量）

    public static void main(String[] args) {
		//反射的方法如上，节约篇幅，这里不进行复制。
        ArrayList<Object> arrayListsSize = new ArrayList<>(20);
        arrayListsSize.add("a");
        System.out.println("arrayListsSize实际长度为：" + arrayListsSize.size());
        int capacity = getCapacity(arrayListsSize);
        System.out.println("arrayListsSize最大容量为：" + capacity);

    }
1
2
3
4
5
6
7
8
9

我们再看看源码是如何实现的

如果容量的入参大于0则新建一个该容量大小的对象数组赋值给elementData；
容量为0 则将EMPTY_ELEMENTDATA赋值给到elementData（而他在新增第一个元素时或将容量设置为默认容量10）。

看到这里我们发现了无参构造是将DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData；有参构造是将EMPTY_ELEMENTDATA赋值给elementData。目前看来两个空数组的区别在于区分初始化这个对象时采用有参构造还是无参构造。

ArrayList的构造方法-有参构造（指定元素）

创建一个指定元素的集合
源码可以看到，使用toArray()先将参数转化为对象数组，
如果size不为0，则判断入参的数据类型是否为ArrayList，是 直接赋值，否则将c转化后的数组，大小以及类型赋值给elementData。
size为0 新建一个空的对象数组

实现方式如下

 public static void main(String[] args) {
        
        Collection<TestOne> testOneCollection =null;

        ArrayList<TestOne> testOnes = new ArrayList<>(testOneCollection);

    }

    class TestOne {
        public String getOne() {
            return "getOne";
        }

        public String getTwo() {
            return "getTwo";
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

ArrayList下的常用方法

ArrayList下的常用方法之add(E e);

add(E e); //添加一个元素，看看源码是如何解释这个方法。

注释说明将这个元素添加值当前集合末尾
那么添加元素，就会涉及到扩容的问题。我们都知道list是动态扩容的，那么他是怎么实现的呢？继续从源码进行解读

add方法 以下也是动态扩容的过程
一，首先调用ensureCapacityInternal，入参为当前集合+1(add方法只添加一个元素，即size必定为1)
也就是下图框选的方法，
二，调用calculateCapacity，如果当前集合为空，比较默认容量和当前集合需要的容量 并返回当前最大size
三，当前size大于默认最大容量时进行扩容 ，也就是 grow(int minCapacity)方法;grow(int minCapacity)，按照1.5倍扩容，如果不够则按照集合最大容量进行扩容，依然不够则最后按照Integer最大值进行扩容，使用的是Arrays.copyOf将容量设置给当前数组(当前集合转换的数组)。
四，elementData[size++] = e;最后将新元素赋值给当前集合（size+1）索引指向的对象。
如果当前集合容量等于默认容量时，进行扩容，新容量为当前集合容量的1.5倍，除了扩容我们看到还有两个判断，这主要是为了防止容量溢出的可能，
先判断扩充后的容量是否比当前集合添加新元素后的容量大，如果小于，则取当前新增元素后的容量为新集合的容量。
再判断 当前新集合容量是否比集合默认最大容量大，如果大于则取Intger的最大值作为新集合的容量。也就是2147483647,(2^32-1)

ArrayList下的常用方法之add(int index, E element);

添加元素到指定索引位置，如果当前指针有对应值将对应值以及后面所有值的指针向右移动。原理同add(E e)，其不同的地方是先将对应索引的位置及后面所有数据向当前索引-1顺延。再将索引指向新的元素。

    public static void main(String[] args) {

        ArrayList<String> arrayTempList = new ArrayList<String>();
        arrayTempList.add("first");
        arrayTempList.add("second");

        arrayTempList.add(1,"two");
		//将索引1指向two。当前指向元素向后顺延
        System.out.println(arrayTempList);

    }
1
2
3
4
5
6
7
8
9
10
11

返回：

源码解析：
一 进行索引检查，避免索引越界的可能。
二 进行扩容
三 使用 System.arraycopy(elementData, index, elementData, index + 1,
size - index);进行复制
四 将指定指针指向指定的元素。

// jdk源码
public void add(int index, E element) {
		//校验索引是否越界
        rangeCheckForAdd(index);

		//进行动态扩容，详情见add(E e);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        /**
		 * elementData 源数组
		 * index 从源数组当前位置
		 * elementData 目标数组
		 * index + 1
		 * size - index
		 */
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ArrayList下的常用方法之addAll(Collection<?> c);

其道理同上，
测试demo

public static void main(String[] args) {

        ArrayList<String> arrayTempList = new ArrayList<String>();
        arrayTempList.add("first");

        ArrayList<String> arrayAddList = new ArrayList<String>();
        arrayAddList.add("one");
        arrayAddList.add("two");
        arrayAddList.add("three");

        arrayTempList.addAll(arrayAddList);
        
        System.out.println(arrayTempList);
        
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查看源码如何实现添加一个集合
addAll(Collection<?> c) //添加一个集合 add(int index,Collection<?> c) //将集合c添加到指定下标index处。其索引对应及其后面的数据向后顺延，

动态扩容

动态扩容按1.5倍扩容，分为自动扩容和被动扩容
主要实现方法： grow(int minCapacity)方法;

线程安全

线程安全：在多个线程对一个集合进行操作时，会出现数据不同步的问题
首先为什么会出现不同步的问题，拿add举例

源码中我们看到赋值这一句代码，他实际操作时两步进行的，

	elementData[index] = element;
 	size++;
1
2

可能出现什么情况呢？在多线程条件下
其一：
列表为空 size = 0。
线程 A 执行完 elementData[size] = e;之后挂起。A 把 “a” 放在了下标为 0 的位置。此时 size = 0。
线程 B 执行 elementData[size] = e; 因为此时 size = 0，所以 B 把 “b” 放在了下标为 0 的位置，于是刚好把 A 的数据给覆盖掉了。
线程 B 将 size 的值增加为 1。
线程 A 将 size 的值增加为 2。
这样子，当线程 A 和线程 B 都执行完之后理想情况下应该是 “a” 在下标为 0 的位置，“b” 在标为 1 的位置。而实际情况确是下标为 0 的位置为 “b”，下标为 1 的位置啥也没有。

其二：
ArrayList 默认数组大小为 10。假设现在已经添加进去 9 个元素了，size = 9。

线程 A 执行完 add 函数中的ensureCapacityInternal(size + 1)挂起了。
线程 B 开始执行，校验数组容量发现不需要扩容。于是把 “b” 放在了下标为 9 的位置，且 size 自增 1。此时 size = 10。
线程 A 接着执行，尝试把 “a” 放在下标为 10 的位置，因为 size = 10。但因为数组还没有扩容，最大的下标才为 9，所以会抛出数组越界异常 ArrayIndexOutOfBoundsException

如何保证线程安全

第一种很容易想到的方法就是使用synchronized来同步所有的ArrayList操作方法，JDK工具类为我们提供了。Collections.synchronizedList()方法其实底层也是在集合的所有方法之上加上了synchronized（默认使用的是同一个monitor对象，也可以自己指定）。

在多线程环境下可以使用 Collections.synchronizedList() 或者 CopyOnWriteArrayList 来实现 ArrayList 的线程安全性。虽然 Vector（已废弃） 每个方法也都有同步关键字，但是一般不使用，一方面是慢，另一方面是不能保证多个方法的组合是线程安全的（因为不是基于同一个monitor）。