preface

  • HashMap 在 Java 和 AndroidVery common in development
  • Today, I’m going to bringHashMapAll source code analysis, I hope you will like.
  1. This article is based on versionJDK 1.7, i.e.,Java 7
  2. About the versionJDK 1.8, i.e.,Java 8Please see the article for detailsJava source code analysis: A major update to HashMap 1.8

directory


Schematic diagram

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


Schematic diagram

  • 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


Schematic diagram

2.2 sketch


Schematic diagram

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


Schematic diagram

2.4 Array elements & linked list node implementation class

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


Schematic diagram

  1. namelyHashMapEssence = 1 storeEntryClass object array + multiple singly linked lists
  2. 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

/** * static class Entry<K,V> static class Entry<K,V> implements Map.Entry<K,V> { final K key; / / V value; / / value Entry < K, V > next; // Points to the next node, which is also an Entry object, to form a single linked list int hash that resolves hash collisions; // hash value /** * constructor creates an Entry * argument: hash value h, key value 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; } public final K getKey() {return key; } public final V getValue() {return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } /** * equals() * Returns true */ 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 int hashCode() {return objects.hashCode (getKey()) ^ objects.hashCode ()); } 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; Returns true Boolean containsValue(Object value); // Check whether there is a key-value pair for this value; Set<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:
  1. Statement 1HashMapThe object of
  2. toHashMapAdd data (in key-value pairs)
  3. To obtainHashMapSome data of
  4. 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("key = product manager: "+ map.get(" product manager ")); * Step 1: Get a Set of key-value pairs (Entry or key or value) * Step 2: Get a Set of key-value pairs (Entry or key or value) There are 3 ways to iterate over the above Set (using either a for loop or an Iterator) : for key-value pairs (Entry or key or value) Get the Set of key-value again through system.out.println (" method 1"); Set< map. Entry<String, Integer>> entrySet = map.entryset (); 2.1 Loop for(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 the Set of keys and repeat system.out.println (" method 2"); Set<String> keySet = map.keyset (); For (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)); Println (" println ");} // Get a Set of values. Collection valueSet = map.values(); Iterator Iterator iter3 = valueset.iterator (); Iterator iter3 = valueset.iterator (); Value while (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 traversal of keySet and valueSet, essentially = traversal of keySet twice: 1 = iterator to iterator, 2 = value operation to fetch key from HashMap (via key values hashCode and equals) // 2. For entrySet traversal, essence = traversal once = get Entry of storage entity (store key and value)Copy 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. The smaller the loading factor is, the fewer the elements are filled = the smaller the space utilization, the smaller the chance of conflicts, the higher the search efficiency (the linked list is not long) // The actual loading factor final float loadFactor; // Default loading factor = 0.75 static final float DEFAULT_LOAD_FACTOR = 0.7f; // 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


Schematic diagram

  • Load factors are detailed here


Schematic diagram

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:


Schematic diagram

  • 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 argument /** * constructor 1 described in the previous section: Default constructor (no arguments) * load factor & capacity = default = 0.75, 16 */ public HashMap() {// Actually call constructor 3: 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); } /** * constructor 3: Public HashMap(int initialCapacity, int initialCapacity, int initialCapacity, Float loadFactor) {// The maximum capacity of HashMap can only be MAXIMUM_CAPACITY, If (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


Schematic diagram

  • Source code analysis
/** * use the 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. Table if (table == EMPTY_TABLE) {inflateTable(threshold); inflateTable(threshold); inflateTable(threshold); inflateTable(threshold); } // 2. Check whether key is null (analysis 2) // 2.1 If key == null, then put the key in the first place of table [0] // (essential: Table [0] where key = Null; hash = 0; If (key == null) return putForNullKey(value); (Analysis 3) // 2.2 If key is not null, calculate the position (subscript, index) in the array table // a. Compute hash value based on key int hash = hash(key); Int I = indexFor(hash, table.length); int I = indexFor(hash, table.length); For (Entry<K,V> e = table[I]; 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), With a new value to replace the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; // and return the old value}} modCount++; (Analysis 5) // 3.2 If the key does not exist, add key-value to the table addEntry(hash, key, value, I). return null; }Copy the code
  • A flow chart based on source code analysis


Schematic diagram

  • 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)

/** * 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 the value to: > The smallest power of 2 of the incoming capacity return 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]

If (key == null) return putForNullKey(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 value for (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); return oldValue; } } modCount++; AddEntry (0, null, value, 0); addEntry(0, null, value, 0); // the first argument to a.addentry () = hash = 0 // b. If key = null, hash = 0. If key = null, hash = 0 If the key of a HashTable is null, an exception will be thrown. // 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)

/** * a. */ a. ->> Analyze 1 int hash = hash(key); 2 int I = indexFor(hash, table.length); /** ** Hash (key) * The implementation of this function is different in JDK 1.7 and 1.8, but the principle is the same. JDK 1.7 does 9 perturbations = 4 bits + 5 xor * JDK 1.8 simplifies the perturbation function = only 2 perturbations = 1 bit + 1 Xor */ / JDK 1.7 implementation: Static final Int hash(int h) {h ^= k.hash (); static final int hash(int h); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // JDK 1.8 implementation: convert key to hash = use hashCode() + 1 bit + 1 xor (2 perturbations) // 1. H = key.hashcode () // 2. H ^ (h >>> 16) static final int hash(Object key) {int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); // a. When key = null, hash = 0. If the key of a HashTable is null, an exception will be thrown. Therefore, the key of a HashTable cannot be null. If key ≠ null, then the hashCode is disturbed by first calculating the hashCode() of the key (denoted by h) : binary} /** * function by bitwise xor (^) hashCode itself moved 16 bits to the right. IndexFor (hash, table.length) * JDK 1.8 does not actually have this function, but the principle is the same, Static int indexFor(int h, int length) {return h & (length-1); static int indexFor(int h, int length) {return h & (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)


    Schematic diagram

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:

  1. Why not just go through itHashCode ()Handles the hash code as a storage arraytableThe subscript position of?
  2. Why use hash and operation (&) (array length -1) to compute array subscripts?
  3. 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


Schematic diagram

  • 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


Schematic diagram

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


Schematic diagram

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

For (Entry<K,V> e = table[I]; 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), With a new value to replace the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; // and return the old value}} modCount++; // 2.2 If the key does not exist, add key-value to the table addEntry(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:




Schematic diagram

Analysis of 2:keyThe comparison of the value

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


Schematic diagram

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
For (Entry<K,V> e = table[I]; e ! = null; e = e.next) { Object k; // 2.1 If the key already exists, The new value to replace the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 2.2 If the value of the key does not exist, add key-value to the table addEntry(hash, key, value, I). /** * addEntry(hash, key, value, I) */ void addEntry(int hash, K key, V value, Int bucketIndex) {// parameter 3 = insert array table index position = array subscript // 1. Check whether the capacity is sufficient // 1.1 If not, expand the capacity by 2 times, recalculate the Hash value, and recalculate the storage array subscript if ((size >= threshold) && (null! = table[bucketIndex])) { resize(2 * table.length); // a. Expand capacity by 2 --> analyze 1 hash = (null! = key) ? hash(key) : 0; // b. Recalculate the hash value of the Key bucketIndex = indexFor(hash, table.length); // c. Recalculate the hash array of the Key} // 1.2 If the hash array is large enough, 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; If (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; if (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. For (int j = 0; for (int j = 0; j < src.length; J ++) {// 3.1 Get each Entry of the old array <K,V> e = SRC [j]; if (e ! SRC [j] = null; SRC [j] = null; Note: When transferring a linked list, save the next node because it is a single linked list. Otherwise, the linked list will break Entry<K,V> next = e.next; 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); }}} /** * 2: createEntry(hash, key, value, bucketIndex) */ void createEntry(int hash, 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. Old entries are added to the linked list (resolving Hash conflicts) 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


Schematic diagram

2. Capacity expansion mechanism

  • The specific process is as follows:


Schematic diagram

  • The diagram for transferring data during capacity expansion is as follows


Schematic diagram

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

  • Schematic diagram


    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:


Schematic diagram

  • Specific source code analysis is as follows
/** * get(key) from HashMap */ map.get(key); Public V get(Object key) {// 1. If (key == null) return getForNullKey(); if (key == null) return getForNull; 2 Entry<K,V> Entry = getEntry(key); return null == entry ? null : entry.getValue(); } /** * getForNullKey() When key == null, */ private V getForNullKey() {if (size == 0) {return null; if (size == 0) {return null; } for (Entry<K,V> e = table[0]; e ! = null; If (e.key ==null) return e.value; if (e.key ==null) return e.value; } return null; } /** * parse 2: getEntry(key) */ Final Entry<K,V> getEntry(Object key) {if (size == 0) {return null; } // 1. Use hash () to calculate the corresponding hash value based on the key value int hash = (key == null)? 0 : hash(key); // 2. Calculate the array index based on the hash value // 3. Run through all nodes of the linked list whose array element is the first node. Find the value corresponding to the key for (Entry<K,V> e = table[indexFor(hash, table.length)]; e ! = null; e = e.next) { Object k; / / if equal hash value & key, then prove that the Entry = we need keys to / / by the equals () to determine whether a key is equal to the if (e.h ash = = hash && ((k = e.k ey) = = 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; Returns true Boolean containsValue(Object value); // Check whether there is a key-value pair for this value; Returns true if yesCopy 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 isEmpty() {return size == 0; } /** * public int size() {return size;} /** * public int size() {return size; } public void clear() {modCount++;} public void clear() {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, If (table == EMPTY_TABLE) {inflateTable((int) math. Max (numKeysToBeAdded * loadFactor, threshold)); } // 3. If the number of copies required is greater than the threshold, If (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 to 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) { return null; Int hash = (key == null)? 0 : hash(key); Int I = indexFor(hash, table.length); // 2. 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--; Table [I] if (prev == e) table[I] = next; // Otherwise, next in the first Entry of the current Entry in the linked list with table[I] as the head is set to next of the current Entry (i.e. delete the current Entry = skip the current Entry directly) else prev.next = next; e.recordRemoval(this); return e; } prev = e; e = next; } return e; } /** * function: containsKey(Object key) * */ public Boolean containsKey(Object key) {return getEntry(key)! = null; } /** * function: containsValue(Object value) * Public Boolean containsValue(Object value) {// If value is null, Call containsNullValue() if (value == null) return containsNullValue(); [] 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; // Return true return false; } // Call method when value is null private Boolean containsNullValue() {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


    Schematic diagram

  • Add & query data flow


    Schematic diagram

  • Expansion mechanism


    Schematic diagram

And 7.JDK 1.8The 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


Schematic diagram

7.2 Obtaining Data (Similar to obtaining data)


Schematic diagram

7.3 Capacity Expansion Mechanism


Schematic diagram

8. Bonus: Additional questions about HashMap

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


Schematic diagram

  • Specific as follows

8.1 How can Hash Table Conflicts Be Resolved


Schematic diagram

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


Schematic diagram

  • 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; If (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; if (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. For (int j = 0; for (int j = 0; j < src.length; J ++) {// 3.1 Get each Entry of the old array <K,V> e = SRC [j]; if (e ! SRC [j] = null; SRC [j] = null; Note: When transferring a linked list, save the next node because it is a single linked list. Otherwise, the linked list will break Entry<K,V> next = e.next; 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

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

  • If (multithreading) concurrent executionPut ()Operation, in case of capacity expansionCircular linked lists are easy to appearTo create an infinite loop as data is fetched and the linked list is traversed (Infinite Loop), that is, the deadlock state, see the following figure:

Initial status, Step 1, Step 2


Schematic diagram

Schematic diagram

Schematic diagram

Note: Since JDK 1.8 transfers data = traverses the linked list in the same order as the old list and inserts the new list in the same order, there will be no reverse order or inversion of the linked list, so it is not easy to have circular lists.

However, JDK 1.8 is still not thread safe because there is no synchronization lock protection

8.3 Why wrapper classes such as String and Integer in HashMap are suitable as key keys


Schematic diagram

8.4 in the HashMapkeyifObjectType, which methods need to be implemented?


Schematic diagram

That’s all you need to know about hashmaps.

9. To summarize

  • This paper mainly explainsJavatheHashMapSource code & related knowledge
  • So I’m going to continue with thisJava,AndroidOther knowledge in depth, interested can continue to pay attention toCarson_Ho android Development Notes

Thumb up, please! Because your encouragement is the biggest power that I write!

The Android event distribution mechanism is the most comprehensive and easy to understand solution for Android screen adaptation. It is the most comprehensive and easy to understand solution for Android screen adaptation. Android development: JSON introduction and the most comprehensive analysis method! BroadcastReceiver Is the most comprehensive version of Android’s BroadcastReceiver

Welcome to attentionCarson_HoJane books!

Share the dry things about Android development from time to time, the pursuit of short, flat, fast, but there is no lack of depth.