Map interface takes you to learn advanced features of Java language

Map interface

I have learned the Collection interface and its corresponding sub-interfaces before, and I can find that all the data stored in the Collection interface are only single objects, and in the data structure, in addition to saving a single object, binary pairs can also be stored. Objects are stored in the form of key=value, and the core meaning of storing binary objects is to obtain the corresponding value through the key.

In development, the purpose of saving data in the Collection collection is for output, and the purpose of saving data in the Map collection is to search for keys.

The Map interface is the largest parent interface for storing binary objects. The interface is defined as follows:

public interface Map
This interface is an independent parent interface, and the types of Key and Value need to be set when instantiating the interface object, that is, two contents need to be saved during the overall operation. There are many operation methods defined in the Map interface, but The following core operating methods need to be kept in mind.

The data in the Map collection is stored in the form of "key=value", and the data in it is not allowed to be repeated when using the of() method. If it is repeated, an "IllegalArgumentException" exception will occur. If the set content If it is null, a "NullPointerException" will occur.

The of() method seen now is not strictly a standard usage of the Map collection, because in normal development, the subclass of the Map collection needs to be used to instantiate the interface object, and the commonly used subclasses: HashMap, HashTable , TreeMap, LinkedHashMap.

HashMap subclass
HashMap is the most common subclass of the Map interface. The main feature of this class is unordered storage. Let’s first observe the definition of the HashMap subclass through the Java document:

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
The definition and inheritance form of this class conforms to the previous collection definition form, and the abstract class is still provided and the Map interface still needs to be implemented repeatedly.

HashMap subclass

Example: Observing the use of the Map collection

import java.util.HashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new HashMap();
map. put("one",1);
map. put("two",2);
map.put("one",101); //key repeat
map.put(null,0); //key is null
map.put("zero",null); //value is null
System.out.println(map.get("one")); //key exists: 101
System.out.println(map.get(null)); //key exists: 0
System.out.println(map.get("ten")); //key does not exist: null
}
}
The above operation form is the most standard processing form used by the Map collection. Through the code, it can be found that the Map interface instantiated through HashMap can save null data for key or value. Instead of an error, a replacement of the content occurs.

However, the put() method provided in the Map interface itself provides a return value, so this return value refers to returning the old value when the key is repeated.
Example: Observing the put() method

import java.util.HashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new HashMap();
System.out.println(map.put("one", 1)); //key is not repeated, return null: null
System.out.println(map.put("one", 101)); //key is repeated, return old data: 1
}
}
When the content of the same key is set, the put() method will return the original data content.

After clarifying the basic functions of HashMap, the next step is to study the source code given in HashMap. A large amount of data must be stored in HashMap, so for data storage, let's see how HashMap operates:

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
When using no parameter construction, there will be a loadFactor attribute, and the default content of this attribute is "0.75" (static final float DEFAULT_LOAD_FACTOR = 0.75f;)

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
When using the put() method to save data, a putVal() method will be called, and the key will be hashed at the same time (generate a hash code), and for the putVal() method, a Node node class will be provided for data storage. Save, and in the process of using the putVal() method, a resize() method will be called to expand the capacity.

Interview question: How to achieve capacity expansion when performing the put() operation of HashMap?

A "DEFAULT_INITIAL_CAPACITY" constant is provided in the HashMap class as the initial capacity configuration, and the default size of this constant is 16 elements, which means that the default maximum content that can be saved is 16;
When the capacity of the saved content exceeds a threshold (DEFAULT_LOAD_FACTOR=0.75f), which is equivalent to "capacity * threshold = 12", the capacity will be expanded when 12 elements are saved;
When expanding, HashMap adopts the double expansion mode, that is, the capacity is expanded by 2 times each time.
Interview question: Please explain the working principle of HashMap (started after JDK1.8)

Data storage in HashMap is still done using the Node class, so in this case it proves that there are only two data structures that can be used: linked list (time complexity "O(n)"), binary tree (time complexity "O(n)") (logn)");
Starting from JDK1.8, the implementation of HashMap has changed, because it has to adapt to the massive data problem in the era of big data, so its storage has changed, and a constant is provided inside the HashMap class: "static final int TREEIFY_THRESHOLD = 8;", when using HashMap to save data, if the saved data does not exceed the threshold 8 (TREEIFY_THRESHOLD), then it will be stored in the form of a linked list. If it exceeds the threshold, the linked list will be converted into a red-black tree to achieve The balance of the tree, and the use of left-handed and right-handed to ensure the query performance of the data.
LinkedHashMap subclass
Although HashMap is the most commonly used subclass in the Map collection, the data stored in it is out of order (ordered or not has no effect on the Map), if you want the order of the stored data in the Map collection to increase its order , then you can replace the subclass with LinkedHashMap (based on the linked list), and observe the definition form of the LinkedHashMap class:

public class LinkedHashMap extends HashMap implements Map
Since it is stored in a linked list, generally the amount of data should not be particularly large when using the LinkedHashMap class, because it will cause a rise in time complexity. Through the inheritance structure, it can be found that LinkedHashMap is a subclass of HashMap. The inheritance relationship is as follows:

LinkedHashMap

Example: Using LinkedHashMap

import java.util.LinkedHashMap;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new LinkedHashMap();
map. put("one", 1);
map. put("two", 2);
map. put("one", 101);
map. put("null", 0);
map. put("zero", null);
System.out.println(map); //{one=101, two=2, null=0, zero=null}
}
}
Through the program execution at this time, it can be found that when LinkedHashMap is used for storage, the storage order of all data is the order of addition.

HashTable subclass
The HashTable class was provided from JDK1.0, and Vector and Enumeration belonged to the earliest batch of dynamic array implementation classes. Later, in order to keep it, it was allowed to implement an additional Map interface. The definition of the HashTable class is as follows:

public class Hashtable extends Dictionary implements Map, Cloneable, Serializable
The inheritance structure of HashTable is as follows:

HashTable subclass

Example: Observe the use of the HashTable subclass

import java.util.Hashtable;
import java.util.Map;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception {
Map map = new Hashtable();
map. put("one", 1);
map. put("two", 2);
map. put("one", 101);
// map.put(null, 0); // cannot be empty
// map.put("zero",null); //Cannot be empty, Exception in thread "main" java.lang.NullPointerException
System.out.println(map); // {two=2, one=101}
}
}
Through observation, it can be found that the key or value set when storing data in the HashTable is not allowed to be null, otherwise a NullPointerException will occur.

Interview question: Please explain the difference between HashMap and HashTable?

The methods in HashMap are all asynchronous operations and are not thread-safe. HashMap allows saving null data;
HashTable is a synchronization method (thread-safe), HashTable does not allow to save null, otherwise NullPointerException will occur;