preface

HashMap 在 Java 和 AndroidVery common in development
Today, I’m going to bringHashMapAll source code analysis, I hope you will like.

This article is based on versionJDK 1.7, i.e.,Java 7

About the versionJDK 1.8, i.e.,Java 8Please see the article for detailsJava source code analysis: A major update to HashMap 1.8

1. Introduction

The class definition

public class HashMap<K,V>
         extends AbstractMap<K,V> 
         implements Map<K,V>, Cloneable, Serializable
Copy the code

This paper mainly introduces

HashMapThe implementation of theJDK 1.7 和 JDK 1.8The difference is bigger
Today, I’m going to focus onJDK 1.7 中 HashMapSource code parsing

Java source Code Analysis: A major update to HashMap 1.8

2. Data structure

2.1 Description

The data structure used by HashMap = array (primary) + singly linked list (secondary), as described below

This data structure method is also called zipper method

2.2 sketch

2.3 Storage Process

Note: in order to let you have a perceptual understanding, just a simple draw storage process, more detailed & specific storage process will be given in the following source code analysis

2.4 Array elements & linked list node implementation class

HashMapThe array element & linked list node inEntryClass, as shown in the figure below

namelyHashMapEssence = 1 storeEntryClass object array + multiple singly linked lists

EntryObject essence = 1 mapping (key-value pair) with properties including: key (key), value (value) & next node (next) = A single linked list pointer = is also aEntryObject for resolutionhashconflict

The source code analysis of this class is as follows

Please refer to the notes for specific analysis

The /** * Entry class implements the map.Entry interface, which implements getKey(), getValue(), equals(Object O), and the map.Entry interfacehashStatic class Entry<K,V> implements Map.Entry<K,V> {final K key; / / V value; / / value Entry < K, V > next; // Points to the next node, also an Entry object, to form the solutionhashConflicting single linked list inthash;  // hashValue /** * constructor creates an Entry * argument: hash h, key k, value v, next node n */ Entry(int h, k k, v v, Entry< k, v > n) {value = v; next = n; key = k;hash= h; } // return the key corresponding to this item public final KgetKey() {  
        returnkey; } // Return the corresponding value public final VgetValue() {  
        return value;  
    }  
  
    public final V setValue(V newValue) {  
        V oldValue = value;  
        value = newValue;  
        returnoldValue; } /** * equals () * checks whether two entries are equaltrue  
     */ 
      public final boolean equals(Object o) {  
        if(! (o instanceof Map.Entry))return false;  
        Map.Entry e = (Map.Entry)o;  
        Object k1 = getKey();  
        Object k2 = e.getKey();  
        if(k1 == k2 || (k1 ! = null && k1.equals(k2))) { Object v1 = getValue(); Object v2 = e.getValue();if(v1 == v2 || (v1 ! = null && v1.equals(v2)))return true;  
        }  
        return false; } / * * *hashCode () */ public final inthashCode() { 
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());  
    }  
  
    public final String toString() {  
        return getKey() + "="+ getValue(); } /** * When adding an element to a HashMap, that is, when calling put(k,v), * overwrites v at a position k already in the HashMap, Void recordAccess(HashMap<K,V> m) {} /** * When an Entry is removed from the HashMap, / void recordRemoval(HashMap<K,V> m) {}}Copy the code

3. Specific use

3.1 Mainly using APIS (methods and functions)

V get(Object key); V put(K key, V value); Void putAll(Map<? extends K, ? extends V> m); V remove(Object key); // Copy key pairs from the specified Map to the Map. // Delete the Boolean containsKey(Object key); // Check whether there is a key-value pair for the key; Is it returnstrueboolean containsValue(Object value); // Check whether there is a key-value pair for this value; Is it returnstrueSet<K> keySet(); Set Collection<V> values(); // Single value sequence, generate a Collection void clear() for all values; // Delete all key pairs int size() from the hash table; // Return the number of key-value pairs in the hash table = key-value pairs in the array + key-value pairs in the linked list Boolean isEmpty(); // Check whether HashMap is empty; Null if size == 0Copy the code

3.2 Usage Process

In specific use, the main process is:

Statement 1HashMapThe object of
toHashMapAdd data (in key-value pairs)
To obtainHashMapSome data of
To obtainHashMapAll data: traversalHashMap

The sample code

import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set; public class HashMapTest { public static void main(String[] args) { /** * 1. */ Map<String, Integer> Map = new HashMap<String, Integer>(); /** * 2. Add data to HashMap (key-value pairs) */ map.put("Android", 1);
        map.put("Java", 2);
        map.put("iOS", 3);
        map.put("Data mining", 4);
        map.put("Product Manager", 5); */ system.out.println (*/ system.out.println)"Key = product manager value:" + map.get("Product Manager")); * Step 1: Get a Set of key-value pairs (Entry) or keys or values * Step 2: Get a Set of key-value pairs (Entry) or keys or values (Setfor// / Select a Set of key-value pairs and then iterate system.out.println ()."1"); Set< map. Entry<String, Integer>> entrySet = map.entryset (); // 2. Run through Set to get key-value // 2.1 passforcyclefor(Map.Entry<String, Integer> entry : entrySet){
            System.out.print(entry.getKey());
            System.out.println(entry.getValue());
        }
        System.out.println("-- -- -- -- -- -- -- -- -- --"); Iterator Iterator Iterator 1 = entryset.iterator (); Iterator entryset.iterator ();while(iter1.hasNext()) {// Obtain the key and value map.Entry entry = (map.entry) iter1.next(); System.out.print((String) entry.getKey()); System.out.println((Integer) entry.getValue()); } // Method 2: get a Set of keys and repeat system.out.println ("Method 2"); Set<String> keySet = map.keyset (); // 2. Select key from Set and value from Setforcyclefor(String key : keySet){
            System.out.print(key);
            System.out.println(map.get(key));
        }

        System.out.println("-- -- -- -- -- -- -- -- -- --"); Iterator iter2 = keyset.iterator (); String key = null;while(iter2.hasNext()) { key = (String)iter2.next(); System.out.print(key); System.out.println(map.get(key)); } // Get a Set of values and repeat system.out.println ("Method 3"); Collection valueSet = map.values(); Iterator Iterator iter3 = valueset.iterator (); Iterator iter3 = valueset.iterator (); // 2.2 Obtain value directly through traversalwhile(iter3.hasNext()) { System.out.println(iter3.next()); }}} // Note: For traversal, it is recommended to use Entry for key-value pairs: High efficiency // Cause: // 1. For iterating over keySet, valueSet, essentially = iterated twice: 1 = iterated to iterator, 2 = value operation to fetch key from HashMap (by key value)hashCode and equals index) // 2. Iterating through entrySet = iterating through entrySet = iterating through entrySet = iterating through entrySet = iterating through entrySetCopy the code

The results

Method 1 Java2 iOS3 Data mining 4 Android1 Product manager 5 ---------- Java2 iOS3 data mining 4 Android1 Product manager 5 Method 2 Java2 iOS3 data mining 4 Android1 Product manager 5 ---------- Java2 iOS3 Data mining 4 Android1 Product Manager 5 Method 3 2 3 4 1 5Copy the code

Below, we use the process in accordance with the above, one step by step source code analysis

4. Basics: Important parameters (variables) in HashMap

Before getting into the real source code analysis, explainHashMapImportant parameters (variables) in
HashMapMajor parameters = capacity, load factor, and capacity expansion threshold
The details are as follows

// 1. Capacity: the length of the array in HashMap // a. Capacity range: must be a power of 2 & < maximum capacity (2 ^ 30) // b. Initial capacity = capacity when the hash table is created // Default capacity =16 =1 <<4 =1 in 00001 moved 4 bits to the left = 10000 = 2^4 in decimal =16 static final int DEFAULT_INITIAL_CAPACITY =1 < < 4; Static final int MAXIMUM_CAPACITY = 1 << 30; // 2. Load factor: a measure of how full a HashMap can be before its capacity automatically increases The larger the loading factor, the more elements are filled = higher space utilization, but more chances of conflicts, and lower look-up efficiency (because the linked list is longer) // b. Smaller loading factor, fewer filled elements = smaller space utilization, less chance of conflicts, higher search efficiency (short list) // Actual loading factor finalfloatloadFactor; // Default loading factor = 0.75 static finalfloatDEFAULT_LOAD_FACTOR = 0.75 f; // 3. Capacity expansion threshold: When the size of the hash table is greater than or equal to the capacity expansion threshold, the HashMap will be expanded. // a. Capacity expansion = resize the hash table (i.e., rebuild the internal data structure) so that the hash table will have approximately twice the number of buckets // b. Capacity expansion threshold = Capacity x load factor int threshold; // Select * from the list where you want to store data. Each element in the Entry array is essentially a one-way linked list transient Entry<K,V>[] TABLE = (Entry<K,V>[]) EMPTY_TABLE; // The number of key-value pairs stored in HashMap transient int size;Copy the code

Parameter diagram

Load factors are detailed here

5. Source code analysis

The source code analysis is mainly based on the use of steps to carry out a detailed analysis of the relevant functions
The main analysis contents are as follows:

Below, I’ll break down the main approaches to the content of each step

Step 1: Declare a HashMap object

/** * function uses prototype */ Map<String,Integer> Map = new HashMap<String,Integer>(); /** ** */ public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable{// omit the arguments described in the previous section /** * constructor 1: default constructor (no arguments) * load factor & capacity = default = 0.75, 16 */ publicHashMap() {// is actually calling constructor 3: the constructor that specifies "capacity size" and "load factor" // passing in the specified capacity & load factor = default this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } /** * constructor 2: Public HashMap(int initialCapacity) {// Actually calls the constructor that specifies capacity size and load factor // Just pass in the loading factor parameter = default loading factor this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, int initialCapacity, int initialCapacity)floatLoadFactor) {// The maximum capacity of a HashMap can only be MAXIMUM_CAPACITY, even if the > maximum capacity is passed inif(initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; // set loadFactor this.loadFactor = loadFactor; // set the capacity expansion threshold = initialCapacity // note: this is not a real threshold, but to expand the table. This threshold will be recalculated later. init(); // An empty method for future subobject extensions} /** * constructor 4: the constructor containing "submap" * that is, the constructed HashMap contains the mapping of the passed Map * loading factor & capacity = default */ public HashMap(Map<? extends K, ? Extends V> m) {this(math.max ((int) (m.size()/DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // This method is used to initialize arrays & thresholds, as described below: inflateTable(threshold); PutAllForCreate (m); }}Copy the code

Note:
1. This is only used to receive the initial capacity size (capacity), loading factor (Load factor), but the hash table is still not actually initialized, that is, the storage array is initializedtable
2. The conclusion here is that the hash table is actually initialized the first time the key-value pair is added, the first time put () is called. More on that below

This concludes the discussion of HashMap constructors.

Step 2: Add data to the HashMap (key-value pairs)

The process for adding data is as follows

Note: in order to let you have a perceptual understanding, just a simple draw storage process, more detailed & specific storage process will be given in the following source code analysis

Source code analysis

/** * function uses prototype */ map.put("Android", 1);
        map.put("Java", 2);
        map.put("iOS", 3);
        map.put("Data mining", 4);
        map.put("Product Manager", 5); */ public V put(K key, V value) // 1. If the hash table is not initialized (that is, the table is empty) // initialize the array table using the threshold set at the time of the constructor (that is, the initial capacity)if(table == EMPTY_TABLE) { inflateTable(threshold); } // 2. Check whether key is null (analysis 2) // 2.1 If key == null, insert the key into the first position in table [0].hashValue = 0, so store in table[0]) // There is only one value in this position. New values overwrite old valuesif (key == null)
            returnputForNullKey(value); (Analysis 3) // 2.2 If key is not null, calculate the position (subscript, index) in the array table // a. Calculate by keyhashValue of the inthash = hash(key); / / b. according tohashInt I = indexFor(int I = indexFor(hash, table.length); // 3. Check whether the value corresponding to the key already exists (by traversing the list with the array element as the head node)for(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k; (Analysis 4) // 3.1 If the key already exists (key-value already exists), replace the old value with the new valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                returnoldValue; // and return the old value}} modCount++; (Analysis 5) // 3.2 If the key does not exist, add key-value to the table.hash, key, value, i);
        return null;
    }
Copy the code

A flow chart based on source code analysis

Below, I’ll elaborate on the five points of analysis of the above process

Analysis 1: Initialize the hash table

That is, initialize array (table), expand threshold (threshold)

/** * functions use prototypes */if(table == EMPTY_TABLE) { inflateTable(threshold); } /** * source code analysis: inflateTable(threshold); */ private void inflateTable(int toSize) { // 1. Will be introduced to the capacity of the size into: > to size the smallest power of 2 / / that is, if the incoming is size is 19, so after transformation, the initialization size 32 (i.e., 5 times the power of 2) int capacity = roundUpToPowerOf2 (toSize); ->> analyze 1 // 2. Recalculate threshold = capacity * loadFactor threshold = (int) math. min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); Table = new Entry[capacity]; table = new Entry[capacity]; // Initialize table initHashSeedAsNeeded(capacity) with this capacity; } /** * roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 roundUpToPowerOf2 */ private static int roundUpToPowerOf2(int number) {// If the capacity exceeds the maximum, set the initial capacity to the maximum. Otherwise, set to: > The smallest power of 2 of the passed capacity sizereturn number >= MAXIMUM_CAPACITY  ? 
            MAXIMUM_CAPACITY  : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;  
Copy the code

Again: the actual initialization of the hash table (initializing the storage array table) is the first time the key-value pair is added, the first time put () is called

If key ==null, store the key-value as the first position in table [0]

/** * functions use prototypes */if (key == null)
           returnputForNullKey(value); PutForNullKey (value) */ private V putForNullKey(V value) {putForNullKey(value) */ private V putForNullKey(V value) {putForNullKey(value); If yes, replace the old value with the new value. Return the old valuefor(Entry<K,V> e = table[0]; e ! = null; e = e.next) {if (e.key == null) {   
            V oldValue = e.value;  
            e.value = value;  
            e.recordAccess(this);  
            returnoldValue; } } modCount++; AddEntry (0, null, value, 0); addEntry(0, null, value, 0); // addEntry () =hashValue = 0 // bhashValue = 0, so the HashMap key can be null // c. Compare HashTable, because HashTable has direct access to keyshashCode () will throw an exception if the key is null. // d. You just need to know that you are adding key-value to the HashMap. The source code analysis of addEntry () will be explained below.return null;  

}     
Copy the code

Here you can see:

HashMapThe key ofkeyfornull(different fromHashTablethekeyDo not fornull)
HashMapThe key ofkeyfornullAnd can only be 1, but the valuevalueCan be null and multiple

Analysis 3: Calculate the location of the array table (array subscript or index)

/** * functions use prototypes * mainly divided into 2 steps: calculationhashValue, according to thehash*/ // a. Calculate the array location based on the key valuehashValue ->> Analyze 1 inthash = hash(key); / / b. according tohashInt I = indexFor(int I = indexFor(hash, table.length); /** **hash(key) * This function is implemented differently in JDK 1.7 and 1.8, but the principle is the same = the perturbation function = causes the hash code generated based on key (hashValue) is more evenly distributed, more random, avoid occurrencehashValue conflict (that is, different keys but the same one is generatedhashJDK 1.7 does 9 perturbs = 4 bits + 5 xor * JDK 1.8 simplifies the perturb function = only 2 bits = 1 bit + 1 Xor *hashValue) operation = usehashCode() + 4 bits + 5 xor (9 perturbations) static final inthash(int h) {
        h ^= k.hashCode(); 
        h ^= (h >>> 20) ^ (h >>> 12);
        returnh ^ (h >>> 7) ^ (h >>> 4); } // JDK 1.8 implementation: convert key to hash code (hashValue) operation = usehashCode() + 1 bit + 1 xor (2 perturbations) // 1. takehashH = key.hashCode() // 2. H ^ (h >>> 16) static final inthash(Object key) {
           int h;
            return(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // a. When key = null,hashValue = 0, so the key of a HashMap can be nullhashCode () will throw an exception if the key is null. If key ≠ NULL, the value of the key is calculated firsthash** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **hashStatic int indexFor(int h, int length) {/ static int indexFor(int h, int length) {returnh & (length-1); // The result of the hash code perturbation and operation (&) (array length -1), finally get the location of the array table (array subscript, index)}Copy the code

To summarize the process of calculating the location of an array table (array subscript, index)

After knowing how to calculate the position in the array table, I will explain why to calculate the position in the array table, namely to answer the following three questions:

Why not just go through itHashCode ()Handles the hash code as a storage arraytableThe subscript position of?
Why use hash and operation (&) (array length -1) to compute array subscripts?
Why do we need to do a second hash before we can evaluate the array subscript: perturbation?

Before we answer these three questions, please keep one key idea in mind:

The fundamental purpose of all processing is to improve the randomness and uniformity of distribution of the index positions of the array storing key-values and avoid hash value conflicts as much as possible. That is, the array index position should be as different as possible for different keys

Question 1: why not just use the hashCode processed by hashCode () as the subscript location for storing the array table?

Conclusion: It is easy to mismatch the hash code and the array size range, that is, the calculated hash code may not be in the array size range, resulting in the failure to match the storage location
Reason to describe

To solve the problem of “hash code does not match array size range”,HashMapSolutions are given:Hash and operation (&) (array length -1); Please continue with question 2

Question 2: Why use hash code and operation (&) (array length -1) to compute array subscripts?

Conclusion: According to the capacity of HashMap (array length), a certain number of low bits of hash code are selected as the subscript positions of the stored array, so as to solve the problem of “mismatch between hash code and array size range”
Solution description

Question 3: Why do we need to do a second hash before calculating the array subscript: perturb?

Conclusion: Increasing the randomness of the Hash code low position makes the distribution more uniform, thus improving the randomness and uniformity of the corresponding array storage subscript position, and ultimately reducing Hash conflict
A detailed description

That concludes how to calculate the key-value stored in the HashMap array and why.

Analysis 4: If the corresponding key already exists, use the new value to replace the old value

Note: When a Hash conflict occurs, the Hash table does not immediately insert new data into the list in order to ensure the uniqueness of the key. Instead, the Hash table looks up whether the key already exists and replaces it if it already exists

/** * function uses prototype */ / 2. Check whether the corresponding value of the key already exists (by traversing the list with the array element as the head node).for(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k; // 2.1 If the key already exists (key-value already exists), replace the old value with the new valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                returnoldValue; // and return the old value}} modCount++; // 2.2 If the key does not exist, add key-value to the table.hash, key, value, i);
        return null;
Copy the code

There is no complex source code analysis here, but there are two main points of analysis here: replacement flow &keyWhether or not there is (i.ekeyComparison of values)

Analysis 1: The replacement process

The details are as follows:

Analysis of 2:`key`The comparison of the value

Equals () or “==” is used for comparison. Here’s how &is compared to “==”

Analysis 5: If the corresponding key does not exist, add the key-value to the corresponding position of the array table

Function source code analysis is as follows

/** * function uses the prototype */ / 2. Check whether the corresponding value of the key already existsfor(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k; // 2.1 If the value corresponding to the key already exists, replace the old value with the new valueif (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this); 
                returnoldValue; } } modCount++; // 2.2 If the value corresponding to the key does not exist, add key-value to the table.hash, key, value, i); /** ** addEntry(hash, key, value, I) * Adds a key/value pair to a HashMap */ void addEntry(int)hash, K key, V value, int bucketIndex) { Check whether the capacity is sufficient. // 1.1 If not, expand the capacity by two times, recalculate the Hash value, and recalculate the storage array indexif((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length); A. Expand capacity by 2 times --> Analysis 1hash= (null ! = key) ?hash(key) : 0; // b. Recalculate the KeyhashValue bucketIndex = indexFor (hash, table.length); // c. Recalculate the Keyhash} // 1.2 Create a new Entry and add it to the array --> analyze 2 createEntry(hash, key, value, bucketIndex); } /** * Analysis 1: resize(2 * table.length) * Effect: When the capacity is insufficient (capacity > threshold), expand (double) */ void resize(int newCapacity) {// 1. Save old table Entry[] oldTable = table; Int oldCapacity = oldtable. length; // 3. If the old capacity is already the default maximum capacity, set the threshold to the maximum value of an integer and exitif (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return; } // 4. Create an array based on the new capacity (twice the capacity), that is, new table Entry[] newTable = new Entry[newCapacity]; Transfer (newTable); transfer(newTable); Table = newTable; // 7. Reset the threshold = (int)(newCapacity * loadFactor); } /** * analysis 1.1: Transfer (newTable); * Move the old array (key/value pair) to the new table, thus complete the expansion * process: */ void transfer(Entry[] newTable) {// 1.src references the old array Entry[] SRC = table; Int newCapacity = newtable. length; // 2. // 3. Transfer the data (key-value pairs) from the old array to the new array by iterating through the old arrayfor(int j = 0; j < src.length; J ++) {// 3.1 Get each Entry of the old array <K,V> e = SRC [j];if(e ! = null) {// 3.2 Free object references from old arrays (forSRC [j] = null;do// Note: When transferring a linked list, it is a single linked list, so save the next node. Otherwise, the linked list will be disconnected after transfer. Int I = indexFor(e.hash, newCapacity); // 3.5 Insert elements on array: use the head insertion method of single linked list = store data on the head of linked list = Place the original data in the array position in the last 1 pointer, and place the data to be placed in the array position // That is, after expansion, there may be reverse order: Insert e.next = newTable[I]; newTable[i] = e; // 3.6 Access the next Entry chain, and so on until all the nodes in the list have been traversed e = next; }while(e ! = null); }}} /** * parse 2: createEntry()hash, key, value, bucketIndex); Void createEntry(int) void createEntry(int) */ void createEntry(inthash, K key, V value, int bucketIndex) { // 1. Save the original Entry in the table. Entry<K,V> e = table[bucketIndex]; // 2. Create an Entry at this position in the table: Insert the key-value pairs of the original header position into the next node (linked list), and insert the key-value pairs into the header position (array) -> to form a linked list. Table [bucketIndex] = New Entry<>(hash, key, value, e); // 3. Add size++ to the hash table's key-value pair count; }Copy the code

There are two things to note here: the way key-value pairs are added & the capacity expansion mechanism

1. Key-value pair addition method: single linked list header insertion method

That is, the original data of this position (on the array) is placed in the next node of this position (linked list), and the data to be inserted in this position (on the array) is placed -> to form the linked list
As shown below

2. Capacity expansion mechanism

The specific process is as follows:

The diagram for transferring data during capacity expansion is as follows

In the process of expansion resize (), when transferring data from the old array to the new array, the transfer operation = traverses the linked list in the positive order of the old list and inserts them in the head of the new list in turn, that is, after data transfer and expansion, the linked list is prone to reverse order

If the storage location remains unchanged after recalculation, go to 1->2->3 before capacity expansion and 3->2->1 after capacity expansion

At this time, if (multithreading) concurrently executes put (), once expansion occurs, circular linked lists are prone to appear, thus forming an Infinite Loop when data is acquired and the linked list is traversed. In other words, the state of deadlock = unsafe thread

The last section below explains this in more detail

conclusion

toHashMapThe full process of adding data (in key-value pairs)

Schematic diagram

This concludes the tutorial on adding data to a HashMap (putting key-value pairs in pairs)

Step 3: Get the data from the HashMap

If you understand the abovePut ()The principle of delta function, soThe get ()The function is easy to understand because the process is almost the same
The get ()The flow of the function is as follows:

Specific source code analysis is as follows

/** * get(key) from HashMap */ map.get(key); Public V get(Object key) {// 1. When key == null, the linked list with the first element (table[0]) as the head node is searched for the key corresponding to key == NULLif (key == null)  
        returngetForNullKey(); 2 Entry<K,V> Entry = getEntry(key);returnnull == entry ? null : entry.getValue(); } /** * private V getForNullKey();} /* private V getForNullKey()getForNullKey() {  

    if (size == 0) {  
        returnnull; } // select * from table[0] where key==nullfor(Entry<K,V> e = table[0]; e ! = null; E = e.ext) {// select key==null from table[0]if (e.key == null)  
            return e.value; 
    }  
    returnnull; } /** * getEntry(key) {final Entry<K,V> getEntry(key) {if (size == 0) {  
        returnnull; } // 1. Pass according to the key valuehash() calculate the correspondinghashValue of the inthash= (key == null) ? Zero:hash(key); / / 2. According tohashValue calculates the corresponding array index // 3. Traverses all nodes in the linked list with the array element with the array index as the head node to find the value corresponding to the keyfor (Entry<K,V> e = table[indexFor(hash, table.length)]; e ! = null; e = e.next) { Object k; / / ifhashIf the value &key is equal, prove that Entry = the key pair we want // check whether the key is equal through equals ()if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))return e;  
    }  
    return null;  
}  
Copy the code

That’s it for getting data to a HashMap

Step 4: Additional operations on the HashMap

That is, source code analysis of the rest using apis (functions, methods)

HashMapExcept for the corePut (),The get ()Function, and the following function methods are mainly used

void clear(); // Delete all key pairs int size() from the hash table; // Return the number of key-value pairs in the hash table = key-value pairs in the array + key-value pairs in the linked list Boolean isEmpty(); // Check whether HashMap is empty; Void putAll(Map<? extends K, ? extends V> m); V remove(Object key); // Copy key pairs from the specified Map to the Map. // Delete the Boolean containsKey(Object key); // Check whether there is a key-value pair for the key; Is it returnstrueboolean containsValue(Object value); // Check whether there is a key-value pair for this value; Is it returnstrue
 
Copy the code

Here is a brief look at the source code analysis of the above functions

/** * the isEmpty() function checks whether the HashMap isEmpty. */ public Boolean if size == 0isEmpty() {  
    returnsize == 0; } /** * function: size() * Returns the number of key-value pairs in the hash table = array key-value pairs + list key-value pairs */ public intsize() {  
    returnsize; } /** * function: clear() * Function: clear hash table, that is, delete all key/value pairs * principle: set all entries stored in array table to null, size to 0 */ public voidclear() { modCount++; Arrays.fill(table, null); size = 0; } /** * function: putAll(Map<? extends K, ? Role extends V > m) * : specifies a Map of key/value pair is copied to the principle of this Map * : similar to Put function * / public void putAll (Map <? extends K, ? Extends V> m) {// 1. Int numKeysToBeAdded = m.size();if (numKeysToBeAdded == 0)  
        return; // 2. If the table is not initialized, initialize the table with the number of copies countedif(table == EMPTY_TABLE) { inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold)); } // 3. If the number of replications to be performed is greater than the threshold, expand the capacity firstif (numKeysToBeAdded > threshold) {  
        int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);  
        if (targetCapacity > MAXIMUM_CAPACITY)  
            targetCapacity = MAXIMUM_CAPACITY;  
        int newCapacity = table.length;  
        while (newCapacity < targetCapacity)  
            newCapacity <<= 1;  
        if(newCapacity > table.length) resize(newCapacity); } // 4. Start the copy (actually keep calling the Put function insert)for(Map.Entry<? extends K, ? extends V> e : m.entrySet()) put(e.getKey(), e.getValue()); } public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value);  
}  
  
final Entry<K,V> removeEntryForKey(Object key) {  
    if (size == 0) {  
        returnnull; } // 1hashValue of the inthash= (key == null) ? Zero:hash(key); Int I = indexFor(int I = indexFor(hash, table.length);  
    Entry<K,V> prev = table[i];  
    Entry<K,V> e = prev;  
  
    while(e ! = null) { Entry<K,V> next = e.next; Object k;if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k)))) { modCount++; size--; // Insert next reference into table[I] // insert next reference into table[I]if(prev == e) table[i] = next; // Otherwise, in the linked list with table[I] as the head, next in the first Entry of the current Entry will be set to next of the current Entry (i.e. deleting the current Entry = directly skipping the current Entry).else  
                prev.next = next;   
            e.recordRemoval(this);  
            return e;  
        }  
        prev = e;  
        e = next;  
    }  
  
    returne; } /** * function: containsKey(Object key) * Is it returnstrue*/ public Boolean containsKey(Object key) {returngetEntry(key) ! = null; } /** * function: containsValue(Object value) * Is it returnstrue*/ public Boolean containsValue(Object value) {// If value is empty, call containsNullValue().if (value == null)
        returncontainsNullValue(); [] TAB = table; // If value is not empty, count each Entry in the linked list through equals () to determine if there is an Entry[] TAB = table;for (int i = 0; i < tab.length ; i++)  
        for(Entry e = tab[i] ; e ! = null ; e = e.next)if (value.equals(e.value)) 
                return true; / / returntrue  
    return false; } // Method called when value is null private BooleancontainsNullValue() {  
    Entry[] tab = table;  
    for (int i = 0; i < tab.length ; i++)  
        for(Entry e = tab[i] ; e ! = null ; e = e.next)if (e.value == null)
                return true;  
    return false;  
} 

Copy the code

At this point, the basic principle of HashMap & mainly use API (functions, methods) is explained.

6. Summary of source code

Below, summarize the entire source content with three diagrams:

Summary = data structure, main parameters, process of adding & querying data, capacity expansion mechanism

Data structure & main parameters
Add & query data flow
Expansion mechanism

And 7.`JDK 1.8`The difference between

The implementation of HashMap differs greatly between JDK 1.7 and JDK 1.8, as follows

JDK 1.8 is optimized to reduce Hash collisions and improve the efficiency of storing and fetching Hash tables. Java source Code Analysis: A major update to HashMap 1.8

7.1 Data Structure

7.2 Data Storage (Similar to data acquisition)

7.3 Capacity Expansion Mechanism

8. Bonus: Additional questions about HashMap

There are a few minor issues that need to be added here

Specific as follows

8.1 How can Hash Table Conflicts Be Resolved

8.2 Why does HashMap have the following characteristics: key-values are allowed to be null, threads are not safe, order is not guaranteed, and storage location changes with time

The specific answers are as follows

The following will mainly explain one of the important reasons why HashMap thread is unsafe: In multi-threading, it is easy to occur resize () Infinite Loop nature = The concurrent execution of PUT () operation triggers expansion behavior, resulting in circular linked list, which forms Infinite Loop when data acquisition traverses the linked list
Resize ()

The source code analysis of resize () has been analyzed in detail above, and the focus is only analyzed here: transfer ()

/** * resize(2 * table.length) */ void resize(int newCapacity) {// 1. Save old table Entry[] oldTable = table; Int oldCapacity = oldtable. length; // 3. If the old capacity is already the default maximum capacity, set the threshold to the maximum value of an integer and exitif (oldCapacity == MAXIMUM_CAPACITY) {  
        threshold = Integer.MAX_VALUE;  
        return; } // 4. Create an array based on the new capacity (twice the capacity), that is, new table Entry[] newTable = new Entry[newCapacity]; Transfer (newTable) transfer(newTable) transfer(newTable); Table = newTable; // 7. Reset the threshold = (int)(newCapacity * loadFactor); } /** * analysis 1.1: Transfer (newTable); * Move the old array (key/value pair) to the new table, thus complete the expansion * process: */ void transfer(Entry[] newTable) {// 1.src references the old array Entry[] SRC = table; Int newCapacity = newtable. length; // 2. // 3. Transfer the data (key-value pairs) from the old array to the new array by iterating through the old arrayfor(int j = 0; j < src.length; J ++) {// 3.1 Get each Entry of the old array <K,V> e = SRC [j];if(e ! = null) {// 3.2 Free object references from old arrays (forSRC [j] = null;do// Note: When transferring a linked list, it is a single linked list, so save the next node. Otherwise, the linked list will be disconnected after transfer. Int I = indexFor(e.hash, newCapacity); // 3.4 Insert elements on array: use head insertion method of single linked list = store data on head of linked list = Place the original data in array position in the last 1 pointer, and place the data to be placed in array position // That is, after expansion, there may be reverse order: Insert e.next = newTable[I]; newTable[i] = e; // Access the next Entry chain, and so on until all the nodes in the list are traversed e = next; }while(e ! = null); // This loop continues until all the elements of the array are iterated}}}Copy the code

As can be seen from the above: In the process of expansion resize (), when transferring the data from the old array to the new array, the operation of data transfer = traverses the linked list in the positive order of the old list and inserts the data in the head of the new list in sequence, that is, after data transfer and expansion, the linked list is prone to reverse order