Dark horse notes -- Set Series Collection

Catalog

1.Set Series collection

1.1Set Series collection overview

Set Series collection features

Set Set implementation class features

1.2HashSet The underlying principle of element disorder ： Hashtable

HashSet Underlying principle

Composition of hash table

Hash value

Object Class API

The hash value of the object

*HashSet1.7 Version principle analysis ： Array + Linked list   +（ Combined with hash algorithm ）

*JDK1.8 Version start HashSet Principle analysis

summary ：

4. When the array is full to 16*0.75=12 when , Automatically expand the capacity , Double the original capacity each time .

1.3HashSet The underlying principle of element de duplication

HashSet To repeat the principle analysis

Case study ：

1.4 Implementation class ：LinkedHashSet

LinkedHashSet Collection overview and features

1.5 Implementation class ：TreeSet

TreeSet Collection overview and features

TreeSet Set default rules

Custom collation

summary ：

2.Collection Characteristics of the system 、 Use scenario summary

3. Supplementary knowledge ： Variable parameters

4. Supplementary knowledge ： Collection tool class Collections

Collections Collection tool class

Collections frequently-used API

Collections Sort related API

5.Collection Comprehensive cases of the system

Case study ： The game called Fighting the Landlord

---

1.Set Series collection

1.1Set Series collection overview

 

Set Series collection features

disorder ： Access order is inconsistent .

No repetition ： You can get rid of duplication .

No index ： There's no way to index , So you can't use ordinary for Loop traversal , You can't get elements by index .

Set Set implementation class features

HashSet : disorder 、 No repetition 、 No index .

LinkedHashSet： Orderly 、 No repetition 、 No index .

TreeSet： Sort 、 No repetition 、 No index .

Set The function of the set is basically the same as Collection Of API Agreement .

1.2HashSet The underlying principle of element disorder ： Hashtable

HashSet Underlying principle

HashSet The bottom layer of the collection takes the data stored in the hash table .

Hash table is a structure with good performance for adding, deleting, modifying and querying data .

Composition of hash table

JDK8 Previous , Array is used at the bottom + The list consists of

JDK8 After start , Array is used at the bottom + Linked list + Red and black trees make up .

Hash value

yes JDK According to the address of the object , Calculated according to some rule int Type value .

Object Class API

public int hashCode​()： Returns the hash value of the object

The hash value of the object

The same object is called more than once hashCode() Method returns the same hash value

By default , Different objects have different hash values .

*HashSet1.7 Version principle analysis ： Array + Linked list   +（ Combined with hash algorithm ）

  The rules ：

Create a default length 16 Array of , Array name table

Calculate the storage location according to the hash value of the element and the length of the array （ The hash algorithm ）.

Judge whether the current position is null, If it is null Deposit directly into .

If the position is not null, Indicates that there are elements , Call equals Methods to compare

If the same , Then it doesn't exist , If it's not the same , Then it is stored in the array ：

1.JDK 7 The new element occupies the position of the old element , Point to the old element

2.JDK 8 Chinese and new elements hang under the old elements

Conclusion ： Hash table is a structure with good performance for adding, deleting, modifying and querying data .

*JDK1.8 Version start HashSet Principle analysis

The underlying structure ： Hashtable （ Array 、 Linked list 、 A combination of red and black trees ）

When there is too much data hanging under the element , Query performance degradation , from JDK8 After start , When the chain length exceeds 8 When , Automatically convert to red black tree .

Conclusion ：JDK8 After start , The introduction of hash table to red black tree further improves the performance of operating data .

summary ：

1.Set What is the underlying principle of set ？

JDK8 Previous , Hashtable ： Array is used at the bottom + The list consists of

JDK8 After start , Hashtable ： Array is used at the bottom + Linked list + Red and black trees make up .

2. Detailed flow of hash table

1. Create a default length 16, Default load because 0.75 Array of , Array name table.

2. Calculate the location that should be stored according to the hash value of the element and the length of the array .

3. Judge whether the current position is null, If it is null Deposit directly into , If the position is not null, Indicates that there are elements ,  Call equals Method to compare property values , If the same , Then it doesn't exist , If it's not the same , Then it is stored in the array .

4. When the array is full to 16*0.75=12 when , Automatically expand the capacity , Double the original capacity each time .

1.3HashSet The underlying principle of element de duplication

HashSet To repeat the principle analysis

 

1. Create a default length 16 Array of , Array name table.

2. Calculate the storage location according to the hash value of the element and the length of the array （ The hash algorithm ）.

3. Judge whether the current position is null, If it is null Deposit directly into .

4. If the position is not null, Indicates that there are elements , Call equals Methods to compare , If the same , Then it doesn't exist , If it's not the same , Then it is stored in the array .

Conclusion ： If you want to Set The group thinks 2 An object with the same content is repeated , Must override the object's hashCode() and equals() Method .

Case study ：

demand ： Create a collection of student objects , Store multiple student objects , Use the program implementation to traverse the collection in the console , requirement ： The member variable values of the student object are the same , We think it's the same object

analysis ：

Define the student class , establish HashSet A collection of objects , Create student objects ;

Add students to the collection ;

Rewrite two methods in the student class ,hashCode() and equals(), Automatically generated ;

Ergodic set ( enhance for).

import java.util.Objects;

public class Student {
    private String name;
    private int age;
    private char sex;

    public Student() {
    }

    public Student(String name, int age, char sex) {
        this.name = name;
        this.age = age;
        this.sex = sex;
    }

    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 char getSex() {
        return sex;
    }

    public void setSex(char sex) {
        this.sex = sex;
    }

    /**
        as long as 2 The content of each object is the same , The result must be true
     * @param o
     * @return
     */
    @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 && sex == student.sex && Objects.equals(name, student.name);
    }

    /**
     s1 = new Student(" All right ", 20, ' male ')
     s2 = new Student(" All right ", 20, ' male ')
     s3 = new Student(" Zhou Xiong ", 21, ' male ')
     */
    @Override
    public int hashCode() {
        return Objects.hash(name, age, sex);
    }

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

import java.util.HashSet;
import java.util.Set;

/**
     The goal is ： Give Way Set Set removes one object of duplicate content （ To repeat ）
 */
public class SetDemo3 {
    public static void main(String[] args) {
        // Set Gather to repeat the reason ： First, judge whether the storage location calculated by the hash value is the same   To determine equals
        Set<Student> sets = new HashSet<>();

        Student s1 = new Student(" All right ", 20, ' male ');
        Student s2 = new Student(" All right ", 20, ' male ');
        Student s3 = new Student(" Zhou Xiong ", 21, ' male ');
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
        System.out.println(s3.hashCode());

        sets.add(s1);
        sets.add(s2);
        sets.add(s3);

        System.out.println(sets);
    }

summary ： If you want to Set The group thinks 2 What should I do if an object with the same content is repeated ？

overridden hashCode and equals Method .

1.4 Implementation class ：LinkedHashSet

LinkedHashSet Collection overview and features

Orderly 、 No repetition 、 No index .

Ordering here refers to ensuring that the stored and extracted elements are in the same order

principle ： The underlying data structure is a hash table , But each element has an additional double linked list mechanism to record the storage order .

  summary ：

LinkedHashSet What are the characteristics and principles of sets ？

Orderly 、 No repetition 、 No index

The bottom layer is based on the hash table , Use the double linked list to record the adding order .

1.5 Implementation class ：TreeSet

TreeSet Collection overview and features

No repetition 、 No index 、 Sortable

Sortable ： In ascending order by default according to the size of the elements （ From small to large ） Sort .

TreeSet The bottom layer of the collection is based on Data structure of red black tree To achieve sorting , The performance of addition, deletion, modification and query is good .

Be careful ：TreeSet Collections must be sorted , You can sort the elements according to the specified rules .

TreeSet Set default rules

For numeric types ：Integer , Double, The official default is to sort in ascending order by size .

For string types ： By default, it is sorted in ascending order according to the number of the first character .

For custom types such as Student object ,TreeSet Cannot sort directly .

Conclusion ： Want to use TreeSet Store custom types , You need to make sorting rules

Custom collation

TreeSet When storing objects in a collection, there are 2 There are two ways to design custom comparison rules

1. Let the custom class （ Such as students ） Realization Comparable Interface rewriting compareTo Method to customize comparison rules .

2.TreeSet Set has a parameter constructor , You can set Comparator The comparator object corresponding to the interface , To customize the comparison rules .

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

/**
    The goal is ： Observe TreeSet How to sort data with value characteristics .
         Learn to sort objects of user-defined types by specified rules 
 */
public class SetDemo5 {
    public static void main(String[] args) {
        //  Mode two ： Set its own comparator object to customize rules 
        //
//        Set<Apple> apples = new TreeSet<>(new Comparator<Apple>() {
//            @Override
//            public int compare(Apple o1, Apple o2) {
//                // return o1.getWeight() - o2.getWeight(); //  Ascending 
//                // return o2.getWeight() - o1.getWeight(); //  Descending 
//                //  Be careful ： Floating point type is recommended to be used directly Double.compare Compare 
//                // return Double.compare(o1.getPrice() , o2.getPrice()); //  Ascending 
//                return Double.compare(o2.getPrice() , o1.getPrice()); //  Descending 
//            }
//        });


        Set<Apple> apples = new TreeSet<>(( o1,  o2) ->  Double.compare(o2.getPrice() , o1.getPrice())  );
        apples.add(new Apple(" Red Fuji ", " Red ", 9.9, 500));
        apples.add(new Apple(" green apple ", " green ", 15.9, 300));
        apples.add(new Apple(" Green apple ", " Cyan ", 29.9, 400));
        apples.add(new Apple(" Yellow apple ", " yellow ", 9.8, 500));
        System.out.println(apples);
    }
}

public class Apple implements Comparable<Apple>{
    private String name;
    private String color;
    private double price;
    private int weight;

    public Apple() {
    }

    public Apple(String name, String color, double price, int weight) {
        this.name = name;
        this.color = color;
        this.price = price;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Apple{" +
                "name='" + name + '\'' +
                ", color='" + color + '\'' +
                ", price=" + price +
                ", weight=" + weight +
                '}';
    }

    /**
       Mode one ： Class custom comparison rules 
      o1.compareTo(o2)
     * @param o
     * @return
     */
    @Override
    public int compareTo(Apple o) {
        //  Compare by weight 
        return this.weight - o.weight ; //  Remove duplicate elements 
        // return this.weight - o.weight >= 0 ? 1 : -1; //  Keep the elements with repeated weight 
    }
}

In two ways , Rules about return values ：

If you think the first element is greater than the second element, you can return a positive integer .

If you think the first element is smaller than the second element, you can return a negative integer .

If you think the first element is equal to the second element, return 0 that will do , here Treeset The collection will retain only one element , Think the two are repeated .

Be careful ： If TreeSet The objects stored in the collection have implementation comparison rules , The set also comes with its own comparator , By default, the set's own comparator is used for sorting .

summary ：

1.TreeSet What are the characteristics of sets ？

Sortable 、 No repetition 、 No index

The bottom layer implements sorting based on red black tree , The performance of adding, deleting, modifying and checking is good

2.TreeSet There are several ways to customize sorting rules for collections

2 Kind of , Class implementation Comparable Interface , Rewrite the comparison rules , Collection customization Comparator Comparator object , Rewrite the comparison rules .

2.Collection Characteristics of the system 、 Use scenario summary

If you want the element to repeat , Another index , Index query should be fast ？

use ArrayList aggregate , array-based .（ Most used ）

  If you want the element to repeat , Another index , The operation of adding and deleting the beginning and end is fast ？

use LinkedList aggregate , Linked list based data mining .

If you want to add, delete, modify and check quickly , But the elements don't repeat 、 disorder 、 No index .

use HashSet aggregate , Hash table based .

If you want to add, delete, modify and check quickly , But the elements don't repeat 、 Orderly 、 No index .

use LinkedHashSet aggregate , Based on hash table and double linked list .

If you want to sort objects .

use TreeSet aggregate , Based on the red black tree . You can also use List The collection implements sorting .

3. Supplementary knowledge ： Variable parameters

Variable parameters

Variable parameters are used in formal parameters and can receive multiple data .

Format of variable parameters ： data type ... Parameter name

The role of variable parameters

The transmission parameters are very flexible , convenient . Parameters may not be transmitted , It can transmit 1 One or more , You can also transfer an array

Variable parameters are essentially an array inside a method .

Note on variable parameters ：

1. There can only be one variable parameter in a formal parameter list

2. Variable parameters must be placed at the end of the formal parameter list

import java.util.Arrays;

/**
     The goal is ： Variable parameters .

     Variable parameters are used in formal parameters and can receive multiple data .
     Format of variable parameters ： data type ... Parameter name 

     The role of variable parameters ：
          The transmission parameters are very flexible , convenient .
          Parameters may not be transmitted .
          You can transfer a parameter .
          Multiple parameters can be transferred .
          You can transfer an array .

      Variable parameters are essentially an array inside a method .
      Note on variable parameters ：
         1. There can only be one variable parameter in a formal parameter list ！！
         2. Variable parameters must be placed at the end of the formal parameter list ！！
      Summary ：
         remember .
 */
public class MethodDemo {
    public static void main(String[] args) {

        sum(); // 1、 Don't pass parameters 
        sum(10); // 2、 You can transfer a parameter 
        sum(10, 20, 30); // 3、 Multiple parameters can be transferred 
        sum(new int[]{10, 20, 30, 40, 50}); // 4、 You can transfer an array 
    }

    /**
        Be careful ： There can only be one variable parameter in a formal parameter list , Variable parameters must be placed at the end of the formal parameter list 
     * @param nums
     */
    public static void sum(  int...nums){
        //  Be careful ： Variable parameters are actually an array inside the method . nums
        System.out.println(" Element number ：" + nums.length);
        System.out.println(" Element content ：" + Arrays.toString(nums));
    }
}

4. Supplementary knowledge ： Collection tool class Collections

Collections Collection tool class

java.utils.Collections: It's a collection tool class

effect ：Collections Does not belong to a collection , Is a tool class used to manipulate collections .

Collections frequently-used API

Collections Sort related API

Using range ： Only for List Sorting of sets .

sort order 1：

sort order 2：

 

import java.util.*;

/**
     The goal is ：Collections Use of tool class .

    java.utils.Collections: It's a collection tool class 
    Collections Does not belong to a collection , Is a tool class used to manipulate collections .
    Collections There are several commonly used API:
         - public static <T> boolean addAll(Collection<? super T> c, T... elements)
              Batch add elements to collection objects ！
         - public static void shuffle(List<?> list) : Disorganize the order of assembly .
         - public static <T> void sort(List<T> list): Sort the elements in the collection according to the default rules .
         - public static <T> void sort(List<T> list,Comparator<? super T> c): Sort the elements in the collection according to the specified rules .
 */
public class CollectionsDemo01 {
    public static void main(String[] args) {
        List<String> names = new ArrayList<>();
        //names.add(" Chu liuxiang ");
        //names.add(" hu tiehua ");
        //names.add(" zhang wuji ");
        //names.add(" Luk siu fung ");
        Collections.addAll(names, " Chu liuxiang "," hu tiehua ", " zhang wuji "," Luk siu fung ");
        System.out.println(names);

        // 2、public static void shuffle(List<?> list) : Disorganize the order of assembly .
        Collections.shuffle(names);
        System.out.println(names);

        // 3、 public static <T> void sort(List<T> list): Sort the elements in the collection according to the default rules . （ Elements of the row value property ）
        List<Integer> list = new ArrayList<>();
        Collections.addAll(list, 12, 23, 2, 4);
        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);
    }
}

public class Apple implements Comparable<Apple>{
    private String name;
    private String color;
    private double price;
    private int weight;

    public Apple() {
    }

    public Apple(String name, String color, double price, int weight) {
        this.name = name;
        this.color = color;
        this.price = price;
        this.weight = weight;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public double getPrice() {
        return price;
    }

    public void setPrice(double price) {
        this.price = price;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "Apple{" +
                "name='" + name + '\'' +
                ", color='" + color + '\'' +
                ", price=" + price +
                ", weight=" + weight +
                '}';
    }

    /**
       Mode one ： Class custom comparison rules 
      o1.compareTo(o2)
     * @param o
     * @return
     */
    @Override
    public int compareTo(Apple o) {
        //  Compare by weight 
        return this.weight - o.weight ; // List Set stores elements of the same size   Will retain ！
    }
}

import java.util.*;

/**
     The goal is ： Sort of reference data types .

     Strings are sorted in ascending order by the number of the first character ！

     Comparison method of custom types API:Collections
         - public static <T> void sort(List<T> list):
                Sort the elements in the collection according to the default rules .
                People don't know how to sort custom reference types , Direct error ！

         - public static <T> void sort(List<T> list,Comparator<? super T> c):
                 Sort the elements in the collection according to the specified rules , Built in comparator 
 */
public class CollectionsDemo02 {
    public static void main(String[] args) {
        List<Apple> apples = new ArrayList<>(); //  Can be repeated ！
        apples.add(new Apple(" Red Fuji ", " Red ", 9.9, 500));
        apples.add(new Apple(" green apple ", " green ", 15.9, 300));
        apples.add(new Apple(" Green apple ", " Cyan ", 29.9, 400));
        apples.add(new Apple(" Yellow apple ", " yellow ", 9.8, 500));

//        Collections.sort(apples); //  Method 1 ： Tolerable ,Apple Class has overridden the comparison rule 
//        System.out.println(apples);

        //  Mode two ：sort Method has its own comparator object 
//        Collections.sort(apples, new Comparator<Apple>() {
//            @Override
//            public int compare(Apple o1, Apple o2) {
//                return Double.compare(o1.getPrice() , o2.getPrice()); //  Sort by price ！！
//            }
//        });

        Collections.sort(apples, ( o1,  o2) ->  Double.compare(o1.getPrice() , o2.getPrice()) );
        System.out.println(apples);

    }
}

5.Collection Comprehensive cases of the system

Case study ： The game called Fighting the Landlord

demand ：

When starting the game room , Should be prepared in advance 54 card , Finish shuffling 、 Licensing 、 Card sorting 、 Logic .

analysis ：

1. When the system starts up and data needs to be prepared , You can use static code blocks .

2. Shuffling is to disrupt the order of cards .

3. Define three players 、 In turn 51 card

4. Sort players' cards ( expand )

5. Output the card data of each player .

public class Card {
    private String size;
    private String color;
    private int index; //  The real size of the card 

    public Card(){
    }

    public Card(String size, String color, int index) {
        this.size = size;
        this.color = color;
        this.index = index;
    }

    public String getSize() {
        return size;
    }

    public void setSize(String size) {
        this.size = size;
    }

    public String getColor() {
        return color;
    }

    public void setColor(String color) {
        this.color = color;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }

    @Override
    public String toString() {
        return size + color;
    }
}

import java.util.*;

/**
     The goal is ： Landlords game case development .

     Business needs analysis :
         Playing cards against landlords ,  Shuffle ,  Licensing ,  Sort （ Expand knowledge ）,  Look at cards .
         Business :  All in all 54 card .
         points : "3","4","5","6","7","8","9","10","J","Q","K","A","2"
         Design and color : "", "", "", ""
         Big and small king : "" , ""
         The points should be combined separately 4 Plant designs , One for each king .
         fight against landlords ： issue 51 card , be left over 3 As a card .

     function ：
        1. Make cards .
        2. Shuffle .
        3. Definition 3 Players 
        4. Licensing .
        5. Sort （ expand , understand , Homework ）
        6. Look at cards 
 */
public class GameDemo {
    /**
      1、 Define a static collection storage 54 Card object 
     */
     public static List<Card> allCards = new ArrayList<>();

    /**
      2、 Make cards ： Define static code block initialization card data 
     */
    static {
        // 3、 Define the number of points ： The number is determined , Type determination , Using arrays 
        String[] sizes = {"3","4","5","6","7","8","9","10","J","Q","K","A","2"};
        // 4、 Define decor ： The number is determined , Type determination , Using arrays 
        String[] colors = {"", "", "", ""};
        // 5、 Combine points and decors 
        int index = 0; //  The size of the record board 
        for (String size : sizes) {
            index++;
            for (String color : colors) {
                // 6、 Encapsulated into a card object .
                Card c = new Card(size, color, index);
                // 7、 Put it into the collection container 
                allCards.add(c);
            }
        }
        // 8  The size king is stored in the collection object  "" , ""
        Card c1 = new Card("" ,  "", ++index);
        Card c2 = new Card("" ,  "",++index);
        Collections.addAll(allCards , c1 , c2);
        System.out.println(" New card ：" + allCards);
    }

    public static void main(String[] args) {
        // 9、 Shuffle 
        Collections.shuffle(allCards);
        System.out.println(" After the shuffle ：" + allCards);

        // 10、 Licensing （ Define three players , Each player's card is also a collection container ）
        List<Card> linhuchong = new ArrayList<>();
        List<Card> jiumozhi = new ArrayList<>();
        List<Card> renyingying = new ArrayList<>();

        // 11、 Start to deal （ Issue from the card set 51 Cards are given to three players , The remaining 3 As a card ）
        // allCards = [, A, 5, 2, 2, Q, , Q ...
        //    i        0  1   2   3   4   5    6  7      %  3
        for (int i = 0; i < allCards.size() - 3; i++) {
            //  Get the current card object first 
            Card c = allCards.get(i);
            if(i % 3 == 0) {
                //  Please take the card with ah Chong 
                linhuchong.add(c);
            }else if(i % 3 == 1){
                //  Please ah Jiu 
                jiumozhi.add(c);
            }else if(i % 3 == 2){
                //  Please accept the card 
                renyingying.add(c);
            }
        }

        // 12、 Get the last three cards ( Cut the last three cards into a subset )
        List<Card> lastThreeCards = allCards.subList(allCards.size() - 3 , allCards.size());

        // 13、 Sort players' cards （ From big to small   You can try how to achieve it yourself ）
        sortCards(linhuchong);
        sortCards(jiumozhi);
        sortCards(renyingying);

        // 14、 Output player's cards ：
        System.out.println(" Ah, rush ：" + linhuchong);
        System.out.println(" Ah dove ：" + jiumozhi);
        System.out.println(" Yingying ：" + renyingying);
        System.out.println(" Three cards ：" + lastThreeCards);
    }

    /**
        Sort cards 
     * @param cards
     */
    private static void sortCards(List<Card> cards) {
        // cards = [J, A, 3, , 5, Q, 2
        Collections.sort(cards, new Comparator<Card>() {
            @Override
            public int compare(Card o1, Card o2) {
                // o1 = J
                // o2 = A
                //  Know the size of the card , Rules can be specified 
                return o2.getIndex() - o1.getIndex();
            }
        });
    }

}