Set interface

Basic introduction

Note: the removal sequence is fixed and will not change. Traversal method: iterator, enhanced for, cannot use for loop, because there is no index and no get method. Demonstrate with HashSet.

HashSet

The bottom layer is HashMap # using the Hash + equals method

    public HashSet() {
        map = new HashMap<>(); //Create a HashMap
    }

General idea of HashSet add method:

   1. First obtain the hash value of the element (hashCode method) 2 The hash value is calculated to obtain an index value, which is the position number to be stored in the hash table. 3. If there are no other elements in this position, store them directly. 4. If there are other elements in this position, you need to judge equals. If they are equal, they will not be added. If they are not equal, they are added in the form of a linked list.   

Among them, PRESENT is an Object object, which only plays the role of placeholder.

Key is the entered keyword, and value is PRESENT. The hash method calculates the hash value of the key. Note that the hashCode method is not simply called, but the pseudo hash value calculated by XOR with H > > > 16. Finally, the index is calculated by bitwise sum in the putVal method.

The key point is to understand the putVal method. Look at the source code yourself. Only the description is written here. The resize method is used to modify the size of the Node array. afterNodeInsertion(evict) is of no practical use and is a method left to subclass implementation.

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;  
        //Table is an attribute of HashMap and an array of nodes. At first, the table is null. resize initializes the tab and expands it to 16 spaces
        if ((p = tab[i = (n - 1) & hash]) == null) //Calculate the real index and assign the corresponding position to p
            tab[i] = newNode(hash, key, value, null); //If p is empty, there is no element. Create a node and put the content in it.
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
        //The hash value of the key to be added is the same as the hash value of the first node of the linked list corresponding to the current index position.
        //And meet one of the following two conditions: 1 The key of the Node pointed to by P and the key to be added are the same object
                            2. p directive Node Nodal key use equals Methods and methods to be added key Same after comparison
        //You can't join at this time. e points to p without any processing
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // If p is a red black tree, call the putTreeVal method to join
            else {
        // The last case shows that although the location is occupied, it is different from the first element node. Find the linked list corresponding to the first element node  
                for (int binCount = 0; ; ++binCount) { //Start traversing the linked list
                    if ((e = p.next) == null) {  
                        p.next = newNode(hash, key, value, null);// After comparing with each element of the linked list in turn, if it is different (to the last node), it will be added to the last node of the linked list
                        if (binCount >= TREEIFY_THRESHOLD - 1) // Note that after adding elements to the linked list, judge whether the linked list has reached 8 nodes (i.e. > = 7)
                            treeifyBin(tab, hash);// If it has reached, treeifyBin() is called. In this method, first judge if (tab = = null | (n = tab. Length) < min_ TREEIFY_ Capability) is to see whether the table is empty or less than 64. If so, expand the capacity of the table first. If not, it will turn into a red black tree.
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
         // In the process of comparing with each element of the linked list, if there is the same situation, break directly (the judgment conditions are the same as those above)
                    p = e;
                }
            }
            if (e != null) { // Description: there are duplicate elements (mainly for HashMap, used for overwriting)
                V oldValue = e.value; //Both record value and HashSet are PRESENT, but HashMap is defined by itself
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value; //If the HashMap needs to be overwritten, the HashSet does not need to be overwritten because the PRESENT is null
                afterNodeAccess(e);
                return oldValue; //add failed (not null)
            }
        }
        ++modCount; //Record modification times
        if (++size > threshold) //In the resize method, threshold is the critical value of the table (initial 12)
            resize(); //If the size is greater than the critical value, expand the capacity
        afterNodeInsertion(evict);//The method left for subclass implementation is an empty method for HashMap
        return null;//Return null success
    }

One thing to pay attention to: two opportunities for table expansion - 1 Greater than the critical value ﹤ 2 The linked list has more than 8 nodes

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize(); // Some codes of treeifyBin
              // This tells us that if there are more than 8 nodes on the linked list, but the table has not reached 64, the capacity will be expanded first

Rewrite the method to determine whether to join

You need to override the equals method and hashCode method of the Employee class (enter equals directly)

Note that the method generated in this way is the rewritten method and does not need to be changed.

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return age == employee.age && Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() { 
        return Objects.hash(name, age); //name,age and other attributes are stuffed into an object array
    }

If there are other class attributes in the class (for example, there are objects of class B in A), the equals and hashCode methods should also be overridden in B

LinkedHashSet 

(the node should be placed in the green box, which is not clearly drawn here)

1. The order of adding linkedhashset is consistent with the order of taking out elements.

2. A LinkedHashMap (a subclass of HashMap) is maintained at the bottom of the linkedhashset

3. LinkedHashSet underlying structure - array table + bidirectional linked list

4. When adding for the first time, the array table is directly expanded to 16. The array table is of HashMap$Node [] type, but the stored Node type is LinkedHashMap$Entry (polymorphic), which is a subclass of Node (you can view it from the structure in the lower left corner)

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }