Double column collection Map and its subclasses

Double-column collection Map and its subclasses

• Map collection
• HashMap collection
• LinkedHashMap collection
• TreeMap collection

Map collection

Map set is the ancestor class of all double-column sets. The so-called double-column set means that an element in the set is composed of two parts, namely key and value, also called key-value pair. The elements in the Map collection are stored in the form of key-value pairs. Each key corresponds to a value, and the keys in the collection cannot be repeated, but the values can be repeated.

• Application scenarios

1. When we encounter data that corresponds to each other during development, we can use Map collection storage, such as a mobile phone corresponding to a price, a city corresponding to a weather, etc…

• Common methods

Method	Function
put(K key, V value)	Add elements
size()	Get the collection size
isEmpty()	Determines whether the collection is empty. If it is empty, it returns true, otherwise it returns false
get(Object key)	Get the corresponding value based on the key
remove(Object key)	Delete the entire element based on the key
containsKey(Object key)	Judge whether the set contains a certain key
containsValue(Object value)	Judge the set Whether it contains a certain value
Set keySet()	Get the set of all keys
Collection values()	Get all values of the Map collection
putAll(Map list )	Add one collection to another collection
clear()	Clear the collection

public class Demo01 {<!-- -->
    public static void main(String[] args) {<!-- -->
        Map<String,Integer> list = new HashMap();
        // put(K key, V value) add element
        list.put("Shi Hao",24);
        list.put("Ye Fan",21);
        list.put("Chu Feng",18);

        // size() gets the collection size
        int size = list.size();
        System.out.println(size);

        // isEmpty() determines whether the collection is empty. If it is empty, it returns true, otherwise it returns false.
        boolean empty = list.isEmpty();
        System.out.println(empty);

        // get(Object key) gets the corresponding value based on the key
        Integer age = list.get("Shi Hao");
        System.out.println("Shi Hao:" + age);

        // remove(Object key) removes the entire element based on the key
        list.remove("Chu Feng");
        System.out.println(list);

        // containsKey(Object key) determines whether the collection contains a certain key
        boolean isName = list.containsKey("Ye Fan");
        System.out.println(isName);

        // containsValue(Object value) determines whether the collection contains a certain value
        boolean isAge = list.containsValue(99);
        System.out.println(isAge);

        // Set<K> keySet() gets the set of all keys
        Set<String> keySet = list.keySet();
        System.out.println(keySet);

        // Collection<V> values() gets all the values of the Map collection
        Collection<Integer> values = list.values();
        System.out.println(values);

        // putAll(Map<? extends K, ? extends V> list) adds one collection to another collection
        Map<String,Integer> temp = new HashMap<>();
        temp.putAll(list);
        System.out.println(temp);

        // clear() clears the collection
        list.clear();
        System.out.println(list);
    }
}

• How to traverse a Map collection

Key search value

1. Get all the keys in the set through the keySet() method and save them into a Set collection
2. Traverse the Set collection by enhancing the for loop, get each key, and then get the value corresponding to the key through the get() method in the Map collection to complete the traversal.

public class Demo02 {<!-- -->
    public static void main(String[] args) {<!-- -->
        Map<String,Integer> list = new HashMap<>();
        list.put("Caojia",19);
        list.put("ganqiao",17);
        list.put("Shinji",21);

        Set<String> keySet = list.keySet();
        for (String key : keySet) {<!-- -->
            System.out.println(key + "->" + list.get(key));
        }
    }
}

Key-value pairs (more difficult)

1. Call the entrySet() method in the Map collection to obtain a Set collection of key-value pair type
2. By enhancing the for loop traversal, call the getKey() and getValue() methods to obtain the corresponding keys and values to complete the traversal.

public class Demo02 {<!-- -->
    public static void main(String[] args) {<!-- -->
        Map<String,Integer> list = new HashMap<>();
        list.put("Caojia",19);
        list.put("ganqiao",17);
        list.put("Shinji",21);

        Set<Map.Entry<String, Integer>> entries = list.entrySet();
        for (Map.Entry<String, Integer> entry : entries) {<!-- -->
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println(key + "->" + value);
        }
    }
}

Lambda (very simple)

1. Just use the format of forEach((k, v) -> {code}) to traverse

public class Demo02 {<!-- -->
    public static void main(String[] args) {<!-- -->
        Map<String,Integer> list = new HashMap<>();
        list.put("Caojia",19);
        list.put("ganqiao",17);
        list.put("Shinji",21);

        list.forEach((k,v) -> System.out.println(k + "->" + v));
    }
}

HashMap collection

The HashMap collection is an implementation class under the Map interface. It has the characteristics of unordered, no duplication, and no index. These features are implemented based on keys and have nothing to do with their corresponding values. The bottom layer of the HashSet collection is actually implemented using HashMap, but HashSet is the key in the HashMap and does not take its value. The bottom layer of the index HashMap is also implemented based on the hash table. Before JDK8, the hash table consisted of array + linked list, starting from JDK8 the hash table consists of array + linked list + red-black tree

• Steps to add elements to HashMap collection

1. First determine whether the underlying dynamic array is null. If it is null, perform expansion operation.
2. Calculate the hash value based on the key of the element to get the index into the array, and find the position of the index in the array
3. If no element exists at this position, create a new head node and insert it.
4. If there is an element at this position, determine whether the position is a linked list or a red-black tree.
5. If the index is a linked list, traverse the linked list, and if it is found that the key in the linked list is the same as the key of the inserted element, it will directly overwrite the value of the same key in the linked list. The same here is the same after comparing hashCode and equals.
6. If it is different, insert the element directly at the end of the linked list, and then determine whether the length of the linked list is greater than 8. If it is greater than 8, convert the linked list into a red-black tree.
7. If the index is a red-black tree, traverse the red-black tree. If it is found that the key on the node is the same as the key of the inserted element, the value on the node will be overwritten.
8. If different, insert the element at the appropriate position in the tree

• Features of HashMap collection

1. The performance of adding, deleting, modifying and checking data is good.

LinkedHashMap collection

LInkedMap is a subclass of HashMap collection. The elements in the collection have the characteristics of ordered, non-repeating, and non-indexed. All characteristics are determined by the characteristics of the key.

• underlying principles

1. The underlying principle of LinkedHashMap is based on hash tables and double linked lists.
2. In fact, the underlying layer of the LInkedHashSet collection is implemented based on LInkedHashMap. The value of LInkedHashMap is the key of LInkedHashMap.

TreeMap collection

The TreeMap collection is a subclass of the Map collection. Its elements are non-repeating, non-indexable, and sortable according to the key (default ascending order by size)

• underlying principles

1. The bottom layer of the TreeMap collection is implemented based on red-black trees, and the performance of addition, deletion and query is good.
2. In fact, the bottom layer of TreeSet is implemented based on TreeMap, and the value of TreeSet is the key of TreeMap.

• TreeMap sorting method
• Note: TreeMap determines the unique value based on the sorting attribute. In other words, if the attribute values used for sorting are the same, TreeMap will overwrite the old value, as follows:

1. Method 1: Let the class implement the Compareble interface and rewrite the comparaTo method to formulate rules

public class Demo03 {<!-- -->
    public static void main(String[] args) {<!-- -->
        TreeMap<Student,String> list = new TreeMap<>();
        list.put(new Student("Liu Bei",23),"Shu");
        list.put(new Student("Cao Cao",33),"Wei Guo");
        list.put(new Student("Sun Quan",21),"Wu Guo");

        list.forEach((k,v) -> System.out.println(k + "->" + v));
    }
}

class Student implements Comparable<Student> {<!-- -->
    private String name;
    private int age;

    public Student() {<!-- -->
    }

    public Student(String name, int age) {<!-- -->
        this.name = name;
        this.age = age;
    }

    /**
     * Obtain
     * @return name
     */
    public String getName() {<!-- -->
        return name;
    }

    /**
     * set up
     * @param name
     */
    public void setName(String name) {<!-- -->
        this.name = name;
    }

    /**
     * Obtain
     * @return age
     */
    public int getAge() {<!-- -->
        return age;
    }

    /**
     * set up
     * @param age
     */
    public void setAge(int age) {<!-- -->
        this.age = age;
    }

    public String toString() {<!-- -->
        return "Student{name = " + name + ", age = " + age + "}";
    }

    @Override
    public int compareTo(Student o) {<!-- -->
        return this.getAge() - o.getAge();
    }
}

2. Method 2: By calling the parameterized constructor of the TreeSet collection, you can set the Comparator object (comparator object, used to formulate comparisons

public class Demo03 {<!-- -->
    public static void main(String[] args) {<!-- -->
        TreeMap<Student,String> list = new TreeMap<>((o1, o2) -> o1.getAge() - o2.getAge());
        list.put(new Student("Liu Bei",21),"Shu");
        list.put(new Student("Cao Cao",33),"Wei Guo");
        list.put(new Student("Sun Quan",24),"Wu Guo");

        list.forEach((k,v) -> System.out.println(k + "->" + v));
    }
}

class Student {<!-- -->
    private String name;
    private int age;

    public Student() {<!-- -->
    }

    public Student(String name, int age) {<!-- -->
        this.name = name;
        this.age = age;
    }

    /**
     * Obtain
     * @return name
     */
    public String getName() {<!-- -->
        return name;
    }

    /**
     * set up
     * @param name
     */
    public void setName(String name) {<!-- -->
        this.name = name;
    }

    /**
     * Obtain
     * @return age
     */
    public int getAge() {<!-- -->
        return age;
    }

    /**
     * set up
     * @param age
     */
    public void setAge(int age) {<!-- -->
        this.age = age;
    }

    public String toString() {<!-- -->
        return "Student{name = " + name + ", age = " + age + "}";
    }
}