1 Map interface

1.1 general

Java.util interface map < K, V >
Type parameter: K - indicates the key maintained by this mapping; V - indicates the corresponding value maintained by this mapping
Also called hash table, hash table It is often used for data of key value pair structure The key cannot be repeated and the value can be repeated

1.2 features

1. Map can extract the corresponding value according to the key
2. The key of Map cannot be repeated. If it is repeated, the corresponding value will be overwritten
3. Map stores unordered data
4. The initial capacity of the Map is 16, and the default loading factor is 0.75

TIPS: source code excerpt:
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
Initial capacity 1 < < 4, equivalent to 1 * (2 ^ 4), i.e. 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
The default loading factor is 0.75f, that is, when 75% is saved, the capacity will be expanded according to the power of 2

1.3 inheritance structure

1.4 common methods

Just learn the methods in the Map interface

void clear() removes all mapping relationships from this mapping (optional operation) boolean containsKey(Object key) returns true if this mapping contains mapping relationships for the specified key
boolean containsValue(Object value) returns true if this mapping maps one or more keys to the specified value
Set<Map. Entry < K, V > > entryset() returns the set view of the mapping relationship contained in this mapping
boolean equals(Object o) compares whether the specified object is equal to this mapping
V get(Object key) returns the value mapped by the specified key; Returns null if the mapping does not contain a mapping relationship for the key
int hashCode() returns the hash code value of this mapping
boolean isEmpty() returns true if the mapping does not contain a key value mapping relationship
Set keySet() returns the set view of the keys contained in this map
V put(K key, V value) associates the specified value with the specified key in this mapping (optional operation)
Void putall (map <? Extensions K,? Extensions V > m) copies all mapping relationships from the specified mapping to this mapping (optional operation)
V remove(Object key) if there is a key mapping relationship, remove it from this mapping (optional operation)
int size() returns the number of key value mapping relationships in this mapping
Collection values() returns a collection view of the values contained in this map

1.5 exercise: Map common method test

Create package: CN tedu. map
Create class: mapdemo java

package cn.tedu.list;

import java.util.*;

/**This class is used to test the Map interface*/
public class MapDemo {
    public static void main(String[] args) {
        //1. Create a Map object
        /**Map The data in must conform to the mapping rules. Be sure to specify the data types of K and V at the same time
         * The specific type of K and V depends on the specific business requirements*/
        Map<Integer,String> map = new HashMap<>();//Note: Java util
        //2. Store data into the map set. Note that the method is put(), and a pair of < K, V > values need to be stored
        map.put(9527,"Baigujing");
        map.put(9528,"Black bear essence");
        map.put(9529,"Carp essence");
        map.put(9530,"Yellow hair monster");
        map.put(9531,"Black bear essence");
        map.put(9527,"King of the kingdom of daughters");
        /**1.map There are disordered data stored in
         * 2.map The value in can be repeated - for example, we can save two black bear spirits
         * 3.map The key in cannot be repeated. If it is repeated, the following value will overwrite the previous value
         * For example, the king of the daughter country and the white bone essence are 9527, and the white bone essence is covered*/
        System.out.println(map);//Check whether the data in the map set is saved successfully

        //3. Conduct method test
        //map.clear();// Empty collection
        System.out.println(map.hashCode());//Gets the hash code of the collection
        System.out.println(map.equals("Yellow hair monster"));//Judge whether the "yellow hair monster" is equal to the collection object
        System.out.println(map.isEmpty());//Judge whether the set is empty
        System.out.println(map.size());//Gets the number of elements in the collection

        //Judge whether the current map set contains the specified Key
        System.out.println(map.containsKey(9527));//true
        //Judge whether the current map collection contains the specified Value
        System.out.println(map.containsValue("Baigujing"));//false because it has been overwritten
        //Get the corresponding value value according to the key value
        System.out.println(map.get(9530));
        //According to the key value pair corresponding to this key value, K and V are deleted
        System.out.println(map.remove(9529));
        System.out.println(map.containsKey(9529));
        System.out.println(map.containsValue("Carp essence"));

        //Take out all value s in the map Collection and put them into the Collection collection
        //The Type of Type in collection < Type > depends on the Type of value in the map
        Collection<String> values = map.values();
        System.out.println(values);//[daughter country king, black bear spirit, yellow hair monster, black bear spirit]

        //4.map set iteration method 1
        /**Mode 1:
         * Traverse the data in the map, but the map itself has no iterator, so it needs to be converted into a set set first
         * Set<Key>:Store all key values in the map into the set -- keySet()*/
        //4.1 take out the key value in the map set and store it in the set set. The generic type of the set is the type Integer of the key
        Set<Integer> keySet = map.keySet();
        //4.2 to traverse a set, you need to get the iterator of the set
        Iterator<Integer> it = keySet.iterator();
        //4.3 all elements in the loop iteration set
        while(it.hasNext()){//Determine whether the next element can be iterated
            Integer key = it.next();//Get the key of the map obtained in this cycle
            String value = map.get(key);
            System.out.println("{"+key+","+value+"}");
        }

        /**Mode 2:
         * To traverse the map set, you need to convert the map set into a set set first
         * Is to put a pair of key value pairs in the map into the set as an entry < K, V >
         * A pair of K and V is an Entry*/
        Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
        //Get iterator
        Iterator<Map.Entry<Integer, String>> it2 = entrySet.iterator();
        while(it2.hasNext()){//Determine whether there is a next element that can be iterated
            //An Entry object traversed in this round
            Map.Entry<Integer, String> entry = it2.next();
            Integer key = entry.getKey();//Get the key in the Entry
            String value = entry.getValue();//Get value in Entry
            System.out.println("{"+key+","+value+"}");
        }
    }
}

2 HashMap

2.1 Preface

The key of HashMap should rewrite hashCode() and equlas() at the same time
hashCode() is used to determine whether the hash values of the two are the same. After rewriting, it is generated according to the attribute
equlas() is used to determine whether the values of attributes are the same. After rewriting, it is determined according to the attributes
– equlas() judges that if the data are equal, hashCode() must be the same
– equlas() judge that if the data are not equal, hashCode() should be as different as possible

2.2 stored procedure of HashMap:

1. The structure of HashMap is in the form of array + linked list or array + red black tree
2. The Entry [] array at the bottom of HashMap has an initial capacity of 16 and a loading factor of 0.75f. The capacity is expanded by about twice
3. When storing data, the storage location of the data will be calculated according to the hash(key)%n algorithm. N is the length of the array, which is actually the capacity of the set
4. When there is no data stored before the calculated location, the data will be stored directly
5. When there is data in the calculated position, hash collision / hash collision will occur
   The solution is to adopt the structure of linked list and insert new elements after the elements in the array
   In other words, the elements in the array are the first nodes added
6. If the length of the linked list is > 8 and the array length is > 64, the linked list will be turned into a red black tree. When the length of the linked list is < 6, the red black tree will be restored into a linked list again
   

2.3 exercise: get HashMap data

Create package: CN tedu. map
Create class: testhashmap java

package cn.tedu.collection;

import java.util.HashMap;

/**This class is used for HashMap exercises*/
public class TestHashMap {
	public static void main(String[] args) {
		//Create a HashMap object
		HashMap<Integer,String> map = new HashMap();
		/**
		 * Source code excerpt:
		 * static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
		 * The initial capacity is 1 < < 4, which is equivalent to 1 * (2 ^ 4) = 16
		 * static final float DEFAULT_LOAD_FACTOR = 0.75f;
		 * The default loading factor is 0.75, which means that the capacity will be expanded when 75% is saved, and the capacity will be expanded according to the power of 2
		 */
		/*
		 * When the loading factor of the capacity is reached, the space will be reopened and the storage location of all objects will be recalculated, which is also called rehash
		 * When setting the initial capacity and loading factor, we should pay attention to the relative balance. If the loading factor is too low, rehash is too frequent, which will affect the performance
		 * If the initial capacity is set too high or the loading factor is set too high, the query efficiency will be affected
		 */
	}
}

2.4 exercise: character statistics in string

Create package: CN tedu. map
Create class: testmap java

package cn.tedu.map;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/*This class is used to practice map cases: counting the number of characters in a string
* Demand effect: user input aabbbcc, output: a=2,b=3,c=2*/
public class TestMap2 {
    public static void main(String[] args) {
        //1. Receive the string entered by the user
        System.out.println("Please enter the string to be counted:");
        String input = new Scanner(System.in).nextLine();
        //2. Prepare a map set to store the characters that appear, Character and the number of characters, Integer
        //Why is the Character type Character used as the key in the map? Because the key cannot be repeated, but the number of times can be repeated
        Map<Character,Integer> map = new HashMap<>();

        //3. Prepare the data to be stored in the map: K and V
        //3.1 traverse the string entered by the user and count each character
        for (int i = 0; i < input.length(); i++) {
            //3.2 get the characters traversed in this cycle
            char key = input.charAt(i);
            //System.out.println(key);// Print and view the characters obtained in each cycle. There is no problem
            //3.2 get the corresponding value according to the obtained key
            Integer value = map.get(key);//According to the character, get the number of times this character is saved in the map
            if(value == null){//This character has not appeared before, and the number of times is still the default value of Integer null
                map.put(key,1);//If it does not appear, the number of times is set to 1
            }else {//value is not null, else
                map.put(key,value+1);//This character has appeared before, and the number of times becomes the previous number + 1
            }
        }
        System.out.println("The number of occurrences of each character is:"+map);
    }
}

3. Set interface

3.1 general

1. Set is a Collection that does not contain duplicate data
2. The data in the Set set is out of order (because the Set set has no subscript)
3. The elements in the Set cannot be repeated – often used to de duplicate data

3.2 characteristics of set

1. The data is out of order and cannot be duplicated
2. HashSet: the bottom layer is the hash table, which wraps the HashMap, which is equivalent to storing the data as K into the internal HashMap when storing the data into the HashSet. Of course, K is still not allowed to repeat.
3. TreeSet: the bottom layer is TreeMap, which is also in the form of red black tree, which is easy to find data

3.3 common methods

Just learn the methods in the Collection interface

3.4 HashSet overview

The bottom layer is the hash table, which wraps the HashMap, which is equivalent to storing the data into the HashSet as K in the internal HashMap, where k is not allowed to be repeated and null is allowed

3.5 exercise: Set related tests

Create package: CN tedu. collection
Create class: testset java

package cn.tedu.collection;

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

/*This class is used to test Set*/
public class TestSet {
    public static void main(String[] args) {
        //1. Create the corresponding collection object
        Set<String> set = new HashSet<>();
        //2. Data storage
        set.add("Zixia Fairy");
        set.add("Supreme treasure");
        set.add("spider goblin");
        set.add("Zixia Fairy");
        set.add(null);
        /*1.set There is no order in the set
        * 2.set Elements in a collection cannot be duplicated
        * 3.set A collection can hold null values, but there is only one at most*/
        System.out.println(set);//[spider essence, null, zhizunbao, Zixia fairy]

        //3. Common test methods
        System.out.println(set.contains("Tang Monk"));//false to determine whether the specified element is included
        System.out.println(set.isEmpty());//false to judge whether it is empty
        System.out.println(set.remove(null));//true to remove the specified element
        System.out.println(set);//[spider essence, supreme treasure, Zixia fairy]
        System.out.println(set.size());//3. Get the number of elements in the set
        System.out.println(Arrays.toString(set.toArray()));//[spider essence, supreme treasure, Zixia fairy], turn the collection into an array

        //4.1 create set2 set and store data into the set
        Set<String> set2 = new HashSet<>();
        set2.add("Rabbit paper");
        set2.add("Cerebellar axe");
        set2.add("Xiaohaitong");
        set2.add("veal ");
        System.out.println(set2);//[rabbit paper, xiaohaitong, calf, cerebellar axe]
        System.out.println(set.addAll(set2));//Add all the elements of the set2 set to the set set
        System.out.println(set);//[spider essence, rabbit paper, xiaohaitong, zhizunbao, calf, cerebellar axe, Zixia fairy]
        System.out.println(set.containsAll(set2));//Judge whether all elements of set2 set are in the set
        System.out.println(set.removeAll(set2));//Delete all elements belonging to set2 set in set set
        System.out.println(set);//[spider essence, supreme treasure, Zixia fairy]
        System.out.println(set.retainAll(set2));//Only the common elements belonging to the set and set2 sets in the set set are reserved
        System.out.println(set);//[]

		//5. Iteration of sets
		Iterator<String> it = set2.iterator();//5.1 get iterator of collection
		while(it.hasNext()) {//5.2 judge whether the set has the next element
			String s = it.next();//5.3 if yes, loop through to get the currently traversed element
			System.out.println(s);
		}
    }
}

3.6 exercise: Set related test 2

Create package: CN tedu. collection
Create class: student java

package cn.tedu.collection;

import java.util.Objects;

//1. Create a custom reference type Student
public class Student {
    //2. Create attributes
    String name;//full name
    int id;//Student number

    //3. Provide full parameter structure of this class
    public Student(String name, int id) {
        this.name = name;
        this.id = id;
    }
    //3.2 toString() for student class
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", id=" + id +
                '}';
    }
    //3.3 add equals() and hashCode() rewritten by student class
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return id == student.id && Objects.equals(name, student.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, id);
    }
}

3.6 exercise: Set related test 2

Create package: CN tedu. collection
Create class: testset2 java

package cn.tedu.collection;

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

/*This class is used to further test set*/
public class TestSet2 {
    public static void main(String[] args) {
        //4. Create set object set
        Set<Student> set = new HashSet<>();

        //5. Create an object of custom class Student
        Student s1 = new Student("Zhang San",3);
        Student s2 = new Student("Li Si",4);
        Student s3 = new Student("Li Si",4);
        //6. Store the created Student object into the set set
        set.add(s1);
        set.add(s2);
        set.add(s3);
        /*If the type we define is stored in the set
        * You need to add overridden equals() and hashCode() to the custom class to remove duplication
        * Otherwise, it will be considered that the address values of s2 and s3 are different. They are two different objects and will not be duplicated*/
        System.out.println(set);
    }
}

4 expansion

HashMap expansion
Growth factor:
static final float DEFAULT_LOAD_FACTOR = 0.75f;
The previous description has found that when your space is only 10, it is easy to cause the address corresponding to the hashcode of two objects to be one location. This will cause two objects to form a hash bucket (linked list). At this time, there is a parameter of loading factor. The default value is 0.75. If you have 100 hashmap space, the hashmap needs to be expanded when you insert 75 elements. Otherwise, it will form a long hash bucket structure, which will increase the time for query and insertion, because it needs to compare equals one by one. But you can't make the loading factor very small, such as 0.01, which is obviously inappropriate. Frequent capacity expansion will greatly consume your memory. At this time, there is a balance. The default value in jdk is 0.75. Of course, the load factor can be adjusted according to your actual situation.