开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 集合Collection接口与ArrayList与及其背后的数据结构 -> 正文阅读

[数据结构与算法]集合Collection接口与ArrayList与及其背后的数据结构

一、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.基本数据类型和包装类直接的对应关系

基本数据类型	包装类
byte	Byte
short	Short
int	Integer
long	Long
float	Float
double	Double
char	Character
boolean

除了 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常用方法说明

方法签名	说明
boolean add(E e)	将元素 e 放入集合中
void clear()	删除集合中的所有元素
boolean isEmpty()	判断集合是否没有任何元素，俗称空集合
boolean remove(Object e)	如果元素 e 出现在集合中，删除其中一个
int size()	返回集合中的元素个数
Object[] toArray()	将集合中的元素以数组的形式返回

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的构造方法

方法	解释
ArrayList()	无参构造,不初始化大小,但调用add方法时会初始化大小为10
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

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常见操作

方法	说明
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个o的下标
List subList(int fromIndex, int toIndex)	截取部分list

此处需要特别注意的是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进行扩容