The Map interface
Map and Collection exist side by side. Keys in a Map are stored in sets and cannot be duplicated, that is, classes corresponding to the same Map object. The hashCode() and equals() methods must be overridden. The String class is used as the Map’s “key”. There is a one-way one-to-one relationship between key and value. That is, the common implementation classes for a unique, identified value Map interface can always be found by specifying a key :HashMap, TreeMap, LinkedHashMap, and Properties. Among them, HashMap is the most frequently used implementation class of the Map interface
1. Common implementation class structure
| - Map: double row data, store the key - the value of the data - similar to the function of the high school: y = f (x) | - HashMap: as the main implementation class of the Map; Threads are unsafe and efficient; Store the key and the value of null | - LinkedHashMap: guarantee in traverse map elements, can be added according to the order of traversal. Reason: A pair of Pointers were added to the underlying structure of the original HashMap to point to the preceding and following elements. This class performs more efficiently than a HashMap for frequent traversal operations. | - TreeMap: guarantee according to add the key - value for sorting, sort through. Considering the key natural ordering or custom sorting at this time The underlying the use of red and black tree | - Hashtable: as the old implementation class; Thread-safe, inefficient; Unable to store the key and the value of null | - Properties: commonly used to handle the configuration file. Both keys and values are the underlying elements of a HashMap of String type: array + list (JDK 7.0 or earlier) Array + list + red-black tree (JDK 8.0 or later)Copy the code1.1 a HashMap
HashMap is the most frequently used implementation class of the Map interface.
Null keys and null values are allowed, and as with HashSet, the order of mapping is not guaranteed.
The set of all keys is a set: unordered and unrepeatable. So, the class that holds the key overrides equals() and hashCode()
A Collection of all values is a Collection: unordered and repeatable. So, the value class is overridden :equals()
A key-value constitutes an entry
The Set of all entries is a Set: unordered and unrepeatable
A HashMap determines that two keys are equal when they return true via equals() and the hashCode values are equal.
The HashMap criterion for determining the equality of two values is that they return true via equals().
Code examples:
@Test
public void test1(){
Map map = new HashMap();
map.put(null,123);
}
Copy the code1.2 LinkedHashMap
The underlying LinkedHashMap uses the same structure as HashMap because LinkedHashMap inherits from HashMap. The difference is that the LinkedHashMap provides Entry inside, replacing nodes in the HashMap. Like the Linkedhash Set, the LinkedHashMap maintains the iteration order of the Map: The iteration order is the same as the insertion order of key-value pairs. Example of this code:
@Test
public void test2(){
Map map = new LinkedHashMap();
map.put(123,"AA");
map.put(345,"BB");
map.put(12,"CC");
System.out.println(map);
}
Copy the code1.3 TreeMap
When TreeMap stores key-value pairs, sort them by key-value pairs. TreeMap ensures that all key-value pairs are in order.
The underlying TreeSet uses a red-black tree structure to store data
TreeMap Key order:
Natural sort: All TreeMap keys must implement the Comparable interface and all keys must be objects of the same class, otherwise ClasssCastEXception() will be thrown for custom sort: When you create a TreeMap, you pass in a Comparator object that sorts all the keys in the TreeMap. Comparable TreeMap is a standard for determining that two keys are equal. Two keys return 0 using the compareTo() or compare() methods.
1.4 Hashtable
Hashtable is an old Map implementation class, provided in JDK1.0. Unlike HashMap, Hashtable is thread-safe.
The implementation principle and function of Hashtable are the same as that of HashMap. Hash table structure is used in the bottom layer, which can be used interchangeably in many cases
Unlike HashMap., Hashtable does not allow null for keys and values.
Like a HashMap, a Hashtable does not guarantee the order of key-value pairs.
Hashtable specifies whether two keys are equal and two values are equal.
1.5 the Properties
The Properties class is a subclass of Hashtable, which is used to process Properties files
Since the keys and values in the Properties file are strings, the keys and values in the Properties file are strings
When accessing data, setProperty(String Key,String Value) and getProperty(String Key) methods are recommended
Code examples:
//Properties: used to handle configuration files. Public static void main(String[] args) {FileInputStream fis = null; try { Properties pros = new Properties(); fis = new FileInputStream("jdbc.properties"); pros.load(fis); 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(); }}}}Copy the code2. Understanding of storage structure:
— The class where keys are stored in a Map overrides equals() and hashCode() (for example, HashMap). Use Collection to store all values –> the value class overrides equals() as a key-value pair: key-values constitute an Entry object. Entries in a Map: Unordered and non-repeatable. Set is used to store all entries
3. Common methods
3.1 Add, Delete and Modify operations:
Object PUT (Object key,Object value) : Void putAll(map m): Stores all key-value pairs in M to the current map. Object remove(Object key) : Remove key-value pairs for specified keys and return value void clear() : Clears all data in the current map.
@Test
public void test1() { Map map = new HashMap(); //Object put(Object key,Object value) : Adds the specified key-value to (or modifies) the current map Object."AA", 123); map.put("ZZ", 251); map.put("CC", 110); map.put("RR", 124); map.put("FF", 662); System.out.println(map); //{AA=123, ZZ=251, CC=110, RR=124, FF=662} //Object put(Object key,Object value) : Add the specified key-value to (or modify) the current map."ZZ", 261); System.out.println(map); {AA=123, ZZ=261, CC=110, RR=124, FF=662} void putAll(Map m): void putAll(Map m): void putAll(Map m) map1.put("GG", 435); map1.put("DD", 156); map.putAll(map1); System.out.println(map); {AA=123, ZZ=261, CC=110, RR=124, FF=662, GG=435, DD=156} Remove key-value pairs for specified keys and return value Object value = map.remove("GG"); System.out.println(value); //435 System.out.println(map); //{AA=123, ZZ=261, CC=110, RR=124, FF=662, DD=156} //void clear() : clear all data in the current map. System.out.println(map.size()); //0 differs from the map = null operation system.out.println (map); / / {}}Copy the code3.2 Operation of element query:
Boolean containsKey(Object key) : Specifies whether to contain the specified key Boolean containsValue(Object value) : Int size() : returns the number of key-value pairs in the map Boolean isEmpty() : checks whether the map isEmpty Boolean equals(Object obj) : Example of code to determine whether the current map and parameter object obj are equal:
@Test
public void test2() {
Map map = new HashMap();
map.put("AA", 123);
map.put("ZZ", 251);
map.put("CC", 110);
map.put("RR", 124);
map.put("FF", 662); System.out.println(map); //{AA=123, ZZ=251, CC=110, RR=124, FF=662} //Object get(Object key) : obtain the value of the specified key system.out.println (map.get())"AA")); //123 // Boolean containsKey(Object key) : Specifies whether it contains the specified key system.out.println (map.containsKey("ZZ")); //true// Boolean containsValue(Object value) : Specifies whether it contains the specified value System.out.println(map.containsValue(123)); //true//int size() : returns the number of key-value pairs in the map system.out.println (map.size()); //5 // Boolean isEmpty() : check whether the current map isEmpty system.out.println (map.isempty ()); //falseMap map1 = new HashMap(); // Boolean equals(Object obj) : = new HashMap(); map1.put("AA", 123);
map1.put("ZZ", 251);
map1.put("CC", 110);
map1.put("RR", 124);
map1.put("FF", 662); System.out.println(map.equals(map1)); //true
}
Copy the code3.3 Metaview Operation methods:
Set keySet() : returns a Set of all keys. Collection Values () : returns a Set of all values. Set entrySet() : returns a Set of all key-value pairs.
@Test
public void test3() {
Map map = new HashMap();
map.put("AA", 123);
map.put("ZZ", 251);
map.put("CC", 110);
map.put("RR", 124);
map.put("FF", 662); System.out.println(map); //{AA=123, ZZ=251, CC=110, RR=124, FF=662} // Set keySet() : returns the Set Set of all keysset = map.keySet();
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -"); Collection values() : returns a Collection of all values. Collection values = map.values();for (Object obj :
values) {
System.out.println(obj);
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -- --"); //Set entrySet() : returns a Set of key-value pairs Set entrySet = map.entryset (); Iterator iterator1 = entrySet.iterator(); // Method 1:while(iterator1.hasNext()) { Object obj = iterator1.next(); Entry entry = (map.entry) obj; // Entries in entrySet are entry map.entry = (map.entry) obj; System.out.println(entry.getKey() +"-- >" + entry.getValue());
}
System.out.println("-- -- -- -- -- -- -- -- -- -- -- -- -- -"); // Set keySet = map.keyset (); Iterator iterator2 = keySet.iterator();while (iterator2.hasNext()) {
Object key = iterator2.next();
Object value = map.get(key);
System.out.println(key + "= ="+ value); }}Copy the codeSummary: Common methods:
Add: PUT (Object key,Object value) Delete: remove(Object key) Modify: PUT (Object key,Object value) Query: get(Object key) Length: size() Traversal: keySet() / values() / entrySet()
4. Memory structure description :(difficult points)
4.1 Implementation principle of HashMap in JDK 7.0
4.1.1 Storage Structure of HashMap:
JDK 7.0 or earlier: HashMap is an array + list structure.
JDK 8.0: HashMap is an array + linked list + red-black tree implementation
4.1.2 Object Creation and addition process:
HashMap map = new HashMap():
After instantiation, the bottom layer creates a one-dimensional array Entry[] table of length 16.
. You may have performed multiple put…
map.put(key1,value1):
First, we call the class hashCode() of Key1 to calculate the key1 hash value, which is computed by some algorithm to get the location in the Entry array. If the data in this position is empty, key1-value1 is added successfully. —- Case 1 If the data at this location is not empty, (meaning that one or more data (in the form of a linked list) exists at this location), compare the hash values of key1 with one or more existing data: If the hash value of key1 is different from the hash value of the existing data, key1-value1 is added successfully. —- Case 2 If the hash value of key1 is the same as the hash value of an existing data (key2-value2), continue the comparison: Call equals(key2) of the class where key1 is located, compare: if equals() returns false: key1-value1 was added successfully. —- case 3 If equals() returns true: replace value2 with value1.
Add: About case 2 and case 3: at this point key1-Value1 and the original data are stored as linked lists.
In the process of continuous addition, it will involve expansion problem, when the critical value is exceeded (and the location to be stored is not empty), expansion. The default capacity expansion mode is to double the original capacity and copy the original data.
4.1.3 Expansion of HashMap
As the number of elements in a HashMap increases, the probability of hash collisions increases because the array length is fixed. Therefore, in order to improve the efficiency of the query, the HashMap array must be expanded. After the HashMap array is expanded, the location of the data in the original array must be recalculated and put into the new array. This is resize.
4.1.4 Expansion Time of HashMap
Array expansion occurs when the number of elements in a HashMap exceeds the array size (length, not the number in the array) * loadFactor. The default value of loadFactor (DEFAULT_LOAD_ FACTOR) is 0.75, which is a compromise value. In other words, the DEFAULT INITIAL CAPACITY of the array is 16, so when the number of elements in the HashMap exceeds 16 * 0.75=12 (threshold is the code value, also called the threshold), We can double the size of the array to 2 * 16=32, and then recalculate each element’s position in the array. This is a very performance expensive operation, so if we already know the number of elements in the HashMap, the preset number of elements can effectively improve the performance of the HashMap.
4.2 Implementation principle of HashMap in JDK 8.0
4.2.1 Storage structure of HashMap:
The internal storage structure of a HashMap is actually an array + a linked list + a red-black tree.
4.2.2 Process of adding elements to HashMap
InitialCapacity and loadFactor are initialized when a HashMap is instantiated. When the first pair of mappings is put, an array of nodes with initialCapacity is created. This length is called Capacity in the hash table. The location where elements can be stored in this array is called “buckets”. Each bucket has its own index. The system can quickly search for elements in the bucket according to the index.
Each bucket stores one element, a Node object, but each Noe object can have a reference variable next that points to the next element, so it is possible to create a Node chain within a bucket. Each Tree node object can have two leaves, left and right. Therefore, it is possible to generate a TreeNode Tree in a bucket. The new element is the last of the linked list, or the leaf of the tree.
4.2.3 Capacity Expansion Mechanism of HashMap
When the number of objects in a HashMapl chain does not reach 8, it is the same as before JDK 7.0. When the number of objects in a HashMapl reaches 8, if capacity does not reach 64, the HashMap will be expanded first. If capacity reaches 64, the chain will become a Tree, and the Node type will be changed from Node to Tree Node type. Of course, if the number of nodes in the tree is judged to be less than 6 in the next resize method after the mapping relationship is removed, the tree will also be converted to a linked list.
4.2.4 Changes in JDK 8.0 and 7.0
New HashMap(): An array of length 16 is not created underneath
The underlying array in JDK 8.0 is Node[] instead of Entry[].
The first time the put() method is called, the bottom layer creates an array of length 16
JDK 7.0 contains only arrays and linked lists. JDK 8.0: array + linked list + red-black tree.
When forming a linked list, it’s up and down (jdk7: new elements point to old elements. If the number of linked elements in an index of an array is greater than 8 and the length of the current array is greater than 64, all data in the index is stored in a red-black tree instead.
4.3 Description of the underlying typical attributes of HashMap:
DEFAULT_INITIAL_CAPACITY : Default capacity of HashMap, 16 DEFAULT_LOAD_FACTOR: default loading factor of HashMap: 0.75 Threshold: threshold for capacity expansion, = Capacity x padding factor: 16 x 0.75 => 12 TREEIFY_THRESHOLD: If the Bucket list length is larger than the default value, it is converted to a red-black tree :JDK 8.0 introduced MIN_TREEIFY_CAPACITY: the minimum hash table capacity for nodes in the Bucket to be treed is 64
4.4 Underlying implementation principles of LinkedHashMap
The underlying LinkedHashMap uses the same structure as HashMap because LinkedHashMap inherits from HashMap. The difference is that the LinkedHashMap provides Entry inside, replacing nodes in the HashMap. Like the Linkedhash Set, the LinkedHashMap maintains the iteration order of the Map: the iteration order is the same as the insertion order of key-value pairs.
static class Node<K,V> implements Map.Entry<K,V>{
final int hash;
final K key;
V value;
Node<K,V> next;
}
Copy the codeLinkedHashM internal class Entry source:
static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; // Can record the order of the added elements Entry(inthash, K key, V value, Node<K,V> next) {
super(hash, key, value, next); }}Copy the code5. Use of TreeMap
To add a key-value to a TreeMap, specify that objects created by the same class must be sorted by key: natural sort, custom sort
Code examples:
@test public voidtest() {
TreeMap map = new TreeMap();
User u1 = new User("Tom", 23);
User u2 = new User("Jarry", 18);
User u3 = new User("Bruce"56); User u4 = new User("Davie", 23);
map.put(u1, 98);
map.put(u2, 16);
map.put(u3, 92);
map.put(u4, 100);
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "="+ entry.getValue()); } // Order by age @test public voidtest2() {
TreeMap map = new TreeMap(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("Input data type error"); }}); User u1 = new User("Tom", 23);
User u2 = new User("Jarry", 18);
User u3 = new User("Bruce"56); User u4 = new User("Davie", 23);
map.put(u1, 98);
map.put(u2, 16);
map.put(u3, 92);
map.put(u4, 100);
Set entrySet = map.entrySet();
Iterator iterator = entrySet.iterator();
while (iterator.hasNext()) {
Object obj = iterator.next();
Map.Entry entry = (Map.Entry) obj;
System.out.println(entry.getKey() + "="+ entry.getValue()); }}Copy the code6. Read the configuration file using Properties
Code examples:
//Properties: used to handle configuration files. Public static void main(String[] args) {FileInputStream fis = null; try { Properties pros = new Properties(); fis = new FileInputStream("jdbc.properties"); pros.load(fis); 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(); }}}}Copy the codeThe last
You can leave a comment below, you can also ask me a private letter, I generally see after will reply. Also welcome everyone to pay attention to my official account: the future is bright, immediately jin Jiu Yin ten job-hunting interview season, sorted out more than 1000 nearly more than 500 pages of PDF documents of Java interview questions, the article will be updated in it, sorted out the information will be placed in it.