【Java基础】023 -- 集合进阶（List、Set、泛型、树）

目录

一、集合的体系结构

1、单列集合（Collection）

二、Collection集合

1、Collection常见方法

①、代码实现：

②、contains方法重写equals方法示例：（idea可自动重写）

2、Collection的遍历方式（3种）

①、迭代器遍历

②、增强for遍历

③、Lambda表达式遍历

3、小结

三、List集合

1、List集合特有的方法（操作索引的4个方法）

2、List集合的遍历方式（5种）

①、示例代码

②、小结

四、数据结构（常见有8种）

1、什么是数据结构呢？

2、数据结构概述

3、栈（后进先出，先进后出）

4、队列（先进先出，后进后出）

5、栈与队列小结

6、数组

7、链表（与数组相对）

小结

五、ArrayList集合

1、ArrayList集合底层原理

2、ArrayList源码分析

六、LinkedList集合

1、LinkedList特有方法

2、LinkedList源码分析

3、迭代器的底层源码

七、泛型深入

1、没有泛型时的集合如何存储数据？

2、泛型的好处

3、知识点：Java中的泛型是伪泛型

4、泛型的细节

5、泛型可以在很多地方进行定义

①、泛型类

②、泛型方法

③、泛型接口

6、泛型的继承和通配符

①、泛型的继承示例代码

②、泛型的通配符练习

7、小结

八、树（Tree）

1、集合起名的艺术

2、树的基本结构

3、二叉树

4、二叉查找树

①、添加节点

②、查找节点

③、二叉查找树的弊端

5、二叉树的遍历方式

①、前序遍历（根、左、右）

②、中序遍历（左、根、右）

③、后序遍历（左、右、根）

④、层序遍历（一层一层遍历）

⑤、小结

6、平衡二叉树

①、平衡二叉树的旋转机制

②、左旋

③、右旋

④、平衡二叉树需要旋转的四种情况（左左、左右、右右、右左）

⑤、小结

7、树的演变

8、红黑树（一种特殊的二叉查找树，而不是平衡二叉树）【★★】

①、红黑树的红黑规则

②、红黑树添加节点的规则

③、小结（能看懂即可）

九、Set系列集合

1、练习：利用Set系列的集合，添加字符串，并使用多种方式遍历

①、示例代码

②、小结

2、HashSet底层原理

①、哈希值

②、对象的哈希值特点

3、HashSet JDK8 以前的底层原理

①、HashSet完整创建过程

②、HashSet创建的细节

4、HashSet的三个问题

①、HashSet为什么存和取的顺序不一样？

②、HashSet为什么没有索引？

③、HashSet是利用什么机制保证数据去重的？

④、问题回答

5、练习：利用HashSet集合去除重复元素

十、LinkedHashSet

1、LinkedHashSet底层原理

①、示例代码：（LinkedHashSet可以保证数据的存储顺序）

②、小结

十一、TreeSet（自动排序）

1、TreeSet的基本应用

①、TreeSet的特点

②、练习：利用TreeSet存储整数并进行排序

2、TreeSet集合默认的规则

①、TreeSet对象排序练习题

②、示例代码理解

3、TreeSet的两种比较方式

①、方式一：JavaBean类实现Comparable接口指定比较规则

②、方式二：比较器排序，创建TreeSet对象时，传递比较器Comparator指定规则

③、扩展：TreeSet对象排序练习题

4、小结

5、Set集合源码分析

①、HashSet

②、LinkedHashSet

③、TreeSet

十二、集合的使用场景

---

一、集合的体系结构

1、单列集合（Collection）

二、Collection集合

1、Collection常见方法

①、代码实现：

②、contains方法重写equals方法示例：（idea可自动重写）

2、Collection的遍历方式（3种）

①、迭代器遍历

示例：

循环遍历：

示例代码：（不依赖索引，而是通过指针移动的方式）

迭代器书写的小细节：

示例代码：

小结：

②、增强for遍历

示例代码：

增强for的细节：

③、Lambda表达式遍历

示例代码：

Lambda表达式形式：

3、小结

三、List集合

1、List集合特有的方法（操作索引的4个方法）

示例代码：

add方法：

remove方法：

List删除的小细节：

set & get方法：

2、List集合的遍历方式（5种）

①、示例代码

1、迭代器遍历：

2、增强for：

3、Lambda表达式

4、普通for循环

5、列表迭代器（ListIterator，继承于Iterator）

但迭代器默认指向0索引，想要使用previous方法需要先移动到后面

②、小结

四、数据结构（常见有8种）

1、什么是数据结构呢？

数据结构就是计算机存储、组织数据的方式

2、数据结构概述

3、栈（后进先出，先进后出）

栈内存：

4、队列（先进先出，后进后出）

5、栈与队列小结

6、数组

7、链表（与数组相对）

双向链表可以提高查询效率：

小结

五、ArrayList集合

1、ArrayList集合底层原理

2、ArrayList源码分析

idea快捷键：Alt+7：列出方法大纲

添加的数据长度不超过10：

一次添加多个，超过10，但不超过15：

六、LinkedList集合

1、LinkedList特有方法

2、LinkedList源码分析

3、迭代器的底层源码

modCount：集合变化的次数

expectedModCount：创建对象时，传递过来的次数

七、泛型深入

1、没有泛型时的集合如何存储数据？

没有泛型时，集合可以添加任意类型的值，但其弊端也很明显，不能访问子类特有的功能

泛型规范修改：

2、泛型的好处

3、知识点：Java中的泛型是伪泛型

4、泛型的细节

5、泛型可以在很多地方进行定义

①、泛型类

示例代码：

转成Integer：

②、泛型方法

练习：

代码实现：

可变参数改进代码：（即 类型… 变量名）

测试类：

③、泛型接口

方式1：实现类给出具体方法

方式2：实现类延续泛型，创建对象时再确定

6、泛型的继承和通配符

①、泛型的继承示例代码

②、泛型的通配符练习

练习：

示例代码：

7、小结

八、树（Tree）

1、集合起名的艺术

2、树的基本结构

一个树节点的基本结构：

3、二叉树

但数据没什么规则

4、二叉查找树

①、添加节点

②、查找节点

③、二叉查找树的弊端

为了避免长短腿的出现，就出现了平衡二叉树

5、二叉树的遍历方式

①、前序遍历（根、左、右）

②、中序遍历（左、根、右）

③、后序遍历（左、右、根）

④、层序遍历（一层一层遍历）

⑤、小结

6、平衡二叉树

①、平衡二叉树的旋转机制

②、左旋

当根节点是支点时：

③、右旋

普通情况：

当根节点是支点时：

④、平衡二叉树需要旋转的四种情况（左左、左右、右右、右左）

左左：（一次右旋）

左右：（先局部左旋，再整体右旋）

右右：（一次左旋）

右左：（先局部右旋，再整体左旋）

⑤、小结

1、在平衡二叉树中，如何添加节点？

A：大的存右边，小的存左边，相等的不存

2、如何查找单个节点？

A：从根节点开始查找，然后逐个比较

3、为什么要旋转？

A：只有平衡二叉树和红黑树才需要旋转；旋转的原因就是在添加一个节点后，导致这个树不平衡了，那么就需要通过旋转让它重新平衡

4、旋转的触发时机？

A：树不平衡了

5、左左是什么意思？

6、左右是什么意思？

7、右右是什么意思？

8、右左是什么意思？

7、树的演变

8、红黑树（一种特殊的二叉查找树，而不是平衡二叉树）【★★】

平衡二叉树也有一些弊端：在添加节点是时候，由于旋转次数太多，会导致添加节点的时间浪费。

①、红黑树的红黑规则

简单路径：只能往前，不能回头，eg：13 -> 8 -> 1 -> Nil

Nil本身实际上是没有什么含义的，就是在第5条的规则上，要用到它来统计个数的

②、红黑树添加节点的规则

如果默认节点颜色为黑色，那么添加三个节点，需要调整两次

如果默认节点颜色为红色，那么添加三个节点，只需要调整一次

添加节点示例：

③、小结（能看懂即可）

九、Set系列集合

无序：存取顺序不一致

不重复：可以去除重复

无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素

1、练习：利用Set系列的集合，添加字符串，并使用多种方式遍历

①、示例代码

多种方式遍历：

②、小结

2、HashSet底层原理

①、哈希值

②、对象的哈希值特点

因为地址不同

示例代码：

重写hashCode()方法后：

哈希碰撞情况：

3、HashSet JDK8 以前的底层原理

①、HashSet完整创建过程

当我们在创建一个HashSet对象时，在底层会创建一个默认长度为16，默认加载因子为0.75的数组：

②、HashSet创建的细节

4、HashSet的三个问题

①、HashSet为什么存和取的顺序不一样？

HashSet在遍历的时候，是从数组的0索引开始，一条链表，一条链表的查询

但是黄色小球就是第一个被存入的吗？不见得吧！

②、HashSet为什么没有索引？

主要原因是因为HashSet不够纯粹，底层是由数组+链表+红黑树构成的，所以不好规定以谁为索引

③、HashSet是利用什么机制保证数据去重的？

切记：如果HashSet中存储的是自定义对象，那么一定要重写HashCode和equals方法

④、问题回答

5、练习：利用HashSet集合去除重复元素

示例代码：

在JavaBean中重写hashCode和equals方法

十、LinkedHashSet

1、LinkedHashSet底层原理

①、示例代码：（LinkedHashSet可以保证数据的存储顺序）

②、小结

十一、TreeSet（自动排序）

1、TreeSet的基本应用

①、TreeSet的特点

②、练习：利用TreeSet存储整数并进行排序

直接打印：

遍历集合：

2、TreeSet集合默认的规则

字符串比较：

①、TreeSet对象排序练习题

示例代码：

JavaBean：Student.java

测试类：

运行程序结构报错了：因为JavaBean是我们自己写的，并没有给它添加一个默认的比较规则，所以TreeSet也不知道应该怎么比

②、示例代码理解

图解：

代码理解：

3、TreeSet的两种比较方式

①、方式一：JavaBean类实现Comparable接口指定比较规则

②、方式二：比较器排序，创建TreeSet对象时，传递比较器Comparator指定规则

示例：

因为是String类型，源码中已经定义了排序规则：即以ASCII表升序排序

所以我们就需要使用比较器，重写比较方法

改成lambda表达式：

③、扩展：TreeSet对象排序练习题

idea快捷键：

• Ctrl + D ：向下复制一行

示例代码：

JavaBean：Student.java

测试类：

默认排序情况：JavaBean实现Comparable接口，重现CompareTo方法

课堂练习：

在重写方法中加入System.out.println();语句即可

4、小结

如果方式一和方式二同时存在，那么实际上我们以方式二为准

5、Set集合源码分析

①、HashSet

HashSet其实是new了一个HashMap

②、LinkedHashSet

LinkedHashSet其实是new了一个LinkedHashMap

③、TreeSet

new了一个TreeMap

十二、集合的使用场景