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办法