一、Collection接口下的集合关系图

Java 集合框架 Java Collection Framework ，又被称为容器 container ，是定义在 java.util 包下的一组接口 interfaces 和其实现类 classes 。

此图中，黄色方块为接口，深棕色方块为集合类，浅蓝色为抽象类。（此图只列出了Coolection接口与各个包装类、接口、抽象类的常用的关系，不全）

**集合是装对象的容器，其中有很多对 对象 的操作。**本编博客主要对集合类ArrayList与LinkList在Java源码中深度学习。归根结底，ArrayList与LinkList底层的数据结构分别是顺序表与链表。相信大家都已经不陌生了。

集合与数组的三大区别：
1.长度区别：集合长度可变，数组长度不可变

2.内容区别：集合可存储不同类型元素，数组存储只可单一类型元素

3.元素区别：集合只能存储引用类型元素，数组可存储引用类型，也可存储基本类型

二、包装类

Object 引用可以指向任意类型的对象，但有例外出现了，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要失效了？
实际上也确实如此，为了解决这个问题，java 引入了一类特殊的类，即这 8 种基本数据类型的包装类，在使用过程中，会将类似 int 这样的值包装到一个对象中去。

1.基本数据类型和包装类直接的对应关系

除了 Integer 和 Character比较特殊外，其余基本数据类型的包装类都是首字母变为大写即可。

2.包装类的装包（装箱）、拆包（拆箱）

基本数据类型转变为包装类为装箱，反之为拆箱。而装箱和拆箱又分为是否手动，否则为自动。例如下面的代码：

public static void main(String[] args) {
     int i = 10;
     Integer ii = i;//自动装箱
     int j = ii;//自动拆箱
}

我们进行反编译（javap -c 类名）时，结果发现其实编译时期将int基本数据类型转为Integer包装类调用了Integer包装类中的valueOf方法。而Integer类再转为int基本数据类型时又调用了Integer包装类的intValue方法。

手动装箱与拆箱只不过是将编译时编译器自己调用的方法程序员手动去调用。下面是手动装箱与拆箱的代码：

int i = 10; 

// 装箱操作，新建一个 Integer 类型对象，将 i 的值放入对象的某个属性中 Integer ii = Integer.valueOf(i);//手动装箱
Integer ij = new Integer(i); 

// 拆箱操作，将 Integer 对象中的值取出，放到一个基本数据类型中 
int j= ii.intValue()//手动拆箱

3.Integer包装类中特殊的valueOf方法

public static void main(String[] args) {
        Integer a = 128;
        Integer b = 128;
        System.out.println(a==b);
    }
    //打印结果为false

为什么打印结果为false呢？此处我们需要去看valueOf的源码。

而low和high分别被初始化为-128和127，因此if内的区间为-128到127。当满足if判断时，返回一个缓存的数组（cache为缓存的意思）。那么该缓存数组的长度为0到255，共256个数。该数就放在求出的数组下标的位置。例如i为2时，则放入的是数组下标为130的位置下。若不满足if语句的判断条件，则返回的是一个新的对象，返回新的对象时引用肯定不相同，则用==判断引用是否相同时返回值为false

三、Collection接口内部方法的使用

Collection是一个接口，因此它不能被实例化。可以用具体的实现类当作子类。我们可以点入Colection接口当中按中ctrl+7可以看到Colletcion里面的所有方法。此处只演示最基本和最重要的。
Collection接口无法做到调用自己接口当中没有的方法而去调用其它具体实现类当中的方法。并且调用Collection接口中的方法它的实现类必须要重写。

1.Collection常用方法说明

2.Collection接口当中需要注意的两个方法:toArray与toString

(1) toArray方法

此处比较费解的是最后一个toArray方法。点入Collection当中，可以看到toArray方法的返回值为Object[] 类型。因此要用Object[] 来接收。但是此时可能有人会将数组强制类型转换为其它类型数组。
ArrayList当中的toArray方法：

并且elementData是Object[]类型的。

例：

Collection<Integer> collection = new ArrayList<>();
collection.add(1);
collection.add(2);
collection.add(3);
String[] objects = (String[])collection.toArray();

此时我们发现编译器不会对其进行报错，是因为数组是在运行的时候存储和检查数类型信息的。但是我们运行时会发现报错了。

原因是此时的强制类型转换只是将数组的类型转换，数组当中的元素实际上还是Object[]类型。正是Object类型是一切类型的父类，所以强转为String类型是不可行的，但是其它类型转换为Object类型是行得通的。

(2) toString方法

到现在我们都知道每个类当中都有toString方法。但是Collection接口实现子类ArrayList类中并没有实际的toString方法。
例：

Collection<Integer> collection = new ArrayList<>();
collection.add(1);
collection.add(2);
collection.add(3);
System.out.println(collection);
//打印结果
[1, 2, 3]

此时我们在ArrayList类当中没有看到toString方法，但是它继承了AbstractList类。

但AbstractList类当中还是没有toString方法，但它继承了AbstractCollection类。

此时在AbstractCollection类当中找到了toString方法。

如果没有具体的toString实现方法，它打印的就是集合当中每个元素的地址；有toString方法但是不是简单的就是Collection接口实现的类当中，此时需要去找到它继承的父类有没有toString方法。

四、ArrayList

1.ArrayList简介

观察图中的ArrayList与各个接口、抽象类的关系中，我们可以得到下面几个结论：
1.ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2.ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3.ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4.和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5.ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

2.ArrayList的使用

2.1 ArrayList的构造方法

public static void main(String[] args) { 
// ArrayList创建，推荐写法 
// 构造一个空的列表 
List<Integer> list1 = new ArrayList<>(); 

// 构造一个具有10个容量的列表 
List<Integer> list2 = new ArrayList<>(10); 
list2.add(1);
list2.add(2); 
list2.add(3); 
// list2.add("hello"); // 编译失败，List<Integer>已经限定了，list2中只能存储整形元素 

// list3构造好之后，与list中的元素一致 
ArrayList<Integer> list3 = new ArrayList<>(list2);

注意：不能List<Integer> list1 = new List<>();因为List是一个接口不能实例化。

带参数的构造方法源码：

2.2 ArrayList常见操作

此处需要特别注意的是remove方法。当我们一边进行遍历一边又要进行删除时，需要用到的是需要使用next方法迭代出集合中的元素 ，然后才能调用remove方法
例如：

ArrayList<String> list2 = new ArrayList<>();
list2.add("hello");
list2.add("bit");
list2.add("haha");
System.out.println("========迭代器List相关打印==========");
ListIterator<String> it2 = list2.listIterator();
while (it2.hasNext()) {
    String ret = it2.next();
    if(ret.equals("hello")) {
       it2.remove();//首先需要使用next方法迭代出集合中的元素 ，然后才能调用remove方法
    }else {
        System.out.print(ret + " ");
     }
}
//打印结果为 bit haha

我们知道在ArrayList的add方法中，它是添加到顺序表的最后一位的。

ArrayList<String> list2 = new ArrayList<>();
list2.add("hello");
list2.add("bit");
list2.add("haha");
System.out.println(list2);
//打印结果：
[hello, bit, haha]

add(int index, E element) 的方法也是一个一个向后挪动元素的。arraycopy就是挪动元素的过程。

而addAll方法是将添加的另一个顺序表的元素到该顺序表的末尾处。如：

ArrayList<String> list2 = new ArrayList<>();
list2.add("a");
list2.add("c");
ArrayList<String> list3 = new ArrayList<>();
list3.add("我是测试List1");
list3.add("我是测试List2");
list3.add("我是测试List3");
list2.addAll(list3);
System.out.println(list2);
//打印结果：
[a, c, 我是测试List1, 我是测试List2, 我是测试List3]

2.3 ArrayList的遍历

第一种：获取下标进行遍历

List<String> list1 = new ArrayList<>();//长度为0
list1.add("hello");
list1.add("world");
List<String> list3 = new ArrayList<>(list1);//在其它顺序表的基础上初始化
for (int i = 0; i < list3.size(); i++) {
     System.out.print(list3.get(i)+" ");
}

第二种：用foreach进行遍历

List<String> list1 = new ArrayList<>();//长度为0
list1.add("hello");
list1.add("world");
List<String> list3 = new ArrayList<>(list1);//在其它顺序表的基础上初始化
for (String s:list3) {
    System.out.print(s+" ");
}

第三种：用迭代器进行遍历

List<String> list1 = new ArrayList<>();//长度为0
list1.add("hello");
list1.add("world");
List<String> list3 = new ArrayList<>(list1);//在其它顺序表的基础上初始化
Iterator<String> it1 = list3.iterator();
while(it1.hasNext()) {
     System.out.print(it1.next()+" ");
}

第四种：用迭代器List相关打印

List<String> list1 = new ArrayList<>();//长度为0
list1.add("hello");
list1.add("world");
List<String> list3 = new ArrayList<>(list1);//在其它顺序表的基础上初始化
ListIterator<String> it2 = list3.listIterator();
while(it2.hasNext()) {
      System.out.print(it2.next()+" ");
}
System.out.println();

2.4 迭代器ListIterator的ArrayList中add的关系

用迭代器ListIterator也可以一边遍历一边添加元素（此处用ListIterator而不用Iterator原因是Iterator中没有抽象出add方法）。需要注意的是我们要用的是迭代器来添加元素，而不是ArrayList中的add。例如：

ArrayList<String> list2 = new ArrayList<>();
list2.add("hello");
list2.add("bit");
list2.add("haha");
ListIterator<String> it2 = list2.listIterator();
while (it2.hasNext()) {
     String ret = it2.next();
     if(ret.equals("bit")) {
          it2.add("zjr");
     }else {
         System.out.print(ret + " ");
      }
}
    System.out.println();
    System.out.println("======");
    System.out.println(list2);
//打印结果：
hello haha 
======
[hello, bit, zjr, haha]

如果用ArrayList中的add，则程序会报错（将it2.add("zjr");改为list2.add("zjr");）。

此时需要把ArrayList改为CopyOnWriteArrayList。
因为ArrayList是单线程的，CopyOnWriteArrayList是多线程的。

CopyOnWriteArrayList<String> list2 = new CopyOnWriteArrayList<>();//此处改变
list2.add("hello");
list2.add("bit");
list2.add("haha");
ListIterator<String> it2 = list2.listIterator();
while (it2.hasNext()) {
     String ret = it2.next();
     if(ret.equals("bit")) {
          list2.add("zjr");//此处改变
     }else {
         System.out.print(ret + " ");
      }
}
    System.out.println();
    System.out.println("======");
    System.out.println(list2);
//打印结果：
hello haha 
======
[hello, bit, zjr, haha]

3.ArrayList的扩容机制

学到这里，我们都已经知道ArrayList<String> list2 = new ArrayList<>();初始化的空间大小为0，那为什么还能够添加元素呢？要弄清楚这个原因，我们需要去看add的源码是如何去扩容的，它的底层逻辑又是什么。

参数为空的构造方法：

而赋给elementData的值又是一个空的对象。

此时我们点入add方法当中：

因为ArrayList为空，则size为0，因为要调用ensureCapacityInternal方法，则再点进去，minCapacity为1：

此处又调用了calculateCapacity方法，点进去：

此时我们发现，之前如果是第一次add，则满足if语句的判断条件。返回10与1的最大值，明显为10。

此时又回去调用ensureExplicitCapacity方法，minCapacity为10。
modCount为记录修改顺序表的次数。此时minCapacity为10，会进入if语句当中。

调用grow方法。

如果是第一次扩容，因为elementData的长度为0，因此oldCapacity不会扩容，0-10为负数，进入到第一个if语句当中。newCapacity被赋值为10。最后Arrays.copyOf就是扩容的方法。如果不是第一次扩容，则会根据原来顺序表的长度进行1.5倍扩容，用>>运算符是除2的意思，比/效率更高。

当然，如果需要扩容的顺序表的长度非常大，大于int的最大值-8，则调用hugeCapacity。

最终真正地实现了扩容。
总结：
1.检测是否真正需要扩容，如果是调用grow准备扩容
2.预估需要扩容的大小
不是第一次预估按照1.5倍大小扩容，第一次只扩容10。
如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容
真正扩容之前检测是否能扩容成功，防止太大导致扩容失败
3. 使用copyOf进行扩容