1, Set set

1.Set set

1.1Set set overview and features

• Duplicate elements cannot be stored
• Without an index, you cannot use a normal for loop to traverse

1.2 use of set

Store string and traverse

public class MySet1 {
    public static void main(String[] args) {
      	//Create collection object
        Set<String> set = new TreeSet<>();
      	//Add element
        set.add("ccc");
        set.add("aaa");
        set.add("aaa");
        set.add("bbb");

//        for (int i = 0; i < set.size(); i++) {
//            //The Set collection has no index, so the method of getting elements by index cannot be used
//        }
      
      	//Traversal 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);
        }
    }
}

2.TreeSet set

2.1 overview and characteristics of TreeSet set

• Duplicate elements cannot be stored
• No index
• You can sort elements by rules
  • TreeSet(): sort according to the natural order of its elements
  • TreeSet (comparator): sort according to the specified comparator

2.2 basic usage of TreeSet set

Stores integers of type Integer and iterates through them

public class TreeSetDemo01 {
    public static void main(String[] args) {
        //Create collection object
        TreeSet<Integer> ts = new TreeSet<Integer>();

        //Add element
        ts.add(10);
        ts.add(40);
        ts.add(30);
        ts.add(50);
        ts.add(20);

        ts.add(30);

        //Traversal set
        for(Integer i : ts) {
            System.out.println(i);
        }
    }
}

2.3 use of natural sorting Comparable

• Case requirements

  • Store and traverse the student object, create a TreeSet collection, and use the parameterless construction method
  • Requirements: sort according to the age from small to large. If the age is the same, sort according to the alphabetical order of the name

• Implementation steps

  1. Create a TreeSet collection using an empty parameter construct
     • The TreeSet collection is used to store custom objects. The parameterless construction method uses natural sorting to sort elements
  2. The customized Student class implements the Comparable interface
     • Natural sorting is to let the class to which the element belongs implement the Comparable interface and override the compareTo(T o) method
  3. Rewrite the compareTo method in the interface
     • When rewriting a method, be sure to note that the collation must be written according to the required primary and secondary conditions

• code implementation

  Student class

  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) {
          //Sort by object's age
          //Main judgment conditions: sorted by age from small to large
          int result = this.age - o.age;
          //Secondary judgment condition: when the age is the same, sort according to the alphabetical order of the name
          result = result == 0 ? this.name.compareTo(o.getName()) : result;
          return result;
      }
  }
  

  Test class

  public class MyTreeSet2 {
      public static void main(String[] args) {
          //Create collection object
          TreeSet<Student> ts = new TreeSet<>();
  	    //Create student object
          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);
  		//Add students to collection
          ts.add(s1);
          ts.add(s2);
          ts.add(s3);
          ts.add(s4);
          ts.add(s5);
  		//Traversal set
          for (Student student : ts) {
              System.out.println(student);
          }
      }
  }
  

2.4 use of Comparator sorting Comparator

• Case requirements

  • Store the teacher object and traverse it, create a TreeSet collection, and construct the method with parameters
  • Requirements: sort according to the age from small to large. If the age is the same, sort according to the alphabetical order of the name

• Implementation steps

  • The user-defined objects are stored in the TreeSet collection. The construction method with parameters uses comparator sorting to sort the elements
  • Comparator sorting is to let the collection construction method receive the implementation class object of comparator and rewrite the compare(T o1,T o2) method
  • When rewriting a method, be sure to note that the collation must be written according to the required primary and secondary conditions

• code implementation

  Teacher class

  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 +
                  '}';
      }
  }
  

  Test class

  public class MyTreeSet4 {
      public static void main(String[] args) {
        	//Create collection object
          TreeSet<Teacher> ts = new TreeSet<>(new Comparator<Teacher>() {
              @Override
              public int compare(Teacher o1, Teacher o2) {
                  //o1 represents the element to be stored now
                  //o2 represents the element that has been stored in the collection
                
                  //Main conditions
                  int result = o1.getAge() - o2.getAge();
                  //minor criteria 
                  result = result == 0 ? o1.getName().compareTo(o2.getName()) : result;
                  return result;
              }
          });
  		//Create teacher object
          Teacher t1 = new Teacher("zhangsan",23);
          Teacher t2 = new Teacher("lisi",22);
          Teacher t3 = new Teacher("wangwu",24);
          Teacher t4 = new Teacher("zhaoliu",24);
  		//Add teacher to collection
          ts.add(t1);
          ts.add(t2);
          ts.add(t3);
          ts.add(t4);
  		//Traversal set
          for (Teacher teacher : ts) {
              System.out.println(teacher);
          }
      }
  }
  

2.5 summary of two comparison methods

• Summary of two comparison methods
  • Natural sorting: the user-defined class implements the Comparable interface, rewrites the compareTo method, and sorts according to the return value
  • Comparator sorting: when creating a TreeSet object, pass the comparator implementation class object, override the compare method, and sort according to the return value
  • When using, natural sorting is used by default. When natural sorting does not meet the current requirements, comparator sorting must be used
• Rules on return values in two ways
  • If the return value is negative, it means that the element currently stored is a small value, which is stored on the left
  • If the return value is 0, it means that the currently stored element is the same as the element in the collection and will not be saved
  • If the return value is a positive number, it means that the element currently stored is a large value, which is stored on the right

3. Data structure

3.1 binary tree

• Characteristics of binary tree

  • In a binary tree, the degree of any node should be less than or equal to 2
    • Node: in the tree structure, each element is called a node
    • Degree: the number of child nodes of each node is called degree

• Binary tree structure diagram

3.2 binary lookup tree

• Characteristics of binary search tree

  • Binary search tree, also known as binary sort tree or binary search tree
  • There are at most two child nodes on each node
  • The value of all nodes on the left subtree is less than that of the root node
  • The value of all nodes on the right subtree is greater than that of the root node

• Binary lookup tree structure diagram
  

• Binary search tree and binary tree comparison structure diagram

• Rules for adding nodes to binary lookup tree

  • The small one is on the left
  • The big one is on the right
  • The same does not exist

3.3 balanced binary tree

• Characteristics of balanced binary tree

  • The height difference between the left and right subtrees of a binary tree shall not exceed 1
  • The left and right subtrees of any node are a balanced binary tree

• Balanced binary tree rotation

  • Rotation trigger timing

    • When a node is added, the tree is no longer a balanced binary tree

  • Sinistral

    • It is to pull the right side of the root node to the left, change the original right child node into a new parent node, and transfer the redundant left child node to the degraded root node as the right child node

• Dextral

  • That is, pull the left side of the root node to the right, the left child node becomes a new parent node, and transfer the redundant right child node to the degraded root node as the left child node

  
  

• Comparison structure diagram of balanced binary tree and binary lookup tree

• Four cases of balanced binary tree rotation

  • Left left

    • Left: when a node is inserted into the left subtree of the left subtree of the root node, the binary tree is unbalanced

    • How to rotate: directly rotate the whole right
      

  • about

    • Left and right: when a node is inserted into the right subtree of the left subtree of the root node, the binary tree is unbalanced

    • How to rotate: first rotate left at the node position corresponding to the left subtree, and then rotate right on the whole

• Right right

  • Right: when a node is inserted into the right subtree of the right subtree of the root node, the binary tree is unbalanced

  • How to rotate: directly rotate the whole to the left

• Right left

  • Right left: when a node is inserted into the left subtree of the right subtree of the root node, the binary tree is unbalanced

  • How to rotate: first rotate right at the node position corresponding to the right subtree, and then rotate left on the whole

3.4 red black tree

• Characteristics of red black tree

  • Balanced binary B-tree
  • Each node can be red or black
  • The red black tree is not highly balanced. Its balance is realized through "its own red black rules"

• What are the red and black rules of red and black trees

  1. Each node is either red or black

  2. The root node must be black

  3. If a node has no child node or parent node, the corresponding pointer attribute value of the node is Nil. These Nils are regarded as leaf nodes, and each leaf node (Nil) is black

  4. If a node is red, its child nodes must be black (two red nodes cannot be connected)

  5. For each node, the simple path from the node to all its descendant leaf nodes contains the same number of black nodes

• The default color for adding nodes to a red black tree

  • When adding nodes, it defaults to red, which is efficient

  

• How to maintain red black rules after adding nodes to red black tree

  • Root node location
    • Straight to black
  • Non root node location
    • The parent node is black
      • No operation is required. The default color is red
    • The parent node is red
      • The uncle node is red
        1. Set the parent node to black and the uncle node to black
        2. Set the grandfather node to red
        3. If the grandfather node is the root node, the root node is turned black again
      • The node is black
        1. Set the parent node to black
        2. Set the grandfather node to red
        3. Rotate with the "grandfather node" as the fulcrum

3.5 ranking cases

• Case requirements

  • Use TreeSet set to store multiple student information (name, Chinese score, mathematics score, English score), and traverse the set
  • Requirements: appear from high to low according to the total score

• code implementation

  Student class

  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;
      }
  
      @Override
      public int compareTo(Student o) {
          // Main conditions: sort by total score
          int result = o.getSum() - this.getSum();
          // Secondary condition: if the total score is the same, it will be sorted according to the Chinese score
          result = result == 0 ? o.getChinese() - this.getChinese() : result;
          // If the Chinese scores are the same, they will be sorted according to the math scores
          result = result == 0 ? o.getMath() - this.getMath() : result;
          // If the total score is the same and the scores of all subjects are the same, they will be sorted by name
          result = result == 0 ? o.getName().compareTo(this.getName()) : result;
          return result;
      }
  }
  

  Test class

  public class TreeSetDemo {
      public static void main(String[] args) {
          //Create a TreeSet collection object and sort by comparator sorting
          TreeSet<Student> ts = new TreeSet<Student>();
          //Create student object
          Student s1 = new Student("jack", 98, 100, 95);
          Student s2 = new Student("rose", 95, 95, 95);
          Student s3 = new Student("sam", 100, 93, 98);
          //Add student object to collection
          ts.add(s1);
          ts.add(s2);
          ts.add(s3);
  
          //Traversal set
          for (Student s : ts) {
              System.out.println(s.getName() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + s.getSum());
          }
      }
  }
  

4.HashSet set

4.1 overview and characteristics of HashSet set

• The underlying data structure is a hash table
• Access disorder
• Duplicate elements cannot be stored
• Without an index, you cannot use a normal for loop to traverse

4.2 basic application of HashSet set

Store string and traverse

public class HashSetDemo {
    public static void main(String[] args) {
        //Create collection object
        HashSet<String> set = new HashSet<String>();

        //Add element
        set.add("hello");
        set.add("world");
        set.add("java");
        //A collection that does not contain duplicate elements
        set.add("world");

        //ergodic
        for(String s : set) {
            System.out.println(s);
        }
    }
}

4.3 hash value

• Introduction to hash values

  It is a numeric value of type int calculated by JDK according to the address or string or number of the object

• How to get hash value

  public int hashCode() in Object class: returns the hash code value of the Object

• Characteristics of hash value

  • The hashCode() method is called multiple times for the same object, and the returned hash value is the same
  • By default, different objects have different hash values. Rewriting the hashCode() method can make the hash values of different objects the same

4.4 hash table structure

• JDK1. Before 8

  Array + linked list

• JDK1. After 8

  • The number of nodes is less than or equal to 8

    Array + linked list

  • More than 8 nodes

    Array + red black tree

4.5 the HashSet set stores student objects and traverses them

• Case requirements

  • Create a collection to store student objects, store multiple student objects, and use the program to traverse the collection on the console
  • Requirement: if the member variable values of the student object are the same, we think it is the same object

• code implementation

  Student class

  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;
      }
  }
  

  Test class

  public class HashSetDemo02 {
      public static void main(String[] args) {
          //Create a HashSet collection object
          HashSet<Student> hs = new HashSet<Student>();
  
          //Create student object
          Student s1 = new Student("Lin Qingxia", 30);
          Student s2 = new Student("Zhang Manyu", 35);
          Student s3 = new Student("Wang Zuxian", 33);
  
          Student s4 = new Student("Wang Zuxian", 33);
  
          //Add students to collection
          hs.add(s1);
          hs.add(s2);
          hs.add(s3);
          hs.add(s4);
  
          //Traversal collection (enhanced for)
          for (Student s : hs) {
              System.out.println(s.getName() + "," + s.getAge());
          }
      }
  }
  

• summary

  The HashSet collection stores custom type elements. In order to realize the uniqueness of elements, the hashCode method and equals method must be overridden