05集合-Collection&List&Set

Collection体系的特点、使用场景总结

如果希望元素可以重复，又有索引，索引查询要快?

• 用ArrayList集合, 基于数组的。(用的最多)

如果希望元素可以重复，又有索引，增删首尾操作快?

• 用LinkedList集合, 基于链表的。

如果希望增删改查都快，但是元素不重复、无序、无索引。

• 用HashSet集合,于哈希表的。

如果希望增删改查都快，但是元素不重复、有序、无索引。

• 用LinkedHashSet集合, 于哈希表和双链表。

如果要对对象进行排序。

• 用TreeSet集合, 基于红黑树。后续也可以用List集合实现排序。

数组的特点

• 数组定义完成并启动后，类型确定、长度固定。

• 不适合元素的个数和类型不确定的业务场景，更不适合做需要增删数据操作。

• 数组的功能也比较的单一，处理数据的能力并不是很强大。

集合的特点

• 集合的大小不固定，启动后可以动态变化，类型也可以选择不固定。集合更像气球。
• 集合非常适合元素个数不能确定，且需要做元素的增删操作的场景。
• 同时，集合提供的种类特别的丰富，功能也是非常强大的，开发中集合用的更多。

1、数组和集合的元素存储的个数问题。

• 数组定义后类型确定，长度固定
• 集合类型可以不固定，大小是可变的。

2、数组和集合存储元素的类型问题。

• 数组可以存储基本类型和引用类型的数据。
• 集合只能存储引用数据类型的数据。

3、数组和集合适合的场景

• 数组适合做数据个数和类型确定的场景。
• 集合适合做数据个数不确定，且要做增删元素的场景，集合种类更多，功能更强大。

集合

集合的体系特点

• Collection代表单列集合，每个元素（数据）只包含一个值。
• Map代表双列集合，每个元素包含两个值（键值对）。
• 集合中存储的是元素的什么信息?
  • 集合中存储的是元素对象的地址。

集合体系结构

Collection集合体系

Collection集合的特点

• List系列集合：有序、可重复 有索引
  • ArrayList、LinekdList: 有序、可重复 有索引
• Set系列集合：无序、不重复 无索引
  • HashSet: 无序、不重复、无索引
  • LinkedHashSet: 有序、不重复、无索引
  • TreeSet：按照大小默认升序排序、不重复、无索引。

Collection的常用方法

1、集合的代表是？

• Collection接口。

2、Collection集合分了哪2大常用的集合体系？

• List系列集合：添加的元素是有序、可重复、有索引。
• Set系列集合：添加的元素是无序、不重复、无索引。

3、如何约定集合存储数据的类型，需要注意什么？

• 集合支持泛型。
• 集合和泛型不支持基本类型，只支持引用数据类型。

为啥要先学Collection的常用方法？

Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

Collection的常见方法如下:

Collection的遍历方式

迭代器

迭代器是用来遍历集合的专用方式(数组没有迭代器)，在Java中迭代器的代表是Iterator。

Collection集合获取迭代器的方法

Iterator迭代器中的常用方法

Iterator<String> it = lists.iterator();
while(it.hasNext()){
    String ele = it.next();
    System.out.println(ele);
}

1、迭代器的默认位置在哪里。
Iterator<E> iterator()：得到迭代器对象，默认指向当前集合的索引0
2、迭代器如果取元素越界会出现什么问题。
会出现NoSuchElementException异常。
1
2
3
4
5
6
7
8
9
10

增强for循环

1、增强for可以遍历哪些容器？

• 既可以遍历集合也可以遍历数组。

2、增强for的关键是记住它的遍历格式

for(元素数据类型 变量名 : 数组或者Collection集合) { //在此处使用变量即可，该变量就是元素 }
    
Collection<String> c = new ArrayList<>();  ...
for(String s : c) {
    System.out.println(s);
}
增强for可以用来遍历集合或者数组。
增强for遍历集合，本质就是迭代器遍历集合的简化写法。
1
2
3
4
5
6
7
8

Lambda表达式遍历集合

Lambda表达式，提供了一种更简单、更直接的方式来遍历集合。

需要使用Collection的如下方法来完成

Collection<String> lists = new ArrayList<>(); ...
lists.forEach(new Consumer<String>() {
    @Override
    public void accept(String s) {
        System.out.println(s);
    }
});
转为
lists.forEach(s -> {
    System.out.println(s);
});
//  lists.forEach(s -> System.out.println(s));

1
2
3
4
5
6
7
8
9
10
11
12
13

集合存储对象的原理

集合的并发修改异常问题

问题引出

• 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。
• 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误

怎么保证遍历集合同时删除数据时不出bug？

• 使用迭代器遍历集合：但用迭代器自己的删除方法删除数据即可。
• 使用增强for循环遍历集合：无法解决这个问题
• 使用普通for循环遍历集合：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做i --操作。

List集合

有序，可重复，有索引。

List特有方法

collection集合体系

List集合特有方法

• List集合因为支持索引，所以多了很多索引操作的独特api，其他Collection的功能List也都继承了。

List集合的遍历方式有几种？

• 迭代器
• 增强for循环
• Lambda表达式
• for循环（因为List集合存在索引）

ArrayList集合的底层原理

• ArrayList底层是基于数组实现的
  • 查询速度快(注意: 是根据索引查询数据快): 查询数据通过地址值和索引定位，查询任意数据耗时相同。
  • 删除效率低：可能需要把后面很多的数据进行前移。
  • 添加效率极低：可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容。

1. 利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组

2. 添加第一个元素时，底层会创建一个新的长度为10的数组

   List list1 = new ArrayList<>();list1.add("a");

3. 存满时，会扩容1.5倍

4. 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准

应用场景

• ArrayList适合:
• 根据索引查询数据, 比如根据随机索引取数据(高效)! 或者数据量不是很大时
• ArrayList不适合:
  • 数据量大的同时, 又要频繁进行增删操作

List集合的遍历方式有几种？

• 迭代器
• 增强for循环
• Lambda表达式
• for循环（因为List集合存在索引）

LinkedList集合底层原理

基于双链表实现的

查询慢，增删相对较快，但对首尾元素进行增删改查的速度是极快的。

什么是链表? 有啥特点?

• 链表中的结点是独立的对象，在内存中是不连续的，每个结点包含数据值和下一个结点的地址。

特点:

• 链表的特点1：查询慢，无论查询哪个数据都要从头开始找。
• 链表的特点2：增删首尾元素是非常快的

LinkedList集合的特有功能

应用场景

• 可以用来设计队列

  • 先进先出, 后进后出

• 可以用来设计栈

  • 后进先出,先进后出

Set集合

介绍

Collection集合体系

Set系列集合特点： 无序; 不可重复

• 无序:存取顺序不一致
• 不重复:可以去除重复
• 无索引: 没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索弓l来获取元素。

• HashSet:无序、 不重复、无索引.

• LinkedHashSet: 有序、不重复、无索引。

• TreeSet: 排序、不重复、无索引。

• 注意：

  • Set要用到的常用方法，基本上就是Collection提供的！！
  • 自己几乎没有额外新增一些常用功能！

HashSet

Hash值

注意：在正式了解HashSet集合的底层原理前，我们需要先搞清楚一个前置知识：哈希值！

• 就是一个int类型的数值，Java中每个对象都有一个哈希值。
• Java中的所有对象，都可以调用Obejct类提供的hashCode方法，返回该对象自己的哈希值。

public int hashCode()：返回对象的哈希码值。

对象哈希值的特点

• 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
• 不同的对象，它们的哈希值一般不相同，但也有可能会相同(哈希碰撞)。
• Object的hashCode方法根据"对象地址值"计算哈希值子类重写后的hashCode方法可以根据"对象属性值"计算哈希值

HashSet集合判定两个对象的标准就是两个对象的hash值是否一致, 因此我们经常重写hashcode实现集合中对象去重

• 如果希望Set集合认为2个内容相同的对象是重复的应该怎么办？
• 重写对象的hashCode和equals方法。

底层原理

• HashSet集合底层采取哈希表存储的数据。
• 哈希表是一种对于增删改查数据性能都较好的结构。

哈希表的组成

• JDK8之前的, 底层使用数组+链表组成
• JDK8开始后，底层采用数组+链表+红黑树组成。

在了解哈希表之前需要先理解哈希值的概念

哈希值

• 是JDK根据对象的地址， 按照某种规则算出来的int类型的数值。

Object类的API

• public int hashCode0:返回对象的哈希值

对象的哈希值特点

• 同一个对象多次调用hashCode0方法返回的哈希值是相同的
• 默认情况下，不同对象的哈希值是不同的。

哈希表的详细流程

• 创建一个默认长度16，默认加载因为0.75的数组，数组名table
• 根据元素的哈希值跟数组的长度计算出应存入的位置
• 判断当前位置是否为null，如果是null直接存入，如果位置不为null，表示有元素， 则调用equals方法比较属性值，如果一样，则不存，如果不一样，则存入数组。
• 当数组存满到16*0.75=12时，就自动扩容，每次扩容原先的两倍

JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树

树结构(了解)

了解数据结构

(树)

• 二叉树存在的问题:

  • 当数据已经是排好序的，导致查询的性能与单链表一样，查询速度变慢！

• 平衡二叉树

  • 在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能。

红黑树，就是可以自平衡的二叉树

• 红黑树是一种增删改查数据性能相对都较好的结构。
• 左右子树高度差大于 1 便会调整

/*
HashSet集合的底层原理
    JDK8之前: 数组+链表
    JDK8开始: 数组+链表+红黑树

树结构
    二叉树: 基本模型
        每一个根节点最多只能有两个子节点，子节点数量称为度，树的总层数为树高
        左子节点
        右子节点
        左子树
        右子树

    二叉查找/二又搜索树: BST (Binary Search  Tree)
        小的存左边，大的存右边，相同则不存
        如果数据已经排好序，那么存入二又树查找树，会形成类似链表结构，查询效率还是低
        如果左、右子树的树高差比较大，那么导致左右子树不平衡，影响查询效率

    平衡二叉树: AVL (Balanced  Binary Tree)
        有规律且相对平衡的二叉树
        当插入一个元素，导致左右子树的树高差大于1。那么就会触发旋转
        旋转分为左旋和右旋，用来保证左右子树的相对平衡

    红黑: RBT (Red-Black  Tree)
        特殊的/自平衡的二又查找树，是计算机科学中用到的一种数据结构
        1972年出现时被称为平衡二叉树，后来1978年被修改为如今的红黑树
        红黑树不是高度平衡的，有自己保证平衡的规则(红黑规则)，性能较好，红黑规则如下:
            每一个节点都是红色或者黑色的
            根节点必须是黑色的
            两个红色节点不能相连
            如果一个节点没有子节点，则该节点相应的指针属性为Nil (称为叶子结点)，叶子结点是黑色的
            对于每一个节点，到其所有后代叶节点的简单路径上，包含的黑色 节点数量相同
*/
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

手撕平衡二叉树

手撕红黑树

总结

JDK8开始，当链表长度超过8，且数组长度>=64时，自动将链表转成红黑树

HashSet集合的底层原理是什么样的?

• 结构: 数组 + 链表 8-
  数组 + 链表 + 红黑树 8+

• 数组初始16,加载因子0.75, 新数组是原来老数组的2倍

• 对元素进行HashCode % 16[0~15]

• 如果索引对应的值是null, 先equal比较, 如果一样不存储,
  如果不一样, 8- 存储新的, 老的挂载新的下面 8+ 新的挂载到老的下面

• 扩容: 加载因子计算什么时候开始扩容 16 * 0.75= 12
  创建新的数组, 长度是原来的两倍, 重新计算索引放入新的数组中

• 基于哈希表实现的。

• JDK8之前的，哈希表：底层使用数组+链表组成

• JDK8开始后，哈希表：底层采用数组+链表+红黑树组成。

HashSet集合利用哈希表操作数据的详细流程是咋回事？

• 创建一个默认长度16，默认加载因为0.75的数组，数组名table
• 根据元素的哈希值跟数组的长度计算出应存入的位置
• 判断当前位置是否为null，如果是null直接存入，如果位置不为null，表示有元素，
• 则调用equals方法比较属性值，如果一样，则不存，如果不一样，则存入数组.
• 当数组存满到16*0.75=12时，就自动扩容，每次扩容原先的两倍

LinkedHashSet

底层原理

• LinkedHashSet是不可重复的,存取有序的,底层是基于哈希表**(数组、链表、红黑树)**实现的。
• 但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

TreeSet

• 特点：不重复、无索引、可排序（默认升序排序 ，按照元素的大小，由小到大排序）
• 底层是基于红黑树实现的排序。

注意:

• 对于数值类型：Integer , Double，默认按照数值本身的大小进行升序排序。
• 对于字符串类型：默认按照首字符的编号升序排序。
• 对于自定义类型如Teacher对象，TreeSet默认是无法直接排序的。

自定义排序规则

• TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。

方式一:自然排序

• 让自定义的类（如教师类）实现Comparable接口，重写里面的compareTo方法来指定比较规则。

方式二:比较器排序

• 通过调用TreeSet集合有参数构造器，可以设置Comparator对象（比较器对象，用于指定比较规则)。

public TreeSet(Comparator<? super E> comparator)

1
2

总结

• TreeSet集合的特点是怎么样的？

  • 可排序、不重复
  • 底层基于红黑树实现排序，增删改查性能较好

• TreeSet集合对自定义类型的对象排序，有几种方式指定比较规则？

  • 2种
  • 类实现Comparable接口，重写比较规则。
  • 集合自定义Comparator比较器对象，重写比较规则。

Collection集合特点

• List系列集合：有序，可重复
• ArrayList、LinekdList
• Set系列集合：无序，不可重复
• HashSet:
• LinkedHashSet: 有序、不重复、无索引(底层基于哈希表，使用双链表记录添加顺序。)
• TreeSet：可排序、不重复、无索引(底层基于红黑树实现排序，增删改查性能较好)

1、如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？

• 用ArrayList集合（有序、可重复、有索引），底层基于数组的。（常用）

2、如果希望记住元素的添加顺序，且增删首尾数据的情况较多？

• 用LinkedList集合（有序、可重复、有索引），底层基于双链表实现的。

3、如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？

• 用HashSet集合（无序，不重复，无索引），底层基于哈希表实现的。 （常用）

4、如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快？

• 用LinkedHashSet集合（有序，不重复，无索引）， 底层基于哈希表和双链表。

5、如果要对元素进行排序，也没有重复元素需要存储？且希望增删改查都快？

• 用TreeSet集合，基于红黑树实现。