集合进阶

泛型

问题，没有泛型的时候，集合是如何存储数据的

结论：如果我们没有给集合指定类型，默认为所以有数据类型都是object类型，此时可以往集合添加任意的数据类型，但有一个坏处，我们在获取数据的时候，无法使用他特有的行为。

此时就推出了泛型，可以在添加数据的时候就把类型统一，而且我们在获取数据的时候，耶省的强转了，非常的方便

泛型的好处：统一数据类型，把运行时期的问题提前到了编译期间，避免了强制类型转换可能出现的异常，因为在编译阶段类型就能确定下来。

泛型的一些注意细节：泛型中不能写基本数据类型，指定泛型的具体类型后，传递数据时，可以传入该类类型或其子类类型，如果不写泛型，默认是Object类型。

泛型类

使用场景：当一个类中，某个变量的数据类型不确定时，就可以定义带有泛型的类。

格式：

修饰符class类名<类型>{

}

举例：

publuc class ArrayList{

}

此处的E可以理解为变量，但不是用来记录数据的，而是记录数据的类型，可以写成：T、E、K、V等。、

LinkedList和迭代器的源码分析：

泛型

泛型不具备继承性，但数据具备继承性。

1.什么是泛型？

JDK5引入的特性，可以在便已经i二段约束操作的数据类型，并进行检查

2.泛型的好处？

统一数据类型

把运行时期的问题提前到了编译期间，避免了强制

3.泛型的细节？

泛型中不能写基本数据类型。

指定泛型的具体类型过后，传递数据时，可以传入该类型和他的子类类型

如果不写泛型，类型默认是Object

4.哪里定义泛型？

泛型类：在类名后面定义泛型，创建该对象的时候，确定类型

泛型方法：在修饰符后面定义方法，调用该方法的时候，确定类型

泛型接口：在接口名后面定义泛型，实现类确定类型，实现类延续泛型

5.泛型的继承和通配符

泛型不具备继承性，但是数据具备继承性

泛型的通配符：< ？>

？ extend E

？ super E

6.使用场景

定义类，方法，接口的时候，如果类型不确定，就可以定义2泛型

如果类型不确定，但是能知道是哪个继承体系中的，可以使用泛型的通配符

单列集合

数据结构

二叉树、二叉查找树、平衡二叉树。

数据结构（二叉树）小结

结点内部结构

父节点地址

值

左子节点地址右子节点地址

度：每一个结点的子节点数量树高：树的总层数

根节点：最顶层的结点左子节点：左下方的结点

右子节点：右下方的结点跟结点的左子树：蓝色虚线

根节点的右子树：绿色虚线

二叉树的弊端：左边的普通二叉树没有规律想查找数据只能通过遍历，所以就有了右边儿二叉查找树；二叉查找树：小的存左边，大的存右边，一样的不存。

二叉树的四种遍历方式

1.前序遍历：当前结点，左子节点，右子节点

2.中序遍历，左子节点，当前结点，右子节点

3.后序遍历，左子节点，右子节点，当前结点

4.层序遍历：一层一层的去遍历

平衡二叉树

平衡二叉树需要掌握的八个问题

1.在平衡二叉树中，如何添加结点？

平衡二叉树实际就是二叉树演变过来的，所以添加结点也准守着，小的存左边大的存右边的规则。

2.在平衡二叉树中，如何查找单个结点？

平衡二叉树的查找是从根结点开始查找的依次对比，和你所查找的结点进行比较，小的在左边大的在右边。

3.为什么要旋转

普通二叉树和二叉查找树是不需要旋转的，平衡二叉树的需要旋转是因为，在添加一个节点的时候左右节点高度不平衡了，就需要旋转来保持平衡。

4.旋转的触发时机？

当成功添加一个数破坏了这个树的平衡，这个时候就需要旋转来维持平衡，如果添加一个树没有破坏这个树的平衡就不需要旋转。

5.左左是什么意思？如何旋转？

左左就是当我们把新节点添加到根结点的左子树的左子树上破坏了平衡，找到支点进行依次右旋就行了

6.左右事什么意思？如何旋转？

左右就是将新的节点添加在左子树的右子树上破坏了平衡，在左右的情况下只旋转一次是不够的，我们需要先进行局部的左旋然后再来整体的右旋。

7.右右是什么意思？如何旋转？

右右就是在根节点的右子树的右子树上添加新的节点破坏了平衡，找到支点进行一次左旋就可以了。

8.右左是什么意思？如何旋转？

右左就是将新节点添加在右子树的左子树上破坏平衡，这个时候旋转一次也是不够的，我们需要先局部的右旋，再整体的左旋。

红黑树

是一个二叉查找树：

但是，不是高度平衡的

条件：特有的红黑规则

数据结构与（红黑树）红黑规则

1.每一个节点或是红色的，或者是黑色的

2.根节点必须是黑色的

3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的

4.如果某个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）

5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

注意：添加的节点默认是红色的（效率高）。

Set系类集合

无序：存取顺序不一致

不可重复：可以去吃重复

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

Set集合的实现类

HashSet：无须、不重复、无索引

LinkedHashSet：有序、不重复、无索引

TreeSet：可排序、不重复、无索引

Set接口中的方法基本上与Collection的API一致。

HashSet

HashSet底层原理

HashSet集合底层采取哈希表存储数据

哈希表是一种对于增删查改数据性能都较好的结构

哈希表组成

JDK8之前：数组+链表

JDK8开始：数组+链表+红黑树

哈希值：

根据hashCode方法算出来的int类型的整数

该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算

一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值

对象的哈希值特点：

如果没有重写hashCode方法，不同对象计算出来的哈希值是不一样的

如果已经重写hashCode方法，不同的对象只需要属性值相同，计算出来的哈希值就是一样的

在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。（哈希碰撞）

1.LinkedHashSet集合的特点和原理是怎么样的？

有序、不重复、无索引

底层基于哈希表，使用双链表记录添加顺序

2.以后如果要数据去重，我们使用哪个？

默认使用HashSet

如果要求去重且存取有序，才使用LinkedHashSet

TreeSet

1.TreeSet集合的特点是怎么样的？

可排序、不重复、无索引

底层基于红黑树实现排序，增删改查性能好

2.TreeSet集合自定义排序规则有几种方式

方式一：Javabean类实现Comparable接口，指定比较规则

方式二：创建集合时，自定义Comparator比较器对象，指定比较规则

总结

1.如果想要集合钟的元素可重复

用arrayList集合，基于数组的。（用的最多）

2.如果想要集合中的元素可重复，而且当前的增删操作明显多于查询

3.如果想对集合中的元素去重

用HashSet集合，基于哈希表的。（用的最多）

4.如果相对集合中的元素去重，而且保证存取顺序

用LinkedHashSet集合，基于哈希表和双链表，效率低于HashSet

5.如果想对集合中的元素进行排序

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

双列集合

Map

双列集合的特点

1.双列集合一次需要存一对数据，分别为键和值

2.键不能重复，值可以重复

3.键和值是一一对应的，每一个键只能找到自己对应的值

4.键+值这个整体我们称之为“键值对”或者“键值对象”，在Java中叫做“Entrv对象”

HashMap

1.HashMap底层是哈希表结构的

2.依赖hashCode方法和equals方法保证键的唯一

3.如果键存储的是自定义对象，需要重写hashCode和equals方法

如果值存储自定义对象，不需要重写hashCode和equals方法

LinkedHashMap

由键决定：有序、不重复、无索引

这里的有序指的是保证存储和去除的元素顺序一致

原理：底层数据结构依然是哈希表，只是每个键值对元素又额外的多了一个双链表的机制记录存储的顺序。

TreeMap

treeMap根TreeSet底层原理是一样的，都是红黑树结构的。

由键决定特性：不重复、无索引、可排序

可排序：对键进行排序。

注意：默认按照键的从小到大进行排序，也可以自己规定键的排序规则

代码书写两种排序规则

实现Comparable接口，指定比较规则

创建集合时传递Comparator比较器对象，指定比较规则

TreeMap总结

1.TreeMap集合的特点是怎么样的？

不重复、无索引、可排序

底层基于红黑树实现排序，增删改查性能较好

2.TreeMap集合排序的两种方式