Set. Disorder, No Repetition

HashSet

Features: There is no duplicate data, and the data is not output in the order of storage.

Create collection usage code:

Set<String> s = new HashSet<>();

Code demonstration: Common methods and traversal output

import java.util.*;
public class TestHashSet {
    public static void main(String[] args) {
        m010 assignment And ergodic();
    }
    public static void m010 assignment And ergodic() {
        System.out.println("=====assignment And ergodic");
        Set<String> s = new HashSet<>();
        s.add("Sun WuKong");
        s.add("Little White Dragon");
        s.add("Zhu Bajie");
        s.add("Sha Wujing");
        s.add("Sun WuKong");
        System.out.println("Is it empty?:" + s.isEmpty());
        System.out.println("Does it include:" + s.contains("Little White Dragon"));
        System.out.println("remove:" + s.remove("Little White Dragon"));
        // (1)foreach: traversal set
        for (String str : s) {
            System.out.println(str);
        }
        // (2) Iterator: traversal set
        Iterator<String> it = s.iterator();
        while (it.hasNext()) {
            String str = it.next();
            System.out.println("Iterator : " + str);
        }
        // (3)*Java 8 new traversal method
        s.forEach(elm -> System.out.println("Lambda:" + elm));
    }
}

Hash and Hash tables

Hash

HashCode, a decimal integer, is the address value of the object (logical address, not physical address)
The Object class has a method to get the Hash value of the object.

public native int hashCode();

String rewrites the hashCode method

    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

So that some hashCode s of different strings are equal (strings or unequal, whether== or equals):

        System.out.println("Heavy land".hashCode());
        System.out.println("Conversation".hashCode());
        System.out.println("--------------");
        System.out.println("Aspect".hashCode());
        System.out.println("Tree man".hashCode());
        System.out.println("--------------");
        System.out.println("children".hashCode());
        System.out.println("Nong Fung".hashCode());
        System.out.println("--------------");
        System.out.println("Ea".hashCode());
        System.out.println("FB".hashCode());

Hash table

Before Java 8: Hash tables used arrays + linked lists;
After Java 8, red and black trees were added to speed up queries.

The schematic diagram of the Hash table structure is as follows:

How is duplication?

In HashSet, the element does not repeat "equals method is more true, and hashCode is different".

In the following example code, only objects with equals true and hashCode identical are not duplicated in the Set.

import java.util.*;
class A_equalsT {
    public boolean equals(Object obj) {
        return true;
    }
}
class B_hash1 {
    public int hashCode() {
        return 1;
    }
}
class C_hash2_equalsT {
    public int hashCode() {
        return 2;
    }
    public boolean equals(Object obj) {
        return true;
    }
}
public class TestSet How is repetition? {
    public static void main(String[] args) {
        Set<Object> _set = new HashSet<Object>();
        _set.add(new A_equalsT());
        _set.add(new A_equalsT());
        _set.add(new B_hash1());
        _set.add(new B_hash1());
        _set.add(new C_hash2_equalsT());
        _set.add(new C_hash2_equalsT());
        for (Object object : _set) {
            System.out.println(object);
        }
    }
}

Running results: (C_hash2_equalsT saves only one copy, indicating that it is regarded as a duplicate object)

B_hash1@1
B_hash1@1
C_hash2_equalsT@2
A_equalsT@15db9742
A_equalsT@6d06d69c

When HashSet stores custom elements, it is necessary to override hashCode and equals methods to ensure the uniqueness of objects in the collection.

Practice:

To create a Student class, you need to include at least ID and name. Create multiple Student objects to join HashSet, and do not repeat if the number (id) is the same.

TreeSet

TreeSet supports two sorts, natural sort and custom sort. The default is natural sort, which is different from the output order of HashSet.

TreeSet uses a red-black tree to store elements (together with the examples and the next section).

LinkedHashSet

Sets can also be ordered, and the LinkedHashSet can output results in input order.

LinkedHashSet also determines the storage location of elements based on the hashCode value of elements, but adds a linked list to record the storage order of elements, which makes elements orderly.

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
public class TestTree{
    public static void main(String[] args) {
        m020 Various Set();
    }
    private static void m020 Various Set() {
        System.out.println("|-HashSet: ");
        Set<String> _set;
        _set = new HashSet<String>();
        _set.add("B");
        _set.add("A");
        _set.add("1");
        _set.add("2");
        _set.add(null);
        printSet(_set);
        System.out.println("|-TreeSet No null value is accepted:");
        _set = new TreeSet<String>();
        _set.add("B");
        _set.add("A");
        _set.add("1");
        _set.add("2");
        // _set.add(null);
        printSet(_set);
        System.out.println("|-LinkedHashSet:order");
        _set = new LinkedHashSet<String>();
        _set.add("B");
        _set.add("A");
        _set.add("1");
        _set.add("2");
        _set.add(null);
        printSet(_set);
    }
    private static void printSet(Set<String> _set) {
        for (String str : _set) {
            System.out.print(str + " ");
        }
        System.out.println();
    }
}

|-HashSet:
null A 1 B 2
|-TreeSet No null value is accepted:
1 2 A B
|-LinkedHashSet:order
B A 1 2 null

Performance of Set

HashSet is the most efficient and LinkedHashSet traverses faster because of its linked list. TreeSet is inefficient because it maintains red and black trees.