1, Map interface

1. Overview of map interface

• The Map interface is parallel to the Collection interface
• The mapping set represented by the Map interface is used to store double column data, that is, key value (key value pair).
• The Map interface encapsulates the key value in a static internal class, and the two attributes of the class represent key and value respectively

Understanding of key value pairs in Map

• All key s in the Map are unordered and non repeatable, so they can be regarded as stored in a Set. The class in which they can be located should override equals() and hashCode()
• All values can be repeated, but they are out of order. The class where value is located should override equals()
• When the put operation is performed in the Map, the underlying storage is to store the key value as two attributes of the Entry object. The Entry objects stored in the Map are one by one
• Entry: unordered and non repeatable. Use Set to store all entries

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // Hash value of key
        final K key; // Store key value
        V value; // Store value
        Node<K,V> next; // Because elements with the same hash value are not necessarily the same. Therefore, the linked list is used to hang it in the same bucket
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
        /*
         Here are some methods of this class, which will not be shown here
        */
    }

2. Map interface implementation class

        |------ Map : Double column data: store key value pairs, similar to functions y = f(x)
            |------HashMap: As Map The main implementation class of thread is unsafe; Can fly null of key and value
                |------ LinkedHashMap: Guaranteed traversal map Elements can be traversed in the order of addition
                        Reason: in the original HashMap Based on the underlying structure, a pair of pointers are added to point to the previous and subsequent elements
                        For frequent traversal operations, the execution efficiency of this class is higher than that of HashMap
            |------ TreeMap: Ensure that the added key-value Sort and realize sorting traversal; At this time, the sorting is based on the use of key Natural sorting or custom sorting
                            Red and black trees are used at the bottom
            |------ Hashtable: Old implementation class, thread safety; Cannot store null of key and value
                |------ Properties: Commonly used to process configuration files. key and value All String type

3. The underlying implementation principle of the main implementation class HashMap: taking jdk7 as an example

• Map<String,Integer> map = new HashMap<>();
  • After instantiation, the bottom layer creates an array Entry[] table with a length of 16;
• The process of putting elements in HashMap:
  • map.put(key1,value1);

        1.call key1 Class hashCode(0 calculation key1 The hash value is obtained after calculation Entry Storage location in array
              If the data in this location is empty, the key-value1 Added successfully
              2. If the data in this location is not empty, it means that there are one or more data in this location, which exist in the form of linked list and can be compared key1 And the hash value of one or more existing data:
                 If key1 The hash value of is different from that of the existing data. At this time key1-value1 Added successfully
                  3. If key1 The hash value of is the same as that of an existing data. Continue to compare: call key1 Class equals()method
                      If equals()return false,It indicates that the two data are not the same, and this process continues until all the elements in a bucket are compared(All elements in the linked list at the index position of an array)，Indicates that there is no to add in the bucket key1-value1，Then at this time key1-value1 Added successfully
                      If equals()return true: use value1 Replace the same original key1 of value Value (at this time) put Method has the function of modification)
          Supplement: for 2 and 3: at this time key1-value1 And the original data are stored in a linked list

      In the process of continuous addition, capacity expansion will be involved: when the number of arrays stored exceeds the default value and the location to be stored is not empty, capacity expansion will be carried out; Default capacity expansion method: expand the capacity to twice the original capacity and copy the original data

JDK7 and JDK8 implement HashMap differently at the bottom layer:

1. new HashMap(): the bottom layer does not create an array with a length of 16 bits
2. The underlying data of jdk8 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. The underlying structure of jdk7 is only data + linked list. The underlying structure of jdk8 is array + linked list + red black tree
   When the number of elements in an index position of the array in the form of linked list is > 8 and the current data length is > 64, all data in this index position will be stored in red black tree instead

4. Static variable description of HashMap in jdk8

1. static final int DEFAULT_ INITIAL_ CAPACITY = 1 << 4; // Aka 16 default initialization capacity: the length of the underlying array when it is first created
2. static final int MAXIMUM_ CAPACITY = 1 << 30; The default maximum capacity is the maximum length of the array allowed to be created during initialization / expansion
3. static final float DEFAULT_LOAD_FACTOR = 0.75f; Default load factor: a scale factor, which is generally used to calculate the critical value, indicating the capacity expansion when the storage capacity reaches the percentage of the total capacity
4. static final int TREEIFY_THRESHOLD = 8; Treeing threshold: (one of the conditions for jdk8 to expand it into a red black tree) when the length of the linked list at a certain location exceeds 8, it reaches one of the conditions for expanding into a red black tree
5. static final int UNTREEIFY_THRESHOLD = 6; Linked list domain value: when the number of nodes of the tree is less than this value, the red black tree on the bucket is reduced to a linked list
6. static final int MIN_TREEIFY_CAPACITY = 64; Minimum treeing threshold: when the array capacity exceeds this value, one of the conditions for treeing is reached: when the array length exceeds min_ TREEIFY_ Capability, and the length of the linked list on a bucket (position) exceeds TREEIFY_THRESHOLD, the linked list on the bucket is converted into a red black tree
7. threshold: the critical value, which is generally obtained by the loading factor * array length. During initialization, the critical value is 16 * 0.75 = 12, that is, when adding a key value pair, if the number of existing elements in the array exceeds 12 and there are elements in the position of the newly added elements, the capacity will be expanded.

5. Methods defined in the map interface:

(1) Methods of addition, deletion, modification and query:

1. put(key,value); // add to
2. public V put(K key, V value) / / modify: when the keys are the same, the new value will overwrite the old value
3. public V remove(Object key) / / delete and remove the key value pair of the specified key value, and return the value
4. void clear(); // empty
5. V get(Object key) / / find
6. boolean containsKey(Object key); Whether to include the specified key
7. boolean containsValue(Object value); Whether to include the specified value
8. int size(); Gets the number of key value pairs in the map
9. boolean isEmpty(); Is the map empty

(1) Traversal method of map:

• (1) Traverse all key s
  • Call method set < k > keyset(); Get the collection of keys

        System.out.println("\n Traverse all key collection");
        Set set = map.keySet();
        for (Object o : set) {
            System.out.println(o);
        }

• (2) Traverse all value s
  • Call the method collection < V > values(); Get the collection of values

        System.out.println("\n Traverse all value");
        Collection collection = map.values();
        for (Object o : collection) {
            System.out.println(o);
        }

• (3) Traverse all key value pairs
  • Method 1: call keySet to find all keys, and then find value through key

        System.out.println("\n Mode 1 traverses all key-value");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        Iterator iterator = entrySet.iterator();
        while(iterator.hasNext()){
            Map.Entry<String,Integer> entry = (Map.Entry<String,Integer>)iterator.next();
            System.out.println(entry.getKey()+"-------->"+entry.getValue());
        }

• • Method 2: directly call the entrySet() method to get the set of key value pairs

        System.out.println("\n Method 2: call keySet Find all key，adopt key Find again value");
        Set keySet = map.keySet();
        Iterator iterator2 = keySet.iterator();
        while(iterator2.hasNext()){
            String key = (String) iterator2.next();
            System.out.println(key+"------>"+map.get(key));
        }

2, Collections utility class

• Tool classes for operating Collection and Map
• The difference between collections and Collections: collections is the Collection interface for storing single column data, the operation of collections, and the tool class of Collection and Map

common method

1. Public static void reverse (List <? > List) reverses the order of elements in the List
2. Public static void shuffle (list <? > list) randomizes the order of elements in the list

	@Test
    public void test1() {
        List<Integer> list = new ArrayList<>();
        list.add(12);
        list.add(96);
        list.add(-15);
        list.add(0);
        System.out.println("list = " + list); // list = [12, 96, -15, 0]

        Collections.reverse(list);
        System.out.println("yes list After reversing" + list); // After reversing the list [0, - 15, 96, 12]

        Collections.shuffle(list);
        System.out.println("yes list After random sorting" + list); // After randomly sorting the list [- 15, 0, 12, 96]
    }

1. public static <T extends Comparable<? Super T > > void sort (list < T > list) sorts the list naturally
2. Public static < T > void sort (list < T > list, comparator <? Super T > C) customizes the list
3. Public static void swap (list <? > list, int i, int j) exchanges the ith element and the jth element in the list

	@Test
    public void test1() {
        List<Integer> list = new ArrayList<>();
        list.add(12);
        list.add(96);
        list.add(-15);
        list.add(0);
        Collections.sort(list);
        System.out.println("yes list After natural sorting:" + list); // After natural sorting of the list: [- 15, 0, 12, 96]
        Collections.shuffle(list);
        System.out.println("yes list After random sorting:"+list); // After random sorting of the list: [- 15, 12, 0, 96]
        Collections.sort(list,(x,y)-> -x.compareTo(y));
        System.out.println("yes list Arrange in descending order(Custom sorting): "+list); // Sort the list in descending order (customized sort): [96, 12, 0, - 15]
        Collections.swap(list,1,2);
        System.out.println("After swapping the second and third elements:"+list); // After exchanging the first and second elements: [96, 0, 12, - 15]
    }

1. public static <T extends Object & Comparable<? Super T > > t max (collection <? Extensions T > Coll) returns the largest element in a given set according to the natural sorting of elements
2. Public static < T > t max (collection <? Extends T > coll, Comparator <? Super T > COMP) returns the largest element in a given set according to the order specified by the Comparator
3. public static <T extends Object & Comparable<? Super T > > t min (collection <? Extensions T > Coll) returns the smallest element in a given set according to the natural sorting of elements
4. Public static < T > t min (collection <? Extensions T > coll, Comparator <? Super T > COMP) returns the smallest element in a given set according to the order specified by the Comparator
5. Public static int frequency (collection <? > C, object o) returns the number of occurrences of the specified element in the specified collection
6. Public static < T > Boolean replaceall (List < T > List, t oldval, t newval) replaces the old value of the List with the new value

	@Test
    public void test3(){
        List<Integer> list = Arrays.asList(new Integer[]{1, 2, 3, 5, 1, 2, 5, 3, 4, 9, 8, 7, 1, 1, 0, 2, -1}); 
        System.out.println(list); // [1, 2, 3, 5, 1, 2, 5, 3, 4, 9, 8, 7, 1, 1, 0, 2, -1]
        System.out.println("aggregate list Number of occurrences in 1:"+Collections.frequency(list,1)); // Number of occurrences of 1 in the set list: 4
        Collections.replaceAll(list,1,91);
        System.out.println("Set list Replace all 1 in with 91,list = "+list);
        	// Replace all 1 in the set list with 91,list = [91, 2, 3, 5, 91, 2, 5, 3, 4, 9, 8, 7, 91, 91, 0, 2, -1]
    }

1. Public static < T > void copy (list <? Super T > DeST, list <? Extensions T > src) copies the contents of src to dest

• Note: the copy() method requires the number of elements in the destination set dest to be greater than or equal to src, otherwise an out of bounds exception will be thrown

Collections.copy() source code:

    public static <T> void copy(List<? super T> dest, List<? extends T> src) {
        int srcSize = src.size(); // The size() method is called, that is, the number of elements in the collection
        if (srcSize > dest.size()) 
            throw new IndexOutOfBoundsException("Source does not fit in dest");
     /**The rest of the code*******/
    }

	// For collections Copy() to test
    public void test4(){
        List<Integer> list = Arrays.asList(new Integer[]{1, 2, 3, 5, 1, 2, 5, 3, 4, 9, 8, 7, 1, 1, 0, 2, -1});
        List<Integer> newList = new ArrayList<>(Arrays.asList(new Integer[list.size()])); // Use the constructor ArrayList < > (collection Coll), create an array as large as list, convert it into list and pass it into the constructor
        System.out.println("Before copying:newList = " + newList);
        Collections.copy(newList,list);
        System.out.println("After copying:newList: newList = "+newList);
    }

// Operation results:
Before copying:newList = [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
After copying:newList: newList = [1, 2, 3, 5, 1, 2, 5, 3, 4, 9, 8, 7, 1, 1, 0, 2, -1]