Collection sub interface 2: Set interface and TreeSet interface

1, Set interface:

1. Characteristics of stored data: disordered and unrepeatable elements
concrete:
Take HashSet as an example:
1. Disorder: not equal to randomness. The stored data is not added in the order of array index in the underlying array, but determined according to the hash value of the data.
2. Non repeatability: ensure that the added element cannot return true when judged by equals() That is, only one element can be added to the same element.


2. Element adding process: (take HashSet as an example)
We add element a to the HashSet. First, we call the hashCode() method of the class where element a is located to calculate the hash value of element a,
This hash value then calculates the storage position in the underlying array of HashSet (i.e. index position, judgment) through some algorithm
Whether the array has elements at this position:
If there are no other elements in this position, element a is added successfully. ---- > Case 1
If there are other elements b (or multiple elements in the form of linked list) in this position, compare the hash values of element a and element b:
If the hash values are different, element a is added successfully. ---- > Situation 2
If the hash values are the same, you need to call the equals() method of the class where element a is located:
equals() returns true, adding element a failed
If equals() returns false, element a is added successfully. ---- > Situation 3

For cases 2 and 3 of successful addition: element a and the data already existing at the specified index position are stored in a linked list.
jdk 7: put element a into the array and point to the original element.
jdk 8: the original element is in the array and points to element a
Conclusion: seven up and eight down

HashSet bottom layer: array + linked list structure. (premise: jdk7)


3. Common methods
There are no new methods defined in the Set interface, but all the methods declared in the Collection are used.

4. Common implementation classes:
|----Collection interface: single column collection, used to store objects one by one
* |--- Set interface: store unordered and unrepeatable data -- > high school talk about "Set"
* |--- HashSet: as the main implementation class of Set interface; Thread unsafe; null values can be stored
* |--- LinkedHashSet: as a subclass of HashSet; When traversing its internal data, it can be traversed in the order of addition
While adding data, each data also maintains two references to record the previous data and the latter data of this data. The traversal efficiency of hashedset is higher than that of hashedset.linkset for frequent operations

* |--- TreeSet: you can sort according to the specified attributes of the added object.

5. Requirements for storage object class:
HashSet/LinkedHashSet:

Requirement: the class of data added to set (mainly HashSet and LinkedHashSet) must override hashCode() and equals()
Requirement: the rewritten hashCode() and equals() should be consistent as much as possible: equal objects must have equal hash codes
*Tip for rewriting two methods: the Field in the object used as the comparison of the equals() method should be used to calculate the hashCode value.
*

II Use of TreeSet

 

TreeSet:
1. In natural sorting, the standard for comparing whether two objects are the same is: compareTo() returns 0 No longer equals()
2. In custom sorting, the standard for comparing whether two objects are the same is: compare() returns 0 No longer equals()

 

6.1 instructions:
1. The data added to TreeSet must be objects of the same class.
2. Two sorting methods: natural sorting (realizing Comparable interface) and customized sorting (Comparator)

package main.exer;

/**
 * @Author lx
 * @Description
 * @Date 21:27 2020/8/14
 * @Version
 */
public class Employee implements Comparable{
    private String name;
    private int age;
    private MyDate birthday;

    public Employee() {
    }

    public Employee(String name, int age, MyDate birthday) {
        this.name = name;
        this.age = age;
        this.birthday = birthday;
    }

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

    public MyDate getBirthday() {
        return birthday;
    }

    public void setBirthday(MyDate birthday) {
        this.birthday = birthday;
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", birthday=" + birthday +
                '}';
    }

    @Override
    public int compareTo(Object o) {
        if (o instanceof Employee){
            Employee empl = (Employee) o;
            return this.name.compareTo(empl.name);
        }else
            return 0;
    }
}

 

package main.exer;

import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

/**
 * @Author lx
 * @Description
 * @Date 21:43 2020/8/14
 * @Version
 */
public class Test2 {
    public static void main(String[] args) {

        TreeSet set = new TreeSet(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Employee && o2 instanceof Employee) {
                    Employee e1 = (Employee) o1;
                    Employee e2 = (Employee) o2;

                    MyDate b1 = e1.getBirthday();
                    MyDate b2 = e2.getBirthday();

                    int minusYear = b1.getYear() - b2.getYear();
                    if (minusYear != 0) {
                        return minusYear;
                    }
                    int minusMonth = b1.getMonth() - b2.getMonth();
                    if (minusMonth != 0) {
                        return minusMonth;
                    }
                    int minusDay = b1.getDay() - b2.getDay();
                    if (minusDay != 0) {
                        return minusDay;
                    }

                }
                return 0;
            }
        });

        Employee emp1 = new Employee("lihua", 24, new MyDate(1998, 6, 8));
        Employee emp2 = new Employee("zhangchun", 28, new MyDate(1998, 6, 5));
        Employee emp3 = new Employee("liuai", 18, new MyDate(2001, 3, 7));
        Employee emp4 = new Employee("yangguang", 26, new MyDate(1994, 5, 9));


        set.add(emp1);
        set.add(emp2);
        set.add(emp3);
        set.add(emp4);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

    }

}

 

Posted by chrispols on Mon, 23 May 2022 07:59:35 +0300