-
红黑树
-
HashSet
-
Map
-
HashMap
-
TreeMap
==知识点梳理==
1.1红黑树-概述【了解】
1.什么是红黑树
平衡二叉B树，每一个节点可以是红或者黑，红黑树不是高度平衡的,它的平衡是通过"自己的红黑规则"进行实现的。
1.2 红黑树-红黑规则 (了解)
-
红黑树的红黑规则有哪些
-
每一个节点或是红色的,或者是黑色的
-
根节点必须是黑色
-
所有叶子节点（空的节点被称作叶子节点）都是黑色的
-
不能出现两个红色节点相连 的情况
-
对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点
-
1.3 红黑树-添加节点的默认颜色（了解)
添加节点时,默认为红色,效率高
1.4 红黑树-添加节点后，如何保证红黑规则1 【难点】
1.5 红黑树-添加节点后，如何保证红黑规则2 【难点】
（旋转之后，根据规则验证是否是红黑树，总结红黑树添加节点的规则）
1.6 红黑树练习-成绩排序案例【重点】
(共3点)
1.案例需求
-
用TreeSet集合存储多个学生信息(姓名,语文成绩,数学成绩,英语成绩),并遍历该集合
-
要求: 按照总分从低到高排序
代码实现
学生类
public class Student implements Comparable<Student> {
private String name;
private int chinese;
private int math;
private int english;
public Student() {
}
public Student(String name, int chinese, int math, int english) {
this.name = name;
this.chinese = chinese;
this.math = math;
this.english = english;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getChinese() {
return chinese;
}
public void setChinese(int chinese) {
this.chinese = chinese;
}
public int getMath() {
return math;
}
public void setMath(int math) {
this.math = math;
}
public int getEnglish() {
return english;
}
public void setEnglish(int english) {
this.english = english;
}
public int getSum() {
return this.chinese + this.math + this.english;
}
测试类
public class TreeSetDemo {
public static void main(String[] args) {
//创建TreeSet集合对象，通过比较器排序进行排序
TreeSet<Student> ts = new TreeSet<Student>();
//创建学生对象
Student s1 = new Student("jack", 98, 100, 95);
Student s2 = new Student("rose", 95, 95, 95);
Student s3 = new Student("sam", 100, 93, 98);
//把学生对象添加到集合
ts.add(s1);
ts.add(s2);
ts.add(s3);
//遍历集合
for (Student s : ts) {
System.out.println(s.getName() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + s.getSum());
}
}
}
2.TreeSet原理
2.HashSet集合
2.1HashSet-基本使用【重点】
1.什么是HashSet(HashSet的特点)
-
底层数据结构是哈希表
-
存取无序
-
不可以存储重复元素
-
没有索引,不能使用普通for循环遍历（get方法）
2.HashSet使用-存储字符串并遍历
package com.itheima.myhashset;
import java.util.HashSet;
import java.util.Iterator;
/**
* 添加字符串并进行遍历
*/
public class HashSetDemo1 {
public static void main(String[] args) {
HashSet<String> hs = new HashSet<>();
hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("java");
hs.add("java");
hs.add("java");
hs.add("java");
hs.add("java");
Iterator<String> it = hs.iterator();
while(it.hasNext()){
String s = it.next();
System.out.println(s);
}
System.out.println("=============================");
for (String s : hs) {
System.out.println(s);
}
}
}
2.2哈希值【了解】
1.什么是哈希值
是JDK根据对象的地址或者属性值，算出来的int类型的整数
2.如何获取对象中的Hash值
Object类中有一个方法: public int hashCode():根据对象的地址值计算出来的哈希值
3.哈希值的特点
-
没有重写HashCode的情况：
1.同种一对象多次调用hashCode方法返回值是一样的
2.不同对象hashCode方法返回值不一样
-
Object子类重写hashCode方法的情况：
重写的目的是计算对象哈希值时，按属性值来计算，因此只要属性值相同，不同对象的hashCode方法返回值是一样的
package com.itheima.myhashset;
/**
* 计算哈希值
*/
public class HashSetDemo2 {
public static void main(String[] args) {
Student s1 = new Student("xiaozhi",23);
Student s2 = new Student("xiaomei",22);
//因为在Object类中，是根据对象的地址值计算出来的哈希值。
System.out.println(s1.hashCode());//1060830840
System.out.println(s1.hashCode());//1060830840
System.out.println(s2.hashCode());//2137211482
}
}
Student类
package com.itheima.myhashset;
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;
}
//我们可以对Object类中的hashCode方法进行重写
//在重写之后，就一般是根据对象的属性值来计算哈希值的。
//此时跟对象的地址值就没有任何关系了。
2.4HashSet-JDK7底层原理【难点】
哈希表=数组 + 链表
2.5HashSet-JDK8底层优化【难点】
（共两点）
1.HashSet 在JDK1.8之后的原理
-
节点个数少于等于8个
数组 + 链表
-
节点个数多于8个
数组 + 红黑树
2.HashSet 在JDK1.8版本的存储流程
2.6HashSet集合存储学生对象并遍历【重点】
-
案例需求
-
创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合
-
要求：学生对象的成员变量值相同，我们就认为是同一个对象
-
-
代码实现
测试类
public class HashSetDemo2 {
public static void main(String[] args) {
//HashSet集合存储自定义类型元素,要想实现元素的唯一,要求必须重写hashCode方法和equals方法
HashSet<Student> hashSet = new HashSet<>();
Student s1 = new Student("xiaohei",23);
Student s2 = new Student("xiaohei",23);
Student s3 = new Student("xiaomei",22);
hashSet.add(s1);
hashSet.add(s2);
hashSet.add(s3);
for (Student student : hashSet) {
System.out.println(student);
}
}
}学生类
package com.itheima.myhashset;
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;
}
3.Map集合
3.1Map-基本使用【重点、难点】
(共3点)
1.什么是Map集合【记忆】
Map集合又称为双列集合，双列集合中元素的内容是成对的
2.Map集合的特点 【记忆】
键不能重复，值可以重复
键与值之间是一一对应的关系
(键+值)这个整体我们称之为"键值对"或"键值对对象",在Java中又叫"Entry对象"
3.如何使用Map集合
1.Map集合格式
interface Map<K,V> K：键的类型；V：值的类型
2.如何创建Map集合对象
Map<String,String> map = new HashMap<String,String>();//使用具体实现类，采用多态形式创建
4.使用Map集合存储学生学号和姓名
package com.itheima.mapdemo1;
import java.util.HashMap;
import java.util.Map;
/**
* Map的基本使用
*/
public class MyMap1 {
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
//map.add();
map.put("itheima001","小智");
map.put("itheima002","小美");
map.put("itheima003","大胖");
System.out.println(map);
}
}
3.2Map常用方法【重点】
-
方法介绍
方法名 说明 V put(K key,V value) 添加元素 V remove(Object key) 根据键删除键值对元素 void clear() 移除所有的键值对元素 boolean containsKey(Object key) 判断集合是否包含指定的键 boolean containsValue(Object value) 判断集合是否包含指定的值 boolean isEmpty() 判断集合是否为空 int size() 集合的长度，也就是集合中键值对的个数 -
示例代码
package com.itheima.mapdemo1;
import java.util.HashMap;
import java.util.Map;
/**
* Map的基本方法
*/
public class MyMap2 {
public static void main(String[] args) {
Map<String,String> map = new HashMap<>();
map.put("itheima001","小智");
map.put("itheima002","小美");
map.put("itheima003","大胖");
map.put("itheima004","小黑");
map.put("itheima005","大师");
//method1(map);
//method2(map);
//method3(map);
//method4(map);
//method5(map);
//method6(map);
//method7(map);
}
private static void method7(Map<String, String> map) {
// int size() 集合的长度，也就是集合中键值对的个数
int size = map.size();
System.out.println(size);
}
private static void method6(Map<String, String> map) {
// boolean isEmpty() 判断集合是否为空
boolean empty1 = map.isEmpty();
System.out.println(empty1);//false
map.clear();
boolean empty2 = map.isEmpty();
System.out.println(empty2);//true
}
private static void method5(Map<String, String> map) {
// boolean containsValue(Object value) 判断集合是否包含指定的值
boolean result1 = map.containsValue("aaa");
boolean result2 = map.containsValue("小智");
System.out.println(result1);
System.out.println(result2);
}
private static void method4(Map<String, String> map) {
// boolean containsKey(Object key) 判断集合是否包含指定的键
boolean result1 = map.containsKey("itheima001");
boolean result2 = map.containsKey("itheima006");
System.out.println(result1);
System.out.println(result2);
}
private static void method3(