1. 泛型
1.1 泛型概述
-
泛型的介绍
泛型是 JDK5 中引入的个性，它提供了编译时类型平安检测机制
-
泛型的益处
- 把运行期间的问题提前到了编译期间
- 防止了强制类型转换
-
泛型的定义格局
- < 类型 >: 指定一种类型的格局. 尖括号外面能够任意书写, 个别只写一个字母. 例如: <E> <T>
- < 类型 1, 类型 2…>: 指定多种类型的格局, 多种类型之间用逗号隔开. 例如: <E,T> <K,V>
2.Set 汇合
2.1Set 汇合概述和特点
- 不能够存储反复元素
- 没有索引, 不能应用一般 for 循环遍历
2.2Set 汇合的应用
存储字符串并遍历
public class MySet1 {public static void main(String[] args) {
// 创立汇合对象
Set<String> set = new TreeSet<>();
// 增加元素
set.add("ccc");
set.add("aaa");
set.add("aaa");
set.add("bbb");
// for (int i = 0; i < set.size(); i++) {
// //Set 汇合是没有索引的，所以不能应用通过索引获取元素的办法
// }
// 遍历汇合
Iterator<String> it = set.iterator();
while (it.hasNext()){String s = it.next();
System.out.println(s);
}
System.out.println("-----------------------------------");
for (String s : set) {System.out.println(s);
}
}
}3.TreeSet 汇合
3.1TreeSet 汇合概述和特点
- 不能够存储反复元素
- 没有索引
-
能够将元素依照规定进行排序
- TreeSet()：依据其元素的天然排序进行排序
- TreeSet(Comparator comparator)：依据指定的比拟器进行排序
3.2TreeSet 汇合根本应用
存储 Integer 类型的整数并遍历
public class TreeSetDemo01 {public static void main(String[] args) {
// 创立汇合对象
TreeSet<Integer> ts = new TreeSet<Integer>();
// 增加元素
ts.add(10);
ts.add(40);
ts.add(30);
ts.add(50);
ts.add(20);
ts.add(30);
// 遍历汇合
for(Integer i : ts) {System.out.println(i);
}
}
}3.3 天然排序 Comparable 的应用
-
案例需要
- 存储学生对象并遍历，创立 TreeSet 汇合应用无参构造方法
- 要求：依照年龄从小到大排序，年龄雷同时，依照姓名的字母程序排序
-
实现步骤
-
应用空参结构创立 TreeSet 汇合
- 用 TreeSet 汇合存储自定义对象，无参构造方法应用的是天然排序对元素进行排序的
-
自定义的 Student 类实现 Comparable 接口
- 天然排序，就是让元素所属的类实现 Comparable 接口，重写 compareTo(T o)办法
-
重写接口中的 compareTo 办法
- 重写办法时，肯定要留神排序规定必须依照要求的次要条件和主要条件来写
-
-
代码实现
学生类
public class Student implements Comparable<Student>{ private String name; private int age; public Student() {} public Student(String name, int age) { this.name = name; this.age = age; } public String getName() {return name;} public void setName(String name) {this.name = name;} public int getAge() {return age;} public void setAge(int age) {this.age = age;} @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; } @Override public int compareTo(Student o) { // 依照对象的年龄进行排序 // 次要判断条件: 依照年龄从小到大排序 int result = this.age - o.age; // 主要判断条件: 年龄雷同时，依照姓名的字母程序排序 result = result == 0 ? this.name.compareTo(o.getName()) : result; return result; } }测试类
public class MyTreeSet2 {public static void main(String[] args) { // 创立汇合对象 TreeSet<Student> ts = new TreeSet<>(); // 创立学生对象 Student s1 = new Student("zhangsan",28); Student s2 = new Student("lisi",27); Student s3 = new Student("wangwu",29); Student s4 = new Student("zhaoliu",28); Student s5 = new Student("qianqi",30); // 把学生增加到汇合 ts.add(s1); ts.add(s2); ts.add(s3); ts.add(s4); ts.add(s5); // 遍历汇合 for (Student student : ts) {System.out.println(student); } } }
3.4 比拟器排序 Comparator 的应用
-
案例需要
- 存储老师对象并遍历，创立 TreeSet 汇合应用带参构造方法
- 要求：依照年龄从小到大排序，年龄雷同时，依照姓名的字母程序排序
-
实现步骤
- 用 TreeSet 汇合存储自定义对象，带参构造方法应用的是比拟器排序对元素进行排序的
- 比拟器排序，就是让汇合构造方法接管 Comparator 的实现类对象，重写 compare(T o1,T o2)办法
- 重写办法时，肯定要留神排序规定必须依照要求的次要条件和主要条件来写
-
代码实现
老师类
public class Teacher { private String name; private int age; public Teacher() {} public Teacher(String name, int age) { this.name = name; this.age = age; } public String getName() {return name;} public void setName(String name) {this.name = name;} public int getAge() {return age;} public void setAge(int age) {this.age = age;} @Override public String toString() { return "Teacher{" + "name='" + name + '\'' + ", age=" + age + '}'; } }测试类
public class MyTreeSet4 {public static void main(String[] args) { // 创立汇合对象 TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() { @Override public int compare(Teacher o1, Teacher o2) { //o1 示意当初要存入的那个元素 //o2 示意曾经存入到汇合中的元素 // 次要条件 int result = o1.getAge() - o2.getAge(); // 主要条件 result = result == 0 ? o1.getName().compareTo(o2.getName()) : result; return result; } }); // 创立老师对象 Teacher t1 = new Teacher("zhangsan",23); Teacher t2 = new Teacher("lisi",22); Teacher t3 = new Teacher("wangwu",24); Teacher t4 = new Teacher("zhaoliu",24); // 把老师增加到汇合 ts.add(t1); ts.add(t2); ts.add(t3); ts.add(t4); // 遍历汇合 for (Teacher teacher : ts) {System.out.println(teacher); } } }
3.5 两种比拟形式总结
-
两种比拟形式小结
- 天然排序: 自定义类实现 Comparable 接口, 重写 compareTo 办法, 依据返回值进行排序
- 比拟器排序: 创立 TreeSet 对象的时候传递 Comparator 的实现类对象, 重写 compare 办法, 依据返回值进行排序
- 在应用的时候, 默认应用天然排序, 当天然排序不满足当初的需要时, 必须应用比拟器排序
-
两种形式中对于返回值的规定
- 如果返回值为正数，示意以后存入的元素是较小值，存右边
- 如果返回值为 0，示意以后存入的元素跟汇合中元素反复了，不存
- 如果返回值为负数，示意以后存入的元素是较大值，存左边
4. 数据结构
4.1 二叉树
-
二叉树的特点
-
二叉树中, 任意一个节点的度要小于等于 2
- 节点: 在树结构中, 每一个元素称之为节点
- 度: 每一个节点的子节点数量称之为度
-
- 二叉树结构图
4.2 二叉查找树
-
二叉查找树的特点
- 二叉查找树, 又称二叉排序树或者二叉搜寻树
- 每一个节点上最多有两个子节点
- 左子树上所有节点的值都小于根节点的值
- 右子树上所有节点的值都大于根节点的值
-
二叉查找树结构图
- 二叉查找树和二叉树比照结构图
-
二叉查找树增加节点规定
- 小的存右边
- 大的存左边
- 一样的不存
4.3 均衡二叉树
-
均衡二叉树的特点
- 二叉树左右两个子树的高度差不超过 1
- 任意节点的左右两个子树都是一颗均衡二叉树
-
均衡二叉树旋转
-
旋转触发机会
- 当增加一个节点之后, 该树不再是一颗均衡二叉树
-
左旋
- 就是将根节点的右侧往左拉, 原先的右子节点变成新的父节点, 并把多余的左子节点出让, 给曾经降级的根节点当右子节点
-
-
右旋
- 就是将根节点的左侧往右拉, 左子节点变成了新的父节点, 并把多余的右子节点出让, 给曾经降级根节点当左子节点
-
均衡二叉树和二叉查找树比照结构图
-
均衡二叉树旋转的四种状况
-
左左
- 左左: 当根节点左子树的左子树有节点插入, 导致二叉树不均衡
-
如何旋转: 间接对整体进行右旋即可
-
左右
- 左右: 当根节点左子树的右子树有节点插入, 导致二叉树不均衡
-
如何旋转: 先在左子树对应的节点地位进行左旋, 在对整体进行右旋
-
右右
- 右右: 当根节点右子树的右子树有节点插入, 导致二叉树不均衡
-
如何旋转: 间接对整体进行左旋即可
-
右左
- 右左: 当根节点右子树的左子树有节点插入, 导致二叉树不均衡
-
如何旋转: 先在右子树对应的节点地位进行右旋, 在对整体进行左旋
-
4.3 红黑树
-
红黑树的特点
- 均衡二叉 B 树
- 每一个节点能够是红或者黑
- 红黑树不是高度均衡的, 它的均衡是通过 ” 本人的红黑规定 ” 进行实现的
-
红黑树的红黑规定有哪些
- 每一个节点或是红色的, 或者是彩色的
- 根节点必须是彩色
- 如果一个节点没有子节点或者父节点, 则该节点相应的指针属性值为 Nil, 这些 Nil 视为叶节点, 每个叶节点 (Nil) 是彩色的
- 如果某一个节点是红色, 那么它的子节点必须是彩色(不能呈现两个红色节点相连 的状况)
- 对每一个节点, 从该节点到其所有后辈叶节点的简略门路上, 均蕴含雷同数目的彩色节点
-
红黑树增加节点的默认色彩
- 增加节点时, 默认为红色, 效率高
-
红黑树增加节点后如何放弃红黑规定
-
根节点地位
- 间接变为彩色
-
非根节点地位
-
父节点为彩色
- 不须要任何操作, 默认红色即可
-
父节点为红色
-
叔叔节点为红色
- 将 ” 父节点 ” 设为彩色, 将 ” 叔叔节点 ” 设为彩色
- 将 ” 祖父节点 ” 设为红色
- 如果 ” 祖父节点 ” 为根节点, 则将根节点再次变成彩色
-
叔叔节点为彩色
- 将 ” 父节点 ” 设为彩色
- 将 ” 祖父节点 ” 设为红色
- 以 ” 祖父节点 ” 为支点进行旋转
-
-
-
5.HashSet 汇合
5.1HashSet 汇合概述和特点
- 底层数据结构是哈希表
- 存取无序
- 不能够存储反复元素
- 没有索引, 不能应用一般 for 循环遍历
5.2HashSet 汇合的根本利用
存储字符串并遍历
public class HashSetDemo {public static void main(String[] args) {
// 创立汇合对象
HashSet<String> set = new HashSet<String>();
// 增加元素
set.add("hello");
set.add("world");
set.add("java");
// 不蕴含反复元素的汇合
set.add("world");
// 遍历
for(String s : set) {System.out.println(s);
}
}
}5.3 哈希值
-
哈希值简介
是 JDK 依据对象的地址或者字符串或者数字算进去的 int 类型的数值
-
如何获取哈希值
Object 类中的 public int hashCode()：返回对象的哈希码值
-
哈希值的特点
- 同一个对象屡次调用 hashCode()办法返回的哈希值是雷同的
- 默认状况下，不同对象的哈希值是不同的。而重写 hashCode()办法，能够实现让不同对象的哈希值雷同
5.4 哈希表构造
-
JDK1.8 以前
数组 + 链表
-
JDK1.8 当前
-
节点个数少于等于 8 个
数组 + 链表
-
节点个数多于 8 个
数组 + 红黑树
-
5.5HashSet 汇合存储学生对象并遍历
-
案例需要
- 创立一个存储学生对象的汇合，存储多个学生对象，应用程序实现在控制台遍历该汇合
- 要求：学生对象的成员变量值雷同，咱们就认为是同一个对象
-
代码实现
学生类
public class Student { private String name; private int age; public Student() {} public Student(String name, int age) { this.name = name; this.age = age; } public String getName() {return name;} public void setName(String name) {this.name = name;} public int getAge() {return age;} public void setAge(int age) {this.age = age;} @Override public boolean equals(Object o) {if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; if (age != student.age) return false; return name != null ? name.equals(student.name) : student.name == null; } @Override public int hashCode() {int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } }测试类
public class HashSetDemo02 {public static void main(String[] args) { // 创立 HashSet 汇合对象 HashSet<Student> hs = new HashSet<Student>(); // 创立学生对象 Student s1 = new Student("林青霞", 30); Student s2 = new Student("张曼玉", 35); Student s3 = new Student("王祖贤", 33); Student s4 = new Student("王祖贤", 33); // 把学生增加到汇合 hs.add(s1); hs.add(s2); hs.add(s3); hs.add(s4); // 遍历汇合(加强 for) for (Student s : hs) {System.out.println(s.getName() + "," + s.getAge()); } } } -
总结
HashSet 汇合存储自定义类型元素, 要想实现元素的惟一, 要求必须重写 hashCode 办法和 equals 办法