[数据结构与算法]集合(三)

1 红黑树

学习红黑树的目标：学习的就是红黑规则

1.1 概述

特点：

1、红黑树早期将其称之为平衡二叉B树(B-树)

2、红黑树树它的平衡是依赖于红黑规则

3、每一个节点的颜色要么是红色，要么是黑色

1.2 红黑规则

红黑规则：

1、每一个节点的颜色要么是红色，要么是黑色

2、根节点必须是黑色

3、如果一个节点没有父节点或者子节点，那么该节点的这些属性就是nil(null)，这些nil节点我们将其称之为叶节点 ，并且叶节点必须是黑色

4、不能出现两个相邻的红色节点

5、从任意一个节点开始，到其所有的后代的叶节点的简单路径上必须包含相同数量的黑色节点

红黑树：

向红黑树中添加一个节点的默认颜色应该是什么？红色（红色对树的调整次数较少，效率就较高）

向一颗红黑树中添加一个节点，很有可能会破坏红黑规则，此时就需要对树进行调整，而调整方式：1、变色 2、旋转 。

根据不同的情况调整策略不一样。这个小知识点了解即可。

1、根节点

• 直接进行变色(黑色)即可

2、非根节点

• 父节点是黑色 ----> 不需要进行调整
• 父节点是红色
  • 父节点的兄弟节点是红色
    • 父节点以及父节点的兄弟节点变成黑色
    • 将祖父节点设置为红色
    • 如果祖父节点是根节点，再次将其设置为黑色
  • 父节点的兄弟节点是黑色
    • 父节点设置为黑色
    • 祖父节点设置为红色
    • 然后以祖父节点为支点进行旋转

TreeSet底层的数据结构是红黑树。那么接下看看源码是怎么实现红黑树。

需求：键盘录入3个学生信息(姓名,语文成绩,数学成绩,英语成绩),按照总分从高到低输出到控制台

步骤：

1、创建一个TreeSet集合对象

• 自然排序 ： 让学生类去实现Comparable接口
• 比较器排序 ： 选择带参构造方法创建对象

排序的条件：

主要条件：总分

次要条件：各科的成绩以及姓名

2、创建一个学生类（属性：姓名,语文成绩,数学成绩,英语成绩）

3、创建3个学生对象

4、把学生对象添加到集合中

5、遍历集合

2 HashSet

特点：

1、元素无序

2、每一个元素没有索引

3、可以保证元素的唯一性

入门案例

需求：使用HashSet集合存储字符串，并遍历

步骤：

1、创建HashSet集合对象（public HashSet() ）

2、添加元素

3、遍历HashSet集合

• 迭代器
• 增强for
• forEach方法

代码实现：

public class HashSetDemo01 {

    public static void main(String[] args) {

        // 创建HashSet集合对象（public HashSet() ）
        HashSet<String> hashSet = new HashSet<>();

        // 添加元素
        hashSet.add("hello") ;
        hashSet.add("world") ;
        hashSet.add("java") ;
        hashSet.add("java") ;

        // 遍历HashSet集合
        // 迭代器
        Iterator<String> it = hashSet.iterator();
        while(it.hasNext()) {
            System.out.println(it.next());
        }

        System.out.println("----------------------------------------------------");

        // 增强for
        for(String s : hashSet) {
            System.out.println(s);
        }

        System.out.println("----------------------------------------------------");

        // forEach方法
        hashSet.forEach( s -> System.out.println(s) );

    }

}

3 HashSet集合的原理

HashSet集合底层的数据结构是：哈希表

3.1 哈希码值

为什么要学习哈希值？

HashSet底层的数据结构是哈希表，使用哈希表在进行数据存储的时候，需要使用到对象的哈希值。

概述：就是一个int类型的值，这个值是通过对象的地址值计算出来的

获取方式：调用对象的hashCode方法得到，hashCode方是Object类中的方法

特点：

1、通过一个对象，多次调用hashCode方法得到的哈希值都是一样的

2、不同的对象调用hashCode方法，默认情况下得到的结果是不一样的。特殊情况：重写hashCode方法。 两个对象的hashCode值是一样的，也并不能说明两个对象是同一个对象。

3.2 JDK1.7之前的哈希表的结构

哈希表的结构：数组 + 链表

当我们创建了一个HashSet集合对象的时候，在内存中首先会初始化一个数组，数组的长度是16 ， 数组的加载因子是0.75（作用：用来对集合进行扩容的）

添加元素的流程：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BDFTe8lY-1635156670327)(images/image-20210429140457042.png)]

HashSet集合保证元素唯一性原理：依赖于元素的两个方法： hashCode 、equals方法 ， 当hashCode方法返回的哈希值是相同的，并且equals方法返回的结果是true。那么此时就认为这

个元素在集合中已经存在了，就不会把这个元素添加到集合中。

扩容原理：首先根据数组的长度和加载因子，计算出来一个阈值(16 * 0.75 = 12) , 当集合中的元素超过12个的时候，此时就会触发扩容机制，新的数组的长度是元数组的2倍。

3.3 JDK1.8之前的哈希表的结构

JDK1.7之前的哈希表的结构弊端：当链表的长度过长的时候，数据的查询效率较低。因此从JDK1.8之后就对哈希表进行优化。

优化结构：数组 + 链表 + 红黑树

当链表中的元素个数超过8个的时候，并且数组的长度超过64的时候，此时就会把链表变成红黑树。

当链表中的元素个数超过8个的时候，但是数组的长度没有超过64的时候，此时仅仅是进行扩容。

问题：红黑树是可以对元素进行排序，那么要进行排序就必须去指定排序规则，当时我们没有去指定任何的排序规则，那么红黑树到底是怎么进行构建的？

按照对象的哈希码进行排序

3.4 练习题

需求：创建一个存储学生对象的集合，存储多个学生对象，使用程序实现在控制台遍历该集合

要求：学生对象的成员变量值相同，我们就认为是同一个对象

学生类：

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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", 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;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

}

测试类：

public class HashSetDemo02 {

    // 要求：如果两个对象的成员变量都是相同的，则认为是通一个对象
    public static void main(String[] args) {


        // 1、创建HashSet集合对象
        HashSet<Student> hashSet = new HashSet<>();

        // 2、创建学生对象
        Student s1 = new Student("柳岩" , 18) ;
        Student s2 = new Student("陈晓旭" , 20) ;
        Student s3 = new Student("张国荣" , 21) ;
        Student s4 = new Student("张国荣" , 21) ;

        // 3、把学生对象添加到集合中
        hashSet.add(s1) ;
        hashSet.add(s2) ;
        hashSet.add(s3) ;
        hashSet.add(s4) ;

        // 4、遍历集合
        for(Student s : hashSet) {
            System.out.println(s);
        }

    }

}

结论：使用HashSet集合存储元素，要保证元素的唯一性，需要依赖于元素的两个方法：hashCode 、equals方法。存储自定义对象，需要重写这两个方法。

重写方式：借助于idea的开发工具 ， alt + insert —> equals and hasCode…

3.5 总结

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lX0BsQIH-1635156670330)(images/image-20210429150205668.png)]

4 Map集合

4.1 Map概述

Map是双列集合的顶层接口，存储的元素一对一对。第一列将其称之为键（key） 、第二列将其称之为值（value） ， 键是唯一的，值可以重复。并且一个键只能对应一个值。

后期如果数据之间存在对应关系，此时就可以使用Map集合进行存储。

基本使用：

public class MyMap1 {

    public static void main(String[] args) {

        Map<String,String> map = new HashMap<>();
        map.put("itheima001","小智");
        map.put("itheima002","小美");
        map.put("itheima003","大胖");
        System.out.println(map);

    }
    
}

4.2 常用方法

常用方法：

V   put(K key , V  value)				// 添加元素，返回值代表的是上一次该键所对应的值
V   remove(Object key)					// 根据键删除键值对元素，返回值表示被删除的键所对应的值
void   clear()							// 移除所有的键值对元素
boolean containsKey(Object key)			// 判断集合是否包含指定的键
boolean containsValue(Object value)		// 判断集合是否包含指定的值
boolean isEmpty()						// 判断集合是否为空
int size()								// 集合的长度，也就是集合中键值对的个数

4.3 遍历方式

4.3.1 键找值遍历

思路：

1、获取Map集合中所有的键（得到的就是一个集合对象） Set keySet();

2、遍历这个集合对象，获取每一个键，然后根据这个键从Map集合中查找对应值 V get(Object key);

代码实现：

public class MyMap3 {
    
    public static void main(String[] args) {
        
        //创建集合并添加元素
        Map<String,String> map = new HashMap<>();
        map.put("1号丈夫","1号妻子");
        map.put("2号丈夫","2号妻子");
        map.put("3号丈夫","3号妻子");
        map.put("4号丈夫","4号妻子");
        map.put("5号丈夫","5号妻子");

        //获取到所有的键
        Set<String> keys = map.keySet();
        
        //遍历Set集合得到每一个键
        for (String key : keys) {
            //通过每一个键key，来获取到对应的值
            String value = map.get(key);
            System.out.println(key + "---" + value);
        }
        
    }
}

4.3.2 键值对遍历

思路：

1、获取Map集合中所有的键值对对象(得到的就是一个集合) Set<Map.Entry<K, V>> entrySet();

2、遍历这个集合，获取每一个元素，每一个元素就是一个键值对对象

3、调用键值对对象的方法，获取键和值

K getKey();				// 获取键
V getValue();			// 获取值

代码实现：

public class MyMap4 {

    public static void main(String[] args) {
    
        //创建集合并添加元素
        Map<String,String> map = new HashMap<>();
        map.put("1号丈夫","1号妻子");
        map.put("2号丈夫","2号妻子");
        map.put("3号丈夫","3号妻子");
        map.put("4号丈夫","4号妻子");
        map.put("5号丈夫","5号妻子");

        //首先要获取到所有的键值对对象。
        //Set集合中装的是键值对对象（Entry对象）
        //而Entry里面装的是键和值
        Set<Map.Entry<String, String>> entries = map.entrySet();
        for (Map.Entry<String, String> entry : entries) {
            //得到每一个键值对对象
            String key = entry.getKey();
            String value = entry.getValue();
            System.out.println(key + "---" + value);
        }
        
    }
}

4.3.3 forEach方法

public class MapDemo01 {

    public static void main(String[] args) {

        //创建集合并添加元素
        Map<String,String> map = new HashMap<>();

        map.put("1号丈夫","1号妻子");
        map.put("2号丈夫","2号妻子");
        map.put("3号丈夫","3号妻子");
        map.put("4号丈夫","4号妻子");
        map.put("5号丈夫","5号妻子");

        // 调用forEach方法进行遍历
        map.forEach( (key , value) -> {
            System.out.println(key + "---" + value);
        });

    }

}

4.4 HashMap原理

和HashSet底层原理一致。

4.5 练习题

需求：创建一个HashMap集合，键是学生对象(Student)，值是籍贯(String)。存储三个键值对元素，并遍历

要求：如果两个学生的年龄和姓名都是相同的，则认为是同一个对象

步骤：

1、创建一个学生类

2、创建HashMap集合对象

3、创建学生对象

4、把学生对象添加到集合中

5、遍历集合

代码实现：

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 String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", 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;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

}

测试类：

public class HashMapDemo01 {

    public static void main(String[] args) {

        HashMap<Student , String> hashMap = new HashMap<>() ;

        Student s1 = new Student("张三" , 23) ;
        Student s2 = new Student("李四" , 24) ;
        Student s3 = new Student("王五" , 25) ;
        Student s4 = new Student("王五" , 25) ;

        hashMap.put(s1 , "陕西") ;
        hashMap.put(s2 , "北京") ;
        hashMap.put(s3 , "上海") ;
        hashMap.put(s4 , "广州") ;

        hashMap.forEach( (key  , value) -> {
            String studentInfo = key.getName() + "----" + key.getAge() + "----" + value ;
            System.out.println(studentInfo);
        });

    }

}

4.6 TreeMap原理

和TreeSet底层原理一致

4.7 练习题

需求：创建一个TreeMap集合，键是学生对象(Student)，值是籍贯(String)。学生属性姓名和年龄，按照年龄进行排序并遍历。

排序条件：

主要条件：年龄

次要条件：姓名

步骤：

1、创建学生类

2、创建集合TreeMap对象，采用自然排序对学生进行排序

3、创建学生对象

4、把学生对象添加到集合中

5、遍历集合

代码：

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 boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public int compareTo(Student o) {
        int result = this.age - o.age;
        int result2 = result == 0 ? this.name.compareTo(o.name) : result ;
        return result2;
    }
}

测试类：

public class TreeMapDemo01 {

    public static void main(String[] args) {

        // 使用就是自然排序
        TreeMap<Student , String> treeMap = new TreeMap<>() ;

        Student s1 = new Student("张三" , 23) ;
        Student s2 = new Student("李四" , 12) ;
        Student s3 = new Student("王五" , 25) ;
        Student s4 = new Student("itheima" , 25) ;

        treeMap.put(s1 , "陕西西安") ;
        treeMap.put(s2 , "北京") ;
        treeMap.put(s3 , "上海") ;
        treeMap.put(s4 , "广州") ;

        treeMap.forEach( (student , value) -> {
            String studentInfo = student.getName() + "----" + student.getAge() + "----" + value ;
            System.out.println(studentInfo);
        });

    }

}

c void main(String[] args) {

    // 使用就是自然排序
    TreeMap<Student , String> treeMap = new TreeMap<>() ;

    Student s1 = new Student("张三" , 23) ;
    Student s2 = new Student("李四" , 12) ;
    Student s3 = new Student("王五" , 25) ;
    Student s4 = new Student("itheima" , 25) ;

    treeMap.put(s1 , "陕西西安") ;
    treeMap.put(s2 , "北京") ;
    treeMap.put(s3 , "上海") ;
    treeMap.put(s4 , "广州") ;

    treeMap.forEach( (student , value) -> {
        String studentInfo = student.getName() + "----" + student.getAge() + "----" + value ;
        System.out.println(studentInfo);
    });

}

}