4, java collection

4.1 overview of Java collection framework

• On the one hand, the object-oriented language reflects things in the form of objects. In order to facilitate the operation of multiple objects, it is necessary to store objects. On the other hand, there are some disadvantages in using Array to store objects, and Java collection is like a container, which can dynamically put the references of multiple objects into the container. Sets and arrays are structures that store multiple data, referred to as Java containers for short.

  • Characteristics of array in memory storage:

    • After the array is initialized, the length is determined.
    • The type of array declaration determines the type of element initialization

  • Disadvantages of array in storing data:

    • After the array is initialized, the length is immutable, which is not easy to expand
    • There are few attributes and methods provided in the array, which is not convenient for adding, deleting, inserting and other operations, and the efficiency is not high. At the same time, the number of storage elements cannot be obtained directly
    • The data stored in the array is ordered and repeatable. - --- > The characteristics of stored data are single

• Java collection classes can be used to store multiple objects with different numbers, and can also be used to store associative arrays with mapping relationships.

• Java collections can be divided into Collection and Map systems

  • Collection interface: single column data, which defines the collection of methods to access a group of objects

    • List: an ordered and repeatable collection of elements - > a dynamic array, which can be added or reduced at any time

      • ArrayList,LinkedList,Vector

    • Set: an unordered and unrepeatable set of elements - > similar to the set taught in high school, draw a circle

      • HashSet,LinkedHashSet,TreeSet

  • Map interface: double column data, saving a set with a mapping relationship of "key value pairs" - > similar to high school function: y=f(x), one key cannot correspond to multiple values, but multiple values can correspond to multiple keys

    • HashMap,LinkedHashMap,TreeMap,Hashtable,Properties

[Collection interface inheritance tree]

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-fddn0k2k-1625036862604) (C: \ users \ Zhengxu \ appdata \ roaming \ typora user images \ image-20210625102041447. PNG)]

[Map interface inheritance tree]

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-lrvxjscr-1625036862605) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ typora user images \ image-20210625102253875. PNG)]

4.2 Collection interface method

• The Collection interface is the parent interface of the List, Set and Queue interfaces. The methods defined in this interface can be used to operate both Set sets and List and Queue sets.
• JDK does not provide any direct implementation of this interface, but provides more specific implementation of sub interfaces (such as Set and List).
• Before Java 5, Java collections would lose the data types of all objects in the container and treat all objects as Object types; After adding generics to JDK 5.0, Java collections can remember the data types of objects in containers.

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

/**
 * Collection Method usage in interface:
 * 1.add(Object e):Add the element e to the collection coll
 * 2.size():Gets the number of added elements
 * 3.addAll():Add the elements in coll to the current collection
 * 4.isEmpty():Judge whether the current collection is empty
 * 5.clear():Empty collection elements
 * 6.contains(Object obj):Judge whether the current collection contains obj
 * 7.containsAll(collection coll2):Judge whether all elements in the formal parameter coll1 exist in the current collection
 * 8.remove(Object obj):Removes the obj element from the current collection and returns a Boolean value
 * 9.removeAll(Collection coll2):Subtraction: removes all elements in coll2 from the current set
 * 10.coll.retainAll(Collection coll3): Intersection: get the intersection of the current set and coll3 and return it to coll
 * 11.equals(Object obj):To return true, the elements of the current Set and the formal parameter Set must be the same. Whether the order is consistent depends on the defined Set type, and the Set must be in the same order
 * 12.hashCode():Returns the hash value of the current object
 * 13.toArray():Convert collection to array
 * 14.asList():Convert array to collection
 * @author zhengxu
 * @create 2021-06-25 10:32
 */
public class collection {

    @Test
    public void test01(){
        Collection coll=new ArrayList();

        //1.add(Object e): add element e to the collection coll
        coll.add("AA");
        coll.add(new String("Tom"));
        coll.add(123);//You can add objects of different data types

        //2.size(): get the number of added elements
        System.out.println(coll.size());//3

        //3.addAll(): add the elements in coll to the current collection
        Collection coll1=new ArrayList();
        coll1.add(456);
        coll1.add("BB");
        coll1.addAll(coll);

        System.out.println(coll1.size());//5

        //4.isEmpty(): judge whether the current collection is empty
        System.out.println(coll.isEmpty());//false

        //5.clear(): clear set elements
        coll1.clear();
        System.out.println(coll1.isEmpty());//true

        //6.contains(Object obj): judge whether the current set contains obj
        boolean contains=coll.contains(123);
        System.out.println(contains);//true
        System.out.println(coll.contains(new String("Tom")));//true, the content of the judgment is not the address, and the called equals is not==
        coll.add(new Person(21,"Jerry"));
        //System.out.println(coll.contains(new Person(21,"Jerry")));//false. To be true, you need to override the equals method of person
        //After overriding the equals method of person
        System.out.println(coll.contains(new Person(21,"Jerry")));//true

        //7. Containsall (collection collel2): judge whether all elements in the formal parameter colle1 exist in the current collection
        Collection coll2=new ArrayList();
        coll2.add(123);
        coll2.add("AA");
        System.out.println(coll.containsAll(coll2));//true

        //8.remove(Object obj): removes the obj element from the current collection, and the return value is Boolean
        System.out.println(coll.remove(123));//true, the removal succeeded
        System.out.println(coll);//[AA, Tom, study.javaSenior.commonlyClass.string.Person@442754a]
        System.out.println(coll.remove(new Person(21,"Jerry")));//true, the equals of person has been rewritten
        System.out.println(coll);//[AA, Tom]

        //9.removeAll(Collection coll2): subtraction: removes all elements in coll2 from the current collection
        coll.removeAll(coll2);
        System.out.println(coll);//[Tom], if there is no 123, it will not be removed, only the existing ones will be removed, and equals will be called

        //10.coll. Retain all (collection coll3): intersection: get the intersection of the current collection and coll3 and return it to coll
        Collection coll3= Arrays.asList(123,new String("Jerry"),new String("Tom"));
        coll.retainAll(coll3);
        System.out.println(coll);//[Tom]

        //11.equals(Object obj): to return true, the elements of the current Set and the parameter Set must be the same. Whether the order is consistent depends on the defined Set type, and the Set must be in the same order
        Collection coll4=new ArrayList();
        coll4.add(123);
        coll4.add(456);
        Collection coll5=new ArrayList();
        coll5.add(456);
        coll5.add(123);
        System.out.println(coll4.equals(coll5));//false, the content is consistent, but the order is inconsistent

        //12.hashCode(): returns the hash value of the current object
        System.out.println(coll4.hashCode());//5230

        //13.toArray(): convert a set to an array
        Object[] arr=coll4.toArray();
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);//123456
        }
        System.out.println();

        //14.asList(): convert an array to a collection
        List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
        System.out.println(list);//[AA, BB, CC]

        //15.iterator(): returns an instance of the iterator interface, which is used to traverse the collection elements and put them in the iteratortest Explain in Java
    }
}

[note]: when removing or judging an element in the set, be sure to observe whether the equals method of the element in the set needs to be rewritten. Otherwise, the address value of the element is sometimes compared instead of the content.

4.3 Iterator iterator interface

• The Iterator object is called an Iterator (a kind of design pattern) and is mainly used to traverse the elements in the Collection.
• **GOF defines iterator pattern as providing a way to access each element in a container object without exposing the internal details of the object. The iterator pattern is born for containers** Similar to "conductor on the bus", "stewardess on the train" and "stewardess".
• The Collection interface inherits Java Lang. Iterable interface, which has an iterator() method, then all Collection classes that implement the Collection interface have an iterator() method to return an object that implements the Iterator interface.
• Iterator is only used to traverse collections, and iterator itself does not provide the ability to load objects. If you need to create an iterator object, you must have a collection that is iterated.
• Every time a collection object calls the iterator() method, it gets a new iterator object, and the default cursor is before the first element of the collection.

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;

/**
 * Traversal of collection elements, using Iterator iterator interface
 * 1.Internal method: hasNext() and next() are used together
 * 2.Delete element: remove()
 *  Iterator You can delete the elements of the collection, but it is the remove side of the iterator object during traversal
 * Method, not the remove method of the collection object.
 *  If next() has not been called or the remove method has been called since the next method was last called,
 * Calling remove again will report IllegalStateException.
 * @author zhengxu
 * @create 2021-06-25 15:21
 */
public class IteratorTest {

    @Test
    public void test01(){
        Collection coll=new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person(21,"Jerry"));
        coll.add(new String("Tom"));
        coll.add(false);

        Iterator iterator = coll.iterator();
        //ergodic
        //Mode 1 (not recommended)
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());
//        System.out.println(iterator.next());

        //Mode 2 (not recommended)
//        for (int i = 0; i < coll.size(); i++) {
//            System.out.println(iterator.next());
//        }

        //Mode 3 (recommended)
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    //Two wrong ways of traversal
    @Test
    public void test02(){
        Collection coll=new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person(21,"Jerry"));
        coll.add(new String("Tom"));
        coll.add(false);

        Iterator iterator = coll.iterator();
        //Error mode 1: skip 123 and output 456 directly; NoSuchElementException will also occur
//        while ((iterator.next()!=null)){
//            System.out.println(iterator.next());
//        }

        //Error mode 2: it falls into an endless loop and keeps outputting 123. Every time the cursor is called, it is before the first object
//        while (coll.iterator().hasNext()){
//            System.out.println(coll.iterator().next());
//        }
    }


    //Test remove() in Iterator
    @Test
    public void test03(){
        Collection coll=new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person(21,"Jerry"));
        coll.add(new String("Tom"));
        coll.add(false);

        Iterator iterator = coll.iterator();
        //Delete Tom from the collection“
        while (iterator.hasNext()) {
            Object obj = iterator.next();
            if ("Tom".equals(obj)) {
                iterator.remove();
            }
        }
    }
}

• Enhanced for loop traversal collection

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.ArrayList;
import java.util.Collection;

/**
 * jdk5.0 New foreach loop for traversing collections and arrays
 * @author zhengxu
 * @create 2021-06-25 16:10
 */
public class ForTest {
    @Test
    public void test(){
        Collection coll=new ArrayList();
        coll.add(123);
        coll.add(456);
        coll.add(new Person(21,"Jerry"));
        coll.add(new String("Tom"));
        coll.add(false);

        //For (element type local variable in collection: collection object)
        //The iterator is still called internally
        for(Object obj:coll){
            System.out.println(obj);
        }
    }

    //Exercises
    @Test
    public void test01(){
        String[] arr=new String[]{"MM","MM","MM"};

        //Method 1: normal for loop
        for (int i = 0; i < arr.length; i++) {
            arr[i]="GG";
        }

        //Mode 2: enhanced for loop
        for(String s:arr){
            s="GG";
        }

        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
        //In mode 1, the output is GG,
        //In mode 2, the output is MM, because the enhanced for loop assigns the value to s and does not change the original set elements
    }
}

4.4 Collection sub interface I: List

• In view of the limitation that arrays are used to store data in Java, we usually use List instead of arrays.

  • The elements in the List collection class are ordered and repeatable, and each element in the collection has its corresponding sequential index.

  • The elements in the List container correspond to an integer serial number, recording their position in the container. The elements in the container can be accessed according to the serial number.

  • The implementation classes of List interface in JDK API are ArrayList, LinkedList and Vector.

• In addition to the methods inherited from the Collection collection, the List Collection adds some methods to operate the Collection elements according to the index.

  • void add(int index, Object ele): inserts an ele element at the index position
  • boolean addAll(int index, Collection eles): add all elements in eles from the index position
  • Object get(int index): gets the element at the specified index position
  • int indexOf(Object obj): returns the position where obj first appears in the collection
  • int lastIndexOf(Object obj): returns the last occurrence of obj in the current collection
  • Object remove(int index): removes the element at the specified index position and returns this element
  • Object set(int index, Object ele): sets the element at the specified index position to ele
  • List subList(int fromIndex, int toIndex): returns a subset from fromIndex to toIndex

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1.List Interface: store ordered and repeatable data - > dynamic array to replace the original array
 *   Specific implementation classes: ArrayList, LinkedList and Vector
 *
 *   Interview question: what are the similarities and differences among ArrayList, LinkedList and Vector?
 *   Same: the three classes implement the List interface, and the characteristics of storing data are the same: storing orderly and repeatable data
 *   Difference:
 *      ArrayList:As the main implementation class of the List interface, the thread is unsafe and efficient; The underlying layer uses Object[] elementData storage
 *      LinkedList:For frequent insert and delete operations, the efficiency of using this type is higher than that of ArrayList; The bottom layer uses two-way linked list storage!!!!
 *      Vector:As an ancient implementation class of the List interface, it appears before the List interface. Thread safety and low efficiency; The underlying layer uses Object[] elementData storage
 *
 * 2. ArrayList Source code analysis:
 *
 *   2.1 jdk7 Case
 *       ArrayList list=new ArrayList();//The bottom layer creates an Object [] array elementData with a length of 10 by default
 *       list.add(123);//elementData[0]=new Integer(123);
 *       .....
 *       list.add(11);//If the capacity of the elementData array at the bottom of the inverted layer is insufficient, the capacity will be expanded
 *       By default, the capacity expansion is 1.5 times of the principle capacity, and the data in the original array needs to be assigned to the new array.
 *
 *       Conclusion: it is suggested to use the constructor of substitute meal in the development: ArrayList = new ArrayList (int capacity); Specify initial length
 *
 *   2.2 jdk8 Changes in ArrayList under
 *       ArrayList list=new ArrayList();//The underlying Object[] elementData is initialized to {}, and an array with a length of 10 is not created
 *       list.add(123);//The first time add() is called, the underlying layer creates an array with a length of 10 and adds it to elementData
 *       ...
 *       There is no difference between the follow-up and jdk7
 *
 *   2.3 Summary: the creation of ArrayList in jdk7 is similar to the starving type of singleton, and the creation of ArrayList in jdk8 is similar to the lazy type of singleton, which delays the creation of array
 *            Save memory space
 *
 * 3.LinkedList Source code analysis
 *    LinkedList list=new LinkedList();//The first and last attributes of Node type are declared internally, and the default value is null
 *    list.add(123);//123 is encapsulated in the Node and the Node object is created.
 *
 *    Node is defined as a two-way linked list that embodies LinkedList
 *    private static class Node<E>{
 *        E item;
 *        Node<E> next;
 *        Node<E> perv;
 *
 *        Node(Node<E> prev,E element,Node<E> next){
 *        this.item=element;
 *        this.next=next;
 *        this.prev=prev;
 *        }
 *    }
 *
 * 4.Vector Source code analysis: when creating objects through the Vector () constructor in jdk7 and jdk8, the underlying layer creates an array with a length of 10
 *    In terms of capacity expansion, it is twice the original capacity by default
 *
 * 5.Summary: common methods
 *  Add: add(Object obj)
 *  Delete: remove(int index)/ remove(Object obj)
 *  Change: set(int index,Object obj)
 *  Query: get(int index)
 *  Insert: add(int index,Object obj)
 *  Length: size()
 *  Traversal: ① Iterator iterator mode
 *       ②Enhanced for loop mode
 *       ③Ordinary cycle
 *
 * @author zhengxu
 * @create 2021-06-25 16:22
 */
public class ListTest {

    //List common methods
    @Test
    public void test01(){
        ArrayList list=new ArrayList();
        list.add(123);
        list.add(456);
        list.add("AA");
        list.add(new Person(21,"Jerry"));
        list.add(456);

        //1.void add(int index, Object ele): inserts an ele element at the index position
        list.add(2,789);
        System.out.println(list);//[123, 456, 789, AA, study.javaSenior.commonlyClass.string.Person@442754a]

        //2.boolean addAll(int index, Collection eles): add all elements in eles from the index position
        List list1= Arrays.asList(1,2,3);
//        list.addAll(list1);// It means that the original number 123 of LIST1 is added to the list
        list.addAll(list1);
        System.out.println(list.size());//8

        //3.Object get(int index): get the element at the specified index position
        System.out.println(list.get(1));//456

        //4.int indexOf(Object obj): returns the position where obj first appears in the collection. If not, it returns - 1
        int index=list.indexOf(123);
        System.out.println(index);//0

        //5.int lastIndexOf(Object obj): returns the last occurrence of obj in the current set
        int index1=list.lastIndexOf(456);
        System.out.println(index1);//5

        //6.Object remove(int index): remove the element at the specified index position and return this element
        list.remove(0);

        //7.Object set(int index, Object ele): set the element of the specified index position as ele
        list.set(1,new String("set up"));
        System.out.println(list);//[456, setting, AA, study.javasenior.commonlyclass.string Person@442754a , 456, 1, 2, 3]

        //8.List subList(int fromIndex, int toIndex): returns the subset from fromIndex to toIndex, closed on the left and open on the right
        List sublist=list.subList(1,2);
        System.out.println(sublist);//[setting]
    }
}

[interview question]: distinguish list Is the index or content deleted by the remove () method

package study.javaSenior.collections;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * List Interview question: distinguish list Is the index or content deleted by the remove () method
 * @author zhengxu
 * @create 2021-06-27 14:07
 */
public class ListExercise {
    @Test
    public void testListRemove(){
        List list=new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);//[1]
    }

    public static void updateList(List list){
        list.remove(2);//The index is actually deleted
        list.remove(new Integer(2));//The value is deleted
    }
}

4.5 Collection sub interface 2: Set

• The set interface is a sub interface of the Collection. The set interface does not provide additional methods
• The Set set cannot contain the same elements. If you try to add two identical elements to the same Set set, the add operation fails.
• Set determines whether two objects are the same, not using the = = operator, but according to the equals() method

4.5.1 one of the set implementation classes: HashSet

• HashSet is a typical implementation of the Set interface. This implementation class is used most of the time when using the Set set.

• HashSet stores the elements in the set according to the Hash algorithm, so it has good performance of access, search and deletion.

• HashSet has the following characteristics:

  • The order of elements cannot be guaranteed
  • HashSet is not thread safe
  • Collection elements can be null

• **HashSet sets the criteria for judging the equality of two elements: * * two objects are equal through hashCode() method, and the return values of the equals() method of the two objects are also equal.

• For objects stored in the Set container, the corresponding classes must override the equals() and hashCode(Object obj) methods to implement the object equality rule. That is: "equal objects must have equal hash codes".

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-3l0cywys-1625036862606) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ typora user images \ image-20210628090242721. PNG)]

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

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

/**
 * Set: Disordered and unrepeatable collection of elements - > similar to the collection taught in high school, draw a circle
 * - HashSet:As the main implementation class of set interface; Thread unsafe; null values can be stored
 * - LinkedHashSet: As a subclass of HashSet, the internal data can be traversed according to the added order
 * - TreeSet: You can sort according to the specified attributes of the added object; Similar to red and black trees
 *
 * 1.Set There are no additional new methods declared in the interface. They are all inherited Collection methods
 *
 * 2.Requirement: to add data to the Set, the class must write hashCode() and equals() from
     Requirement: the rewritten hashCode() and equals() are consistent: equal objects must have equal hash codes
       Tip for rewriting two methods: the fields in the object used for the equals() method comparison should be used to calculate the hashCode value.
 *
 * @author zhengxu
 * @create 2021-06-27 17:18
 */
public class SetTest {
    /*
    1, set: store unordered and unrepeatable data
    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 is added according to the hash value of the data

    2.Non repeatability: ensure that the added element cannot return true when judged according to equals(). That is, only one element can be added to the same element

    2, Process of adding elements to HashSet: 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 (i.e. index position) in the underlying array of HashSet through some algorithm (such as modulus%) to judge whether there are elements in this position of the array.
         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 a linked list) at this position, compare the hash values of element a and element b:
            If the hash values are different, the element a is added successfully. -- > Case 2
            If the hash values are the same, you need to call the equals() method of the class where element a is located:
                equals()If true is returned, the addition of element a fails,
                equals()If false is returned, the element a is successfully added -- > case 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.
        jdk7: Element a is placed in the array and points to the original element
        jdk8: The original element is in the array and points to element a
        Conclusion: seven up and eight down
        
        hashCode Underlying structure = array + linked list

     */
    @Test
    public void test(){
        Set set=new HashSet();
        set.add(456);
        set.add(123);
        set.add("AA");
        set.add("CC");
        set.add(new Person(21,"Tom"));
        set.add(new Person(21,"Tom"));
        set.add(129);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//There is only one person output. See the code in the following section for the specific implementation
        }
    }
}

[note]: the essence of the non repeatability of the set lies in the following rewritten hashCode() and equals() methods

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

    @Override
    public int hashCode() {//return name.hashCode()+age; Too small hash value will lead to high repetition rate
        int result=name!=null?name.hashCode():0;
        result=31*result+age;
        return result;
    }

• Take Eclipse/IDEA as an example. In a custom class, you can call tools to automatically rewrite equals and hashCode. Question: why does Eclipse/IDEA copy the hashCode method with the number 31?
  • When selecting the coefficient, select the coefficient as large as possible. Because if the calculated hash address is larger, the so-called "conflicts" will be less, and the search efficiency will be improved. (conflict reduction)
  • Moreover, 31 only occupies 5 bits, and the probability of data overflow caused by multiplication is small.
  • 31 can be represented by I * 31 = = (I < < 5) - 1. Now many virtual machines are optimized. (improve algorithm efficiency)
  • 31 is a prime number. The function of prime number is that if I multiply a number by this prime number, the final result can only be divided by the prime number itself, the multiplicand and 1! (conflict reduction)

[interview question]: deeply understand the storage method of HashSet

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.HashSet;

/**
 * Interview question: help understand the storage method of HashSet!!!!
 * @author zhengxu
 * @create 2021-06-28 17:31
 */
public class HashSetExercise {
    @Test
    public void test(){
        Person p1=new Person(21,"AA");
        Person p2=new Person(22,"BB");

        HashSet set=new HashSet();
        set.add(p1);
        set.add(p2);
        System.out.println(set);

        p1.setName("CC");
        set.remove(p1);//p1 is removed, but it is obviously not removed during output because the storage location of the element has been finalized and cannot be changed when modifying the attribute in the previous step, but the hash value can be changed
                       //However, the hash value of the modified p1 at the time of removal changes due to the change of the attribute, so the location of removal is not the location of p1
        System.out.println(set);
        set.add(new Person(21,"CC"));//This is because the location with the same hash value is not the actual location where p1 exists. It is empty, so it can be added
        System.out.println(set);//Repeated addition of 21, CC

//        [Person{age=22, name='BB'}, Person{age=21, name='AA'}]
//        [Person{age=22, name='BB'}, Person{age=21, name='CC'}]
//        [Person{age=22, name='BB'}, Person{age=21, name='CC'}, Person{age=21, name='CC'}]
    }
}

4.5.2 Set implementation class 2: LinkedHashSet

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

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

public class SetTest { 
    //Usage of LinkedHashSet
    //LinkedHashSet: as a subclass of HashSet, while adding data, each data also maintains two introductions, recording the previous data and the latter data
    //Advantages: LinkedHashSet is more efficient for frequent traversal operations
    @Test
    public void test01(){
        Set set=new LinkedHashSet();
        set.add(456);
        set.add(123);
        set.add("AA");
        set.add("CC");
        set.add(new Person(21,"Tom"));
        set.add(new Person(21,"Tom"));
        set.add(129);

        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//When storing, the storage location is disordered, but the output order is the same as the addition order. The essence is a two-way linked list!!!
        }
    }
}

4.5.3 Set implementation class 3: TreeSet

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

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

/**
 * @author zhengxu
 * @create 2021-06-28 9:53
 */
public class TreeSetTest {
    /*
    1.The data added to the TreeSet must be objects of the same class
    2.Two sorting methods:
        Natural sorting (implement the Compare interface)
        Custom sort (Comparator)

    3.In natural sorting, the standard for comparing whether two objects are the same is: compareTo() returns 0, which is no longer the equals() method
      In person, add the same age and different names. In order not to be considered as repetition by the same age, you need to write a secondary comparison method

    4.In custom sorting, the standard for comparing whether two objects are the same is: compare() returns 0, which is no longer the equals() method
     */

    @Test
    public void test() {
        TreeSet set=new TreeSet();

        //Failed: cannot add objects of different classes
//        set.add(456);
//        set.add(123);
//        set.add("AA");
//        set.add(new Person(21,"Tom"));

        //Example 1:
//        set.add(123);
//        set.add(456);
//        set.add(789);
//        set.add(-23);

        //Example 2:
        set.add(new Person(21,"Tom"));
        set.add(new Person(12,"Jerry"));
        set.add(new Person(12,"Tom"));
        set.add(new Person(21,"Bom"));



        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());//When traversing the output, it is output according to the size
        }
    }

    @Test
    public void test02(){
        Comparator com=new Comparator() {
            //Sorted by age from small to large
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person&&o2 instanceof Person){
                    Person u1=(Person) o1;
                    Person u2=(Person) o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }else {
                    throw new RuntimeException("The data types entered do not match");
                }
            }
        };
        TreeSet set=new TreeSet(com);//Add parameters to sort according to the specified order

        set.add(new Person(21,"Tom"));
        set.add(new Person(12,"Jerry"));
        set.add(new Person(12,"Tom"));
        set.add(new Person(21,"Bom"));

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

4.5.4 summary

• If the object stored in the Collection is an object of a custom class, which method does the custom class need to override?

  • equals()

  • List: equals() method

  • Set: (HashSet and LinkedHashSet are examples): equals(), hashCode()

    (TreeSet as an example): Comparable: comparTo(Object obj)

    ​ Comparator: compare(Object o1,Object o2)

• What are the similarities and differences among ArrayList, LinkedList and Vector? [interview questions]

  • The same point: they are all implementation classes of the List interface, and the characteristics of storing data are the same: storing orderly and repeatable data. Generally, the first two are mainly used
  • Difference: the first one is used for simple addition and deletion, and the second one is used for more insertion and deletion

4.6 Map interface

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ybkdobkg-1625036862608) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ user images \ image-20210629153900580. PNG)]

• Map and Collection exist side by side. Used to save data with mapping relationship: key value
• The key and value in the Map can be data of any reference type
• The key in the Map is stored in a Set and cannot be repeated. That is, the class corresponding to the same Map object must override the hashCode() and equals() methods
• String class is often used as the "key" of Map
• There is a one-way one-to-one relationship between key and value, that is, a unique and definite value can always be found through the specified key
• Common implementation classes of Map interface: HashMap, TreeMap, LinkedHashMap and Properties. Among them, HashMap is the most frequently used implementation class of Map interface

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-7xbmibdg-1625036862610) (C: \ users \ Zhengxu \ appdata \ roaming \ typora user images \ image-20210629155955252. PNG)]

• Map interface: common methods

• Add, delete and modify:

• Object put(Object key,Object value): adds (or modifies) the specified key value to the current map object

• void putAll(Map m): store all key value pairs in m into the current map

• Object remove(Object key): removes the key value pair of the specified key and returns value

• void clear(): clear all data in the current map

• Operation of element query:

• Object get(Object key): get the value corresponding to the specified key

• boolean containsKey(Object key): whether the specified key is included

• boolean containsValue(Object value): whether the specified value is included

• int size(): returns the number of key value pairs in the map

• boolean isEmpty(): judge whether the current map is empty

• boolean equals(Object obj): judge whether the current map and parameter object obj are equal

• Method of metaview operation:

  • Set keySet(): returns the set set composed of all keys

  • Collection values(): returns the collection collection composed of all values

  • Set entrySet(): returns the set set composed of all key value pairs

4.6.1 one of the map implementation classes: HashMap

• HashMap is the most frequently used implementation class of Map interface.
• Null keys and null values are allowed. Like HashSet, the mapping order is not guaranteed.
• The Set composed of all keys is Set: unordered and non repeatable. Therefore, the class where the key is located should be rewritten: equals() and hashCode()
• The Collection composed of all values is Collection: unordered and repeatable. Therefore, the class where value is located should be rewritten: equals()
• A key value constitutes an entry
• The Set composed of all entries is Set: unordered and non repeatable
• The criteria for HashMap to judge whether two keys are equal are: the two keys return true through the equals() method, and the hashCode value is also equal-
• HashMap judges that two value s are equal by returning true through the equals() method.

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-tkl7kbvu-1625036862612) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ user images \ image-20210630091345740. PNG)]

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-ol15mwcg-1625036862614) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ user images \ image-20210630091403823. PNG)]

4.6.1 Map implementation class 2: LinkedHashMap

• LinkedHashMap is a subclass of HashMap
• Based on the HashMap storage structure, a pair of two-way linked lists are used to record the order of adding elements
• Similar to LinkedHashSet, LinkedHashMap can maintain the iteration order of Map: the iteration order is consistent with the insertion order of key value pairs

package study.javaSenior.collections;

import org.junit.Test;

import java.util.*;

/**
 * 1, Structure of Map implementation class
 * |----Map: Double column data, which stores the data of key value pairs ---- similar to high school functions
 *          |----HashMap: As the main implementation class of Map; Unsafe thread and high efficiency; null key value can be stored
 *                  |----LinkedHashMap: Ensure that when traversing Map elements, they can be traversed in the order of addition
 *                                Reason: Based on the underlying structure of HashMap, a pair of pointers are added to point to the previous and subsequent elements.
 *                                For frequent traversal operations, this kind of execution efficiency is higher than HashMap
 *          |----TreeMap: Ensure that the added key value pairs are sorted to achieve traversal sorting. At this time, sort with key
 *                        The bottom layer belongs to red and black trees
 *          |----Hashtable: Ancient Map implementation class; Thread safety and low efficiency; Cannot save null
 *                  |----Properties: Commonly used to process configuration files. Both key and value are String types
 *
 * HashMap Bottom layer: array + linked list (jdk7 before)
 *             Array + linked list + red black tree (jdk8)
 *
 * Interview questions:
 * 1.HashMap The underlying implementation principle of?
 * 2.HashMap And hashtable?
 * 3.CurrentHashMap Similarities and differences with Hashtable? (not for the time being)
 *
 * 2, Map structure understanding
 *  Map Keys in: unordered and non repeatable. Use Set to store all keys -------- > the class where the key is located should override equals() and hashCode()
 *  Map Values in: unordered and repeatable. Use the Collection to store all value s ----- > the class where they belong should override equals()
 *  A key value pair: key value constitutes an Entry object
 *  Map Entries in: unordered and non repeatable. Use Set to store all entries
 *
 * 3, Underlying implementation principle of HashMap (taking jdk7 as an example)
 *  HashMap map=new HashMap();
 *   After instantiation, the bottom layer creates a one-dimensional array Entry[] table with a length of 16;
 *   ......
 *   map.put(key1,value1):
 *      First, call hashCode() of the class where key1 is located to calculate the hash value of key1. After the hash value is calculated by some algorithm, the storage location in the Entry array is obtained
 *      If the data in this position is empty, key1-value1 is added successfully ---------- case 1
 *      If the data in this location is not empty, (which means that there are one or more data in this location (in the form of linked list)), compare the hash values of key1 and one or more existing data:
 *           If the hash value of key1 is different from the existing hash value, key1-value1 is added successfully------------ Case 2
 *           If key1 and an existing data hash value are the same, continue the comparison, call the equals() method where key1 is located, and compare:
 *              If equals() returns false: key1-value1 is added successfully ------------- case 3
 *              If equals() returns true: replace value with value1!!!!!!!!!!!!
 *      Supplement: for case 2 and case 3: at this time, key1-value1 and the original data are stored in the form of linked list.
 *
 *      In the process of continuous addition, the problem of capacity expansion will be involved. When the critical value is exceeded (and the location to be stored is not empty), the default capacity expansion method is to double the original capacity and assign the original data
 *
 *  jdk8 Compared with jdk7 in the underlying implementation:
 *  1.new HashMap():The underlying layer did not create an array with a length of 16
 *  2.jdk8 The underlying array is: Node [], not Entry []
 *  3.When the put() method is called for the first time, the underlying layer creates an array with a length of 16
 *  4.jdk7 The underlying structure is only data + linked list. Underlying structure in jdk8: array + linked list + red black tree
 *    When the number of data of elements at an index position on the underlying linked list array in the form of linked list is > 8 and the length of the current array is > 64,
 *    At this time, the index data at the index position is stored in red black tree instead.
 *
 *  DEFAULT_INITIAL_CAPACITY : HashMap Default capacity of, 16
 *  MAXIMUM_CAPACITY :  HashMap Maximum supported capacity, 2 ^ 30
 *  DEFAULT_LOAD_FACTOR: HashMap Default load factor for
 *  TREEIFY_THRESHOLD: Bucket If the length of the linked list is greater than the default value, it will be converted into a red black tree
 *  UNTREEIFY_THRESHOLD: Bucket If the Node stored in the red black tree is less than the default value, it will be converted into a linked list
 *  MIN_TREEIFY_CAPACITY: The minimum hash table capacity when the nodes in the bucket are trealized. (when the number of nodes in the bucket is so large that it needs to be red black tree, if the hash table capacity is less than min_tree_capacity,
 *  At this time, resize the min_ TREEIFY_ The value of capability must be at least tree_ (4 times the threshold.)
 *
 *  4, Underlying implementation principle of LinkedHashMap (understand)
 *      In the source code:
 *      static class Entry<K,V> extends Map.Node<K,V>{
 *         Entry<K,V> before,after;//It can record the order of added elements
 *         Entry(int hash,K key,V value,Node<K,V> next){
 *             super(hash,key,value,next);
 *         }
 *     }
 *
 *  5, Methods defined in the Map interface:
 *   -  Add, delete and modify:
 *       - Object put(Object key,Object value): Add (or modify) the specified key value to the current map object
 *       - void putAll(Map m):Store all key value pairs in m into the current map
 *       - Object remove(Object key): Remove the key value pair of the specified key and return value
 *       - void clear(): Clear all data in the current map
 *   -  Operation of element query:
 *       - Object get(Object key): Gets the value corresponding to the specified key
 *       - boolean containsKey(Object key): Whether to include the specified key
 *       - boolean containsValue(Object value): Whether to include the specified value
 *       - int size(): Returns the number of key value pairs in the map
 *       - boolean isEmpty(): Judge whether the current map is empty
 *       - boolean equals(Object obj): Judge whether the current map and parameter object obj are equal
 *
 *   - Method of metaview operation:
 *       - Set keySet(): Returns the Set set composed of all key s
 *       - Collection values(): Returns a Collection of all value s
 *       - Set entrySet(): Returns the Set set composed of all key value pairs
 *
 * @author zhengxu
 * @create 2021-06-28 17:49
 */
public class MapTest {

    @Test
    public void test(){
        Map map=new HashMap();

        map.put(null,123);
    }

    //ergodic
    @Test
    public void test01(){
        Map map=new HashMap();
        map.put(123,"AA");
        map.put(456,"BB");
        map.put(789,"CC");

        //Traverse all key sets: keySet()
        Set set=map.keySet();
        Iterator iterator=set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }

        //Traverse all value sets: values()
        Collection values=map.values();
        Iterator iterator1=values.iterator();
        while (iterator1.hasNext()){
            System.out.println(iterator1.next());
        }

        //Traverse all key value sets:
        // Method 1: entrySet()
        Set entrySet=map.entrySet();
        Iterator iterator2=entrySet.iterator();
        while (iterator2.hasNext()){
            Object obj=iterator2.next();
            //All elements in the collection are entries
            Map.Entry entry=(Map.Entry) obj;
            System.out.println(entry.getKey()+"----->"+entry.getValue());
        }

        //Mode 2:
        Set keySet=map.keySet();
        Iterator iterator3=set.iterator();
        while (iterator3.hasNext()){
            Object key=iterator3.next();
            Object value=map.get(key);
            System.out.println(key+"======"+value);
        }
    }
}

4.6.3 Map implementation class 3: TreeMap

• When storing key value pairs in TreeMap, you need to sort them according to key value pairs. TreeMap can ensure that all key value pairs are in an orderly state.

• The underlying TreeSet uses a red black tree structure to store data

• Sorting of TreeMap keys:

  • Natural sorting: all keys of TreeMap must implement the Comparable interface, and all keys should be objects of the same class, otherwise ClasssCastException will be thrown
  • Custom sorting: when creating a TreeMap, a Comparator object is passed in, which is responsible for sorting all keys in the TreeMap. At this time, the key of the Map is not required to implement the Comparable interface

• TreeMap judges the equality of two keys: two keys return 0 through the compareTo() method or the compare() method.

package study.javaSenior.collections;

import org.junit.Test;
import study.javaSenior.commonlyClass.string.Person;

import java.util.*;

/**
 * @author zhengxu
 * @create 2021-06-30 10:59
 */
public class TreeMapTest {
    //Adding key value to TreeMap requires that the key must be an object created by the same class
    //Because you need to sort by key: natural sorting and custom sorting
    @Test
    public void test(){
        Comparator com=new Comparator() {
            //Sorted by age from small to large
            @Override
            public int compare(Object o1, Object o2) {
                if(o1 instanceof Person&&o2 instanceof Person){
                    Person u1=(Person) o1;
                    Person u2=(Person) o2;
                    return Integer.compare(u1.getAge(),u2.getAge());
                }else {
                    throw new RuntimeException("The data types entered do not match");
                }
            }
        };
        TreeMap map=new TreeMap(com);
        Person p1=new Person(23,"Tom");
        Person p2=new Person(32,"Jerry");
        Person p3=new Person(20,"Jack");
        Person p4=new Person(18,"Rose");

        map.put(p1,98);
        map.put(p2,89);
        map.put(p3,76);
        map.put(p4,100);

        Set entrySet=map.entrySet();
        Iterator iterator=entrySet.iterator();
        while (iterator.hasNext()){
            Object obj=iterator.next();
            Map.Entry entry=(Map.Entry) obj;
            System.out.println(entry.getKey()+"----->"+entry.getValue());
        }
    }
}

4.6.4 Map implementation class 4: Hashtable

• Hashtable is an ancient Map implementation class, jdk1 0 is provided. Unlike HashMap, hashtable is thread safe.
• The implementation principle and function of Hashtable are the same as that of HashMap. The bottom layer uses hash table structure, which has fast query speed and can be used with each other in many cases.
• Unlike HashMap, Hashtable does not allow null as key and value
• Like HashMap, Hashtable cannot guarantee the order of key value pairs
• Hashtable judges that two key s are equal and two value s are equal, which is consistent with HashMap.

4.6.5 Map implementation class 5: Properties

• The Properties class is a subclass of Hashtable, which is used to process property files
• Since the key and value in the Properties file are of string type, the key and value in Properties are of string type
• When accessing data, it is recommended to use setProperty(String key,String value) method and getProperty(String key) method

Properties pros = new Properties();
pros.load(new FileInputStream("jdbc.properties"));//Load profile
String user = pros.getProperty("user");
System.out.println(user);

4.7 Collections tool class

• Collections is a tool class that operates on collections such as Set, List, and Map

• Collections provides a series of static methods to sort, query and modify collection elements. It also provides methods to set immutable collection objects and realize synchronous control over collection objects

• Sorting operations: (all static methods)

  • reverse(List): reverse the order of elements in the List
  • shuffle(List): randomly sort the elements of the List collection
  • sort(List): sorts the elements of the specified List set in ascending order according to the natural order of the elements
  • sort(List, Comparator): sort the List collection elements according to the order generated by the specified Comparator
  • swap(List, int, int): exchange the elements at i and j in the specified list set

• Find, replace

  • Object max(Collection): returns the largest element in a given collection according to the natural order of elements
  • Object max(Collection, Comparator): returns the largest element in a given collection according to the order specified by the Comparator
  • Object min(Collection)
  • Object min(Collection，Comparator)
  • int frequency(Collection, Object): returns the number of occurrences of the specified element in the specified collection
  • void copy(List dest,List src): copy the contents of src to dest
  • Boolean replaceall (List, Object oldVal, Object newVal): replaces all old values of the List object with new values

Collections.reverse(list);

• The Collections class provides multiple synchronizedXxx() methods, which can wrap the specified collection into a thread synchronized collection, which can solve the thread safety problem when multiple threads access the collection concurrently

[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-uxefgley-1625036862616) (C: \ users \ Zhengxu \ appdata \ roaming \ typora \ user images \ image-20210630150320179. PNG)]

List list1=Collections.synchronizedList(list);