Map interface

summary

• Map:jdk1,2, double column data, storing data of key value pair
  • HashMap:jdk1.2. As the main implementation class of Map, the thread is unsafe and efficient. It can store null key and value
    • LinkedHashMap:jdk1. 4. The subclass of HashMap ensures that when traversing Map elements, traversal can be realized in the order of addition Reason: Based on the original HashMap underlying structure, 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:jdk1.2. Ensure to sort according to the added key value pairs to realize sorting traversal At this time, consider the natural sorting or customized sorting of keys The use is relatively limited Red and black trees are used at the bottom
  • Hashtable:jdk1.0, as an old implementation class, it is not used much. It is thread safe and inefficient null key and value cannot be stored
    • Properties: commonly used to process configuration files Both key and value are String types

Understanding of Map structure

• The keys in the Map cannot be repeated and out of order. Use set to store - > (take HashMap as an example) the class where the key is located should override equals() and hashCode()
• The values in the Map can be repeated and unordered (stored with Collection, single column data). - > The class where value is located should override equals()
• A key value pair key value constitutes an Entry object. All in put s in the Map are entries, and key value in the Entry
• Entry is out of order and cannot be repeated Store with set

Underlying implementation principle of HashMap

• jdk7 and before: array + linked list
• jdk8: array + linked list + red black tree (to improve efficiency)

Take 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): add

  • 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, it is obtained in the Entry
    The storage location in the array
  • If the data in this location is empty, the Entry(key1-value1) is added successfully. - > Situation 1
  • If the data in this location is not empty, it means that there are only 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 that of existing data, key1-value1 is added successfully. - > Situation II
    • If the hash value of key1 is the same as that of an existing data (key2-value2), continue the comparison: call the equals() method of the class where key1 is located, and compare:
      • If equals() returns false, key1- value1 is added successfully. - > Situation III
      • If equals() returns true, replace value2 with value1

• Case 2 and case 3: key1-value1 and the original data are stored in a 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 copy the original data

• constructor
  

• Create the critical value of array length 16, loading factor 0.75f,threshold=12, and start capacity expansion after 12
  

• put() method
  

JDK8 is different from JDK7 in the underlying implementation

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

• a key:
  • Default capacity of HashMap: 16
  • Default load factor for HashMap: 0.75
  • Critical value of capacity expansion = capacity * loading factor: 12
  • If the length of the linked list in the Bucket is greater than the default value, it will be converted into a red black tree: 8
  • Minimum hash table capacity when nodes in bucket are treelized: 64
    

Underlying implementation principle of LinkedHashMap (understand)

• Can record the sequence of added elements
  

Methods defined in Map (take HashMap as an example)

1. Object put(Object key,Object value): adds (or modifies) the specified key value to the current map object
2. void putAll(Map m): store all key value pairs in m into the current map
3. Object remove(Object key): removes the key value pair of the specified key and returns value
4. void clear(): clear all data in the current map

• Operation of element query

1. Object get(Object key): get the value corresponding to the specified key
2. boolean containsKey(Object key): whether the specified key is included
3. boolean containsValue(Object key): whether the specified value is included
4. int size(): returns the number of key value pairs in the map
5. boolean isEmpty(): judge whether the current map is empty
6. boolean equals(Object obj): judge whether the current map and parameter object obj are equal

package Map;

import org.junit.Test;

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

public class MapTest {
    //Add, delete, modify put putAll remove clear
    @Test
    public void test1() {
        Map map = new HashMap();
        map.put("AA", 123);
        map.put(34, 123);
        map.put("BB", 13);
        //Object put(Object key,Object value): adds (or modifies) the specified key value to the current map object
        map.put("AA", 12);
        //void putAll(Map m): store all key value pairs in m into the current map
        System.out.println(map);
        Map map1 = new HashMap();
        map1.put("CC", 123);
        map1.put("DD", 123);
        map.putAll(map1);
        System.out.println(map);

        //Object remove(Object key): removes the key value pair of the specified key and returns value
        Object value = map.remove("CC");
        System.out.println(value);
        System.out.println(map);

        //void clear(): clear all data in the current map
        map.clear();
        System.out.println(map.size());//0
        System.out.println(map);//{}
    }

    @Test
    public void test2() {
        Map map = new HashMap();
        map.put("AA", 123);
        map.put(34, 123);
        map.put("BB", 13);

        //Object get(Object key): get the value corresponding to the specified key
        System.out.println(map.get(45));

        //boolean containsKey(Object key): whether the specified key is included
        boolean isExist = map.containsKey("BB");
        System.out.println(isExist);
        //boolean containsValue(Object key): whether the specified value is included
        isExist = map.containsValue(123);
        System.out.println(isExist);
        //int size(): returns the number of key value pairs in the map
        System.out.println(map.size());

        //boolean isEmpty(): judge whether the current map is empty
        map.clear();
        System.out.println(map.isEmpty());

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

• Methods of meta view operation

1. Set keySet(): returns the set set composed of all keys,
2. Collection values(): returns the collection collection composed of all values
3. Set entrySet(): returns the set set composed of all key value pairs

 @Test
    public void test3() {
        Map map = new HashMap();
        map.put("AA", 123);
        map.put(34, 123);
        map.put("BB", 13);

        //Set keySet(): returns the set set composed of all keys
        //Traverse all key sets
        Set set = map.keySet();
        Iterator iterator = set.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        System.out.println();
        //Collection values(): returns the collection collection composed of all values
        //Traverse all value sets
        Collection values = map.values();
        Iterator iterator1 = values.iterator();
        while (iterator1.hasNext()) {
            System.out.println(iterator1.next());
        }
        System.out.println();
        //Set entrySet(): returns the set set composed of all key value pairs
        //Traverse all key values
        //Mode 1:
        Set entrySet = map.entrySet();
        Iterator iterator2 = entrySet.iterator();
        while (iterator2.hasNext()) {
            Object obj = iterator2.next();
            //All elements in the entry set collection are entries
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey() + "=" + entry.getValue());
        }
        System.out.println();
        //Mode 2:
        Set keySet = map.keySet();
        Iterator iter = keySet.iterator();
        while (iter.hasNext()) {
            Object key = iter.next();
            Object value = map.get(key);
            System.out.println(key + "=" + value);
        }


    }

• Summary: common methods
• Add: put(Object key,Object value)
• Delete: remove(Object key)
• Modify: put(Object key,Object value)
• Query: get(Object key)
• Length: seze()
• Traversal: keySet() / values() / entrySet()
• Unordered, no insert

TreeMap natural sorting and custom sorting

• 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

package Map;

import org.junit.Test;

import java.util.*;

public class TreeMapTest {

    //Natural sorting
    @Test
    public void test() {
        TreeMap treeMap = new TreeMap();
        User u1 = new User("Tom", 23);
        User u2 = new User("Jon", 22);
        User u3 = new User("Jerry", 25);
        User u4 = new User("Jack", 12);
        treeMap.put(u1, 98);
        treeMap.put(u2, 78);
        treeMap.put(u3, 86);
        treeMap.put(u4, 67);

        Set keySet = treeMap.keySet();
        Iterator iter = keySet.iterator();
        while (iter.hasNext()) {
            Object key = iter.next();
            Object value = treeMap.get(key);
            System.out.println(key + "=" + value);
        }
    }

    //Custom sorting
    @Test
    public void test2() {
        Comparator com = new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof User && o2 instanceof User) {
                    User u1 = (User) o1;
                    User u2 = (User) o2;
                    return Integer.compare(u1.getAge(), u2.getAge());
                }
                throw new RuntimeException("The types entered do not match");

            }
        };
        TreeMap treeMap = new TreeMap(com);
        User u1 = new User("Tom", 23);
        User u2 = new User("Jon", 22);
        User u3 = new User("Jerry", 25);
        User u4 = new User("Jack", 12);
        treeMap.put(u1, 98);
        treeMap.put(u2, 78);
        treeMap.put(u3, 86);
        treeMap.put(u4, 67);

        Set keySet = treeMap.keySet();
        Iterator iter = keySet.iterator();
        while (iter.hasNext()) {
            Object key = iter.next();
            Object value = treeMap.get(key);
            System.out.println(key + "=" + value);
        }
    }

}

class User implements Comparable {
    private String name;
    private int age;

    public User() {
    }

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return age == user.age && Objects.equals(name, user.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    //Sort by name and age
    @Override
    public int compareTo(Object o) {

        if (o instanceof User) {
            User user = (User) o;
//                return this.name.compareTo(user.name);
            int compare = this.name.compareTo(user.name);
            if (compare != 0) {
                return compare;
            } else {
                return Integer.compare(this.age, user.age);
            }
        } else {
            throw new RuntimeException("Input type mismatch");
        }
    }
}

Properties

• Properties: commonly used to handle configuration files. Both key and value are String types

• Create a JDBC Properties configuration file

package Map;

import java.io.FileInputStream;
import java.io.IOException;
import java.util.Properties;

public class PropertiesTest {
    public static void main(String[] args) {
        FileInputStream fis = null;
        try {
            Properties pros = new Properties();
            fis = new FileInputStream("jdbc.properties");
            pros.load(fis);//Load the file corresponding to the stream
            String name = pros.getProperty("name");
            String password = pros.getProperty("password");

            System.out.println("name = " + name + ", password = " + password);
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (fis != null) {

                try {
                    fis.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }

    }
}

Interview questions

Underlying implementation principle of HashMap

Similarities and differences between HashMap and Hashtable

Similarities and differences between CurrentHashMap and Hashtable

• Multithreading, segmented lock