【重拾Java系列】—— 集合之Collection

一、集合体系框架

⭐️概述：集合可以动态的存放多个对象，提供了一系列操作方法，主要由Collection和Map两类组成【单列集合、双列集合】

💥Collection Diagrams图：

单列集合Collection有两个实现接口： List 和 Set
List接口的主要实现类有：ArrayList、LinkedList、Vector
Set接口的主要实现类有：HashSet、TreeSet

💥 Map Diagrams图：

双列集合 Map 主要有三个实现子类：HashMap、Hashtable、TreeMap
LinkedHashMap 继承了 HashMap
Properties 继承了 Hashtable

二、Collection接口的常用方法

⭐️概述： 因为接口不能实例化，所以此处以ArrayList实现Collection接口为例【Collection为编译类型，ArrayList为运行类型】

特别说明：

当remove方法的参数为索引时，返回结果为删除的元素 【编译类型为ArrayList时】
当remove方法的参数为元素时，返回结果为是否成功删除【编译类型为Collection 或 ArrayList时】

举例说明这些常用方法的应用：

Collection list = new ArrayList();
//添加元素【因为没有指明泛型，所以为Object的子类型均可】
list.add(99);
list.add("love");
list.add(true);
//删除元素
System.out.println(list.remove(0));
System.out.println(list.remove(true));
//是否包含指定元素
System.out.println(list.contains("love"));
//元素个数
System.out.println(list.size());
//是否为空
System.out.println(list.isEmpty());
//清除
list.clear();
System.out.println("*******");
//添加多个
ArrayList arrayList = new ArrayList();
arrayList.add("Yang");
arrayList.add("Zhao");
list.addAll(arrayList);
list.remove("Yang");
//包含多个
System.out.println(list.containsAll(arrayList));
//删除多个
System.out.println(list.removeAll(arrayList));
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

运行结果如下：

三、利用迭代器遍历集合

⭐️概述： 我们可以发现Collection集合实现了 Iterable 接口，该接口中有一个 Iterator 接口类型的方法 iterator， 所以后面实现Collection集合的所有类都会实现该方法【迭代器】

迭代器【Iterator】接口有四个方法：【方法二、三比较常用】

集合中迭代器的作用就是用来遍历集合的，那么还是以ArrayList为例来演示迭代器的用法

public class Collection_ {
    @SuppressWarnings({"all"})
    public static void main(String[] args) {
        //创建集合
        Collection list = new ArrayList();
        //添加元素
        list.add("tomorrow");
        list.add("is");
        list.add("more");
        list.add("lovely");
        //创建迭代器
        Iterator iterator = list.iterator();
        //遍历迭代器
        while (iterator.hasNext()) {
            Object next =  iterator.next();
            System.out.println(next);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

一般情况下不会用 Collection 作为编译类型，顶多使用接口实现类的直系接口【List】
而且集合没有使用泛型，所以会给出警告，这里面利用 SuppressWarnings 来抑制警告

• 也可以利用增强for循环来遍历集合：
  增强for循环的底层就是由迭代器实现的，可以理解为简化的迭代器

for(元素类型 变量名: 数组/集合){
	利用该变量遍历集合中的所有元素;
}
1
2
3

四、List接口的常用方法

⭐️概述： List 接口是 Collection 接口的子接口，该集合类中元素是有序的，可以存放重复元素【支持索引、可根据存取顺序的序号获得元素】

（1）有序性【输入顺序和存取顺序相同】

public class List_ {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("program");
        list.add("is");
        list.add("art");
        System.out.println(list);
    }
}
1
2
3
4
5
6
7
8
9

（2）可搜索【List 集合中的每一个元素都有其对应的索引】

list.get(0);
1

（3）常用方法【以 ArrayList 类演示】

• add、addAll 方法，默认情况下在集合的末尾添加元素，也可以在指定位置添加【指定索引处】

list.add("one");
System.out.println(list);
list.add(0, "two");
System.out.println(list);
1
2
3
4

addAll 添加的是集合，与之同理

• get、set、remove方法，根据指定的索引获取元素、修改元素、删除元素【后两者返回的是被修改、被删除的元素】

System.out.println("索引0位置的元素: " + list.get(0));
System.out.println("set方法修改的元素: " + list.set(0, "today"));
System.out.println("修改后的list集合: " + list);
System.out.println("remove方法删除的元素: " + list.remove(0));
System.out.println("删除后的list集合: " + list);
1
2
3
4
5

• indexOf、lastOf 方法，获取指定元素第一次和最后一次出现的位置

System.out.println("one第一次出现的位置: " + list.indexOf("one"));
System.out.println("one最后一次出现的位置: " + list.lastIndexOf("one"));
1
2

• subList 方法，返回指定集合从 fromIndex 到 toIndex 的子集合【前闭后开】

List list1 = list.subList(0,2);
System.out.println(list1);
1
2

33

五、ArrayList底层分析

• ArrayList 可以存储空【null】，底层是数组实现的
• ArrayList 的方法没有被 synchronized修饰，所以是线程不安全的【不推荐用于多线程，但速度会更快一点】
• 对于通过传入指定整型参数构造的ArrayList的对象，初始大小为零，需要扩容时，每次扩容元集合大小的1.5倍
• 对于通过无参构造器生成的ArrayList的对象，初始大小为输入的参数，需要扩容时，第一次扩容为10，之后每次需要扩容时，则扩容元集合大小的1.5倍

（1）ArrayList 底层维护一个 Object 类型的数组 element 来存储元素

（2）添加的元素如果为整型数，那么会先自动装箱转化为 Integer

（3）在添加元素前，要去判断是否需要扩容

此处的 size 是 ArrayList 类的一个私有属性，自动初始化为零，此处参数的含义代表 集合的空间最小值

（4）需要进入该方法去判断最小空间应该为多少【当空间小于十，那么就将最小空间定义为10】

这个 DEFAULT_CAPACITY 就是一个静态常量 10

（5）进入该ensureExplicitCapacity 方法，通过当前最小空间与集合实际的大小比较，判断是否真的需要扩容

（6）满足扩容条件就会进入 grow 方法，来确定扩容后的大小

• 获取此时的集合大小，将新集合的大小更新为原集合大小的 1.5 倍
• 如果新集合的大小比传入的最小空间还小，那么新集和的大小就为这个最小空间。
• 再判断集合大小是不是超过最大范围
• 最后通过 copyOf 方法来完成扩容【newCapacity 就是集合扩容后的大小】

六、Vector底层结构分析

⭐️概述： Vector 底层也是一个对象数组，不过它是线程安全的

• 其扩容机制与 ArrayList 类似，无参构造初始大小为10，之后每次翻一倍；
• 有参构造初始大小为参数，之后每次翻一倍

（1）利用无参构造器创建对象时

创建的是空间大小为 10 的 protected Object [] elementData

（2）当添加元素时，也会判断是否需要扩容

不过此时比较的是集合元素的个数与集合实际的空间

（3）当空间不足时，调用 grow 方法

这个capacityIncrement 初始化为零，所以就相当于 预设新空间为原来的二倍

新空间不比元素个数小，也没超范围，就利用 copyOf 方法对原数组扩容

七、LinkedList底层分析

⭐️概述：LinkedList 底层实现了双端队列和双端链表，可以添加任意元素（包含空），允许元素出现重复，没有实现线程同步（线程不安全）

• LinkedList 底层维护了一个双向链表，链表有两个属性 first 和 last，分别指向首结点和尾结点

• 链表由节点组成，每个结点有三个属性 next、prev、item，分别代表指向后一个节点、指向前一个结点、结点的元素值

LinkedList 添加元素

（1）利用无参构造器创建对象，初始first、last都为空

（2）添加元素时，调用LinkLast方法

（3）linkLast实现在链表的末尾添加元素

• 以当前元素与原链表的尾结点创建一个新的结点，并将这个新的结点作为尾结点。

• 判断尾结点是否为空，如果为空说明之前为空链表，当前结点也是链表的首结点；如果不为空，将原尾结点的后继指针指向当前结点

• size 代表链表中结点的个数，modCount代表操作次数

添加成功，返回true

LinkedList删除元素

（1）默认情况下调用removeFirst方法，删除首结点

（2）判断是否为空链表，如果为空就抛出异常，否则调用unlinkFirst方法

（3）因为要返回删除结点的元素，所以它保存了节点的值与当前结点的后继指针

将当前结点置空，首结点改为这个后继，判断后继是否为空，如果为空说明原链表只有这一个结点，接着把尾结点也置空；如果不为空就将这个后继的前驱置空

八、HashSet底层分析

⭐️概述：Set 接口中的元素是无序的，添加元素和取出元素的顺序不一致。不允许存在重复元素，所以最多只能存储一个null。

• 因为Set接口是Collection的子接口，所以也有Collection的常用方法

• 可以使用增强for循环和迭代器来遍历

• 取出元素的顺序不会改变

1.不能添加重复元素

（1）只能存储一个null

//添加重复元素 1.0
boolean res1 = set.add(null);
boolean res2 = set.add(null);
System.out.println(res1 + " / " + res2);
System.out.println(set);
1
2
3
4
5

（2）可以添加元素值相同的不同对象

//添加重复元素 2.0
boolean res1 = set.add(new Person("XiaoMing"));
boolean res2 = set.add(new Person("XiaoMing"));
System.out.println(res1 + " / " + res2);
System.out.println(set);
1
2
3
4
5

如果我们把名字相同就认为是一个人，不想重复添加一个人的信息，可以通过重写equals方法和hashCode方法，指定根据name是否相同来判断是否是一个人即可。

（3）String 类尽管是不同的对象，但内容相同也会添加失败

//添加重复元素 3.0
boolean res1 = set.add(new String("XiaoMing"));
boolean res2 = set.add(new String("XiaoMing"));
System.out.println(res1 + " / " + res2);
System.out.println(set);
1
2
3
4
5

原因是这样的：
String类重写了hashCode 和 equals 方法，equals 方法判断的就是两个字符串的内容是否相同，也就导致了HashSet添加不同对象但字符串内容相同的字符串时，只能添加一个进去

2.扩容机制【通过添加元素来查看】

（1）利用无参构造器创建了一个HashMap的对象【HashSet的底层是由HashMap实现的】

（2）进入add方法，返回的是哈希表的put方法

PRESENT 是 HashSet的一个静态常量，始终都为空

（3）进入put方法，此时的key就是我们传入的参数，value始终为null

putVal方法中的hash方法，就是根据哈希编码来确定哈希地址的

（4）进入putVal方法

创建表，如果当前哈希表为空或者长度为零，那么就去利用resize方法扩容

因为resize方法太长，所以此处一段一段进行分析：

获取原来的表，并记录原表的大小和预处理的大小，再设置两个变量记录新表的大小和预处理的大小

直接来到匹配的这项，新空间为16，预处理空间为12【设置预处理空间是为了表中元素达到预处理空间大小就要进行扩容】

创建新表并返回这个新的表
扩容结束后，根据的大小和hash确定存储位置，如果该位置为空就将创建的结点添加进去

至此，空表添加第一个元素的过程就结束了。

总而言之，可以简化为一下几个步骤:

先得到哈希值，再根据哈希值得到索引值
找到存储数据表 table ，检查这个索引位置是否已经存放元素了
如果没有，将当前元素添加到该位置
如果有，调用 equals 比较，如果相同则不添加，如果不同则添加到末尾 【equals 方法是程序员指定的】
从java8开始，如果表的结点个数达到64个，每个链表的结点达到8个，那么就会转化成红黑树

九、LinkedHashSet分析

⭐️概述：LinkedHashSet 是 HashSet 的子类，底层是一个LinkedHashMap【数组 + 双向链表】实现的。

• 不能添加重复元素，但是元素的存取是有序的
• 根据元素的HashCode确定存储位置
  

从图中可以看出，LinkedHashSet 维护了一个 hash表和双向链表

链表的每个结点有两个属性，pre 和 next 属性，添加一个元素后，将存储该元素结点的前驱指针指向前一个结点，后继暂时指向后，直至存储下一个结点【有序】

通过hashCode确定储存位置，如果已经存在并且通过equals方法比较是同一个对象，那么就不添加。