Shulou(Shulou.com)06/03 Report--

This article mainly shows you "what are the implementation classes of the Map interface in the Java collection", the content is simple and clear, and I hope it can help you solve your doubts. Let the editor lead you to study and learn about "what are the implementation classes of the Map interface in the Java collection".

HashMap class 1, HashMap class overview

HashMap is the most frequently used implementation class of the Map interface, allowing the use of null keys and null values, and, like HashSet, does not guarantee the order of mapping.

The set of all key is Set: unordered and unrepeatable. So, the class in which key is located needs to override the

Equals () and hashCode ().

The set of all value is Collection: unordered and repeatable. So, the class in which value is located

To override equals ().

A key-value forms an entry, and the set of all entry is Set: unordered and unrepeatable.

HashMap criteria for judging the equality of two key: two key returns true through the equals () method

The hashCode () value is also equal.

HashMap's criterion for determining that two value are equal: two value returns true through the equals () method.

2. The storage structure of HashMap (underlying implementation principle) HashMap map = new HashMap ()

(described in JDK1.7)

After instantiation, the underlying layer creates an one-dimensional array Entry [] table of length 16.

Map.put (key1,value1)

First, the hashCode () of the class where key1 belongs is called to calculate the key1 hash value, which is calculated by some algorithm to get the location in the Entry [] array.

If the data at this location is empty, the key1-value1 is added successfully at this time. -case 1

If the data at this location is not empty (meaning that one or more data exists at this location (in the form of a linked list), continue to compare the hash values of key1 and one or more data that already exist:

If the hash value of the key1 is different from that of the existing data, the key1-value1 is added successfully. -case 2

If the hash value of key1 is the same as that of an existing data key2-value2, continue to compare:

Call the equals (key2) of the class where key1 belongs

If equals () returns false: key1-value1 is added successfully at this time. -case 3

If equals () returns true: replace value2 with value1.

Add: for cases 2 and 3, the key1-value1 and the original data are stored as linked lists.

In the process of continuous addition, the problem of capacity expansion will be involved. The default method of capacity expansion is to expand the capacity to twice the original capacity, and copy the original data.

JDK1.8 differs from JDK1.7 in its underlying implementation:

① new HashMap (), the underlying layer has not created an array of length 16

The underlying array of ② JDK1.8 is: Node [], not Entry []

When ③ first calls the put () method, the underlying layer creates an array Node of length 16 []

When ④ forms a linked list structure, the newly added key-value pairs are at the end of the linked list (seven up and eight down)

The underlying structure of ⑤ JDK1.7 is only "array + linked list", while the underlying structure of JDK1.8 is "array + linked list + red-black tree".

When the number of data in the form of a linked list of elements in an index position of an array is more than 8 and the length of the current array is more than 64, all data at that index position is stored in a red-black tree instead.

3. Important constants in HashMap source code

DEFAULT_INITIAL_CAPACITY: default capacity of HashMap, 16

MAXIMUM_CAPACITY: maximum supported capacity of HashMap, 2 ^ 30

Default load factor for DEFAULT_LOAD_FACTOR:HashMap, 0.75

The length of the linked list in TREEIFY_THRESHOLD:Bucket is greater than the default value of 8, which is converted to a red-black tree.

The Node stored in the red-black tree in UNTREEIFY_THRESHOLD:Bucket is less than the default value of 6, which is converted to a linked list.

MIN_TREEIFY_CAPACITY: the minimum hash table capacity when the Node in the bucket is treed. (when the number of Node in the bucket is so large that you need to change the red-black tree, if the capacity of hash table is less than MIN_TREEIFY_CAPACITY, you should perform resize expansion operation. The value of this MIN_TREEIFY_CAPACITY is at least 4 times that of TREEIFY_THRESHOLD and 64. )

Table: an array of storage elements, always to the nth power of 2

EntrySet: a set that stores specific elements

Number of key-value pairs stored in size:HashMap

The number of modCount:HashMap capacity expansion and structural changes.

Threshold: critical value of capacity expansion, = capacity * fill factor

LoadFactor: fill factor

LinkedHashMap class

LinkedHashMap is a subclass of HashMap

Based on the HashMap storage structure, a pair of bi-directional linked lists are used to record the order in which elements are added.

Like LinkedHashSet, LinkedHashMap can maintain the iterative order of Map: the iterative order is the same as the insertion order of Key-Value pairs.

TreeMap class 1, TreeMap class overview

When TreeMap stores Key-Value pairs, it needs to be sorted according to key. TreeMap ensures that all Key-Value are in an orderly state.

The underlying layer of TreeSet uses a red-black tree structure to store data.

Sort the Key of TreeMap:

① natural sorting: all Key of TreeMap must implement the Comparable interface, and all

Should be an object of the same class, otherwise ClasssCastException will be thrown.

② custom sorting: when you create a TreeMap, you pass in a Comparator object, which is responsible for the

All key in TreeMap are sorted, and Key of Map is not required to implement the Comparable interface at this time.

The criterion by which TreeMap determines that two key are equal: two key returns 0 through the compareTo () method or the compare () method.

2. Natural sorting import java.util.Iterator;import java.util.Map;import java.util.Set;import java.util.TreeMap;/** * @ Author: Yeman * @ Date: 2021-09-22-22:59 * @ Description: * / class user implements Comparable {String name; int age; public user (String name, int age) {this.name = name; this.age = age } @ Override public String toString () {return "user {" + "name='" + name +'\'+ ", age=" + age +'}';} @ Override public int compareTo (Object o) {if (o instanceof user) {user other = (user) o Integer nameResult = this.name.compareTo (other.name); if (nameResult = = 0) {return Integer.compare (this.age,other.age);} else return nameResult;} else throw new RuntimeException ("Type mismatch");}} public class TreeMapTest {public static void main (String [] args) {Map map = new TreeMap () Map.put (new user ("Tom", 22), 1); map.put (new user ("Jim", 18), 2); map.put (new user ("Marry", 20), 3); map.put (new user ("Lily", 16), 4); map.put (new user ("Tom", 18), 5); Set set = map.entrySet (); Iterator iterator = set.iterator () While (iterator.hasNext ()) {System.out.println (iterator.next ());}

3. Custom sorting import java.util.*;/** * @ Author: Yeman * @ Date: 2021-09-22-22:59 * @ Description: * / class user {String name; int age; public user (String name, int age) {this.name = name; this.age = age } @ Override public String toString () {return "user {" + "name='" + name +'\'+ ", age=" + age +'}' }} public class TreeMapTest {public static void main (String [] args) {Comparator comparator = new Comparator () {@ Override public int compare (Object o1, Object O2) {if (o1 instanceof user & & O2 instanceof user) {user user1 = (user) o1; user user2 = (user) O2 Integer nameResult = user1.name.compareTo (user2.name); if (nameResult = = 0) return Integer.compare (user1.age, user2.age); else return nameResult;} else throw new RuntimeException ("Type mismatch");}}; Map map = new TreeMap (comparator) Map.put (new user ("Tom", 22), 1); map.put (new user ("Jim", 18), 2); map.put (new user ("Marry", 20), 3); map.put (new user ("Lily", 16), 4); map.put (new user ("Tom", 18), 5); Set set = map.entrySet (); Iterator iterator = set.iterator () While (iterator.hasNext ()) {System.out.println (iterator.next ());}

Hashtable class

Hashtable is an ancient Map implementation class, and JDK1.0 provides it. Different from HashMap

Hashtable is thread-safe.

The implementation principle of Hashtable is the same as that of HashMap and its function is the same. The underlying layer uses hash table structure, query

The speed is fast, and it can be used with each other in many cases.

Unlike HashMap, Hashtable does not allow the use of null as key and value.

Like HashMap, Hashtable cannot guarantee the order of Key-Value pairs in it.

The criteria for Hashtable to judge that two key are equal and two value are equal is the same as HashMap.

Properties class

The Properties class is a subclass of Hashtable, and this object is used to deal with properties files. Because key and value in the properties file are string types, key and value in Properties are string types.

When accessing data, it is recommended to use setProperty (String key,String value) method and getProperty (String key) method

Properties pros = new Properties (); pros.load (new FileInputStream ("jdbc.properties")); String user = pros.getProperty ("user"); System.out.println (user). This is all of the article "what are the implementation classes of the Map interface in the Java collection?" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.