Read HashMap

In this article, you will see the source code of HashMap from the perspective of initialization and put(), including the explanation of parameters, expansion mechanism, hash algorithm, and the difference between JDK1.7 and JDK1.8.

Argument parsing

Capacity: Indicates the number of key-value pairs in a HashMap. It is represented by the attribute size

transient int size;

Threshold: indicates whether the threshold needs to be expanded. LoadFactory: indicates the loading factor, which is used to calculate the threshold. The loading factor is a float.

1. Initialize the HashMap

1.1 HashMap1.7 Initialization

Initialization purpose: Initialize parameters and internal table::Entry field

Just read the no-argument constructor and know that the initialization of a HashMap in JDK1.7 occurs in new HashMap a. Constructor HashMap(){// 1. Initialize parameter this.loadfactor = DEFAULT_LOAD_FACTOR; // Default DEFAULT_LOAD_FACTOR=0.75f threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); Table = new Entry[DEFAULT_INITIAL_CAPACITY]; // 2. } b. Parameter constructor public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { // 1. Verify parameters... // 2. Initialize parameter this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); Table = new Entry[capacity]; // 3. // 4. Init () is an extension method. }Copy the code

1.2 HashMap1.8 Initialization

In JDK1.8, only “partial” parameter assignments are done in the constructor, and the table::Node object is not actually constructed.

Public HashMap() {this.loadfactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } b. Public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(int initialCapacity, float loadFactor) { 1. LoadFactor = loadFactory // Find the nearest power of 2 to initialCapacity: InitialCapacity = 10, this.threshold = 16; this.threshold = tableSizeFor(initialCapacity); }Copy the code

As you can see in JDK1.8, the constructor does not actually initialize, but only assigns values to some attributes

2. Put () method in HashMap

Regardless of 1.7 or 1.8, the purpose of the put() method is to ensure that a key-value pair is added to the HashMap. Resize (), hash, index calculation, etc.

2.1 PUT () in JDK1.7

Put () process:

  1. Check whether the table is empty: if it is empty then initialize it (JDK1.7 will not be empty)
  2. Check whether the same key already exists
  3. If the same key does not exist, call addEntry() to add an entry node

A HashMap expansion. PNG

public V put(K key, V value) { // 1. Check whether the table is empty: If the table is empty, initialize it. If (table == EMPTY_TABLE) {inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); Check whether the same key exists for (Entry<K,V> e = table[I]; e ! = null; e = e.next) { Object k; If (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {/ / judge the same key to replace the old value V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; }} // 3. If there is no same key, add data directly to modCount++; addEntry(hash, key, value, i); return null; }Copy the code

Let’s dig deeper into the put() method, and by the end of the study you’ll know the following

  1. How do you compute hashes and indexes, and what happens if hashCode conflicts?
  2. How to determine the same key in a HashMap? What happens if there are elements in the index position of the newly inserted element? Does HashMap in JDK1.7 use header or tail interpolation? Please describe the process of insertion.
  3. When does expansion take place in JDK1.7? Insert and then expand or expand and then insert?

Let’s look at the first question: how do we compute hashes and indexes?

Let’s look at the first question:

  • How to determine the same key in a HashMap?

A: First of all determine whether indexes in value, and then traverse the same index value, to determine whether there is the same key first hash same second key index or content if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k)))

  • What happens if there are elements in the index position of the newly inserted element?

A: If there are elements in the index position, they can be divided into same key/different key. If the keys are the same, the old value can be replaced directly. If the keys are different, the program will run down.

  • Does HashMap in JDK1.7 use header or tail interpolation?

A: To understand this, take a look at the addEntry() source code

// 3. If there is no same key, add data directly modCount++; addEntry(hash, key, value, i); return null; void addEntry(int hash, K key, V value, int bucketIndex) { // a. If ((size >= threshold) && (null! = table[bucketIndex])) { resize(2 * table.length); hash = (null ! = key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } // b. Create element createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) {// Retrieve the current element. If the key is newly added, e is null and the existing element is not empty. Entry<K,V> e = table[bucketIndex]; // Add a new key-value value or create a linked list. Table [bucketIndex] = new Entry<>(hash, key, value, e); size++; }Copy the code

So you can see that the element is inserted by header method, and the element at the original index (or null) is the next of the new element

  • When does expansion take place in JDK1.7?

A: Resize () is used for capacity expansion

  1. Setting a new entry
  2. Transfer the old element to the new entry (what is the index of the data with the original index I in the new entry?)

2.2 PUT () in JDK1.8

In JDK1.8, the original array + list data structure has been changed to array + list/red-black tree after reading this section

  1. What is the initialization time in JDK1.8?
  2. Expansion opportunity in JDK1.8
  3. Hash and index calculations in JDK1.8

Regression the put() method itself, the put() purpose adds an element, the overall flow chart is as follows

It can be concluded from the flow chart:

  1. What is the initialization time in JDK1.8?

A: The real initialization occurs during put(Object key). A: Add nodes before deciding whether to expand capacity. 3. Hash and index calculation in JDK1.8

index:i
hash = hashCode^hashCode>>>16;
i = e.hash & (newCap - 1);
Copy the code