In the previous section, we examined the structure and main methods of HashMap in JDK8. In this section, we compare the implementation of HashMap in JDK7

1.put & addEntry

-put()

  1. Compute the hash value based on the key and obtain the slot position based on the hash value
  2. Traverses the linked list of current slot points
    • OldValue is returned if the same key is overridden
    • If there is no node with the same key, addEntry to the new node.
public V put(K key, V value)
{...// Computes the Hash value
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // Traverses the list of slots
    // Note: there is no red black tree in JDK7 yet, so the only solution to hash collisions is zippers
    for(Entry<K,V> e = table[i]; e ! =null; e = e.next) {
        Object k;
        // If the key already exists, replace the old value
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // The key does not exist and a node needs to be added
    addEntry(hash, key, value, i);
    return null;
}
Copy the code

--addEntry()

When the key does not exist, the addEntry() method is called to add a new node

void addEntry(int hash, K key, V value, int bucketIndex)
{
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    // Check whether the current size exceeds the threshold. If so, resize is required
    if (size++ >= threshold)
        resize(2 * table.length); // Directly pass in the expanded size, 2*len
}
Copy the code

2.resize & transfer

-resize()

Determine whether you can expand the array and create a new array

// Pass in a new capacity
void resize(int newCapacity) {   
    // Reference the Entry array before expansion
    Entry[] oldTable = table;    
    int oldCapacity = oldTable.length;  
    // The size of the array before the expansion has reached the maximum (2^30)
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        // Change the threshold to the maximum value of int (2^31-1) so that the capacity will not be expanded later
        threshold = Integer.MAX_VALUE;  
        return;  
    }  
    
	// Initialize a new Entry array
    Entry[] newTable = new Entry[newCapacity];  
    / /!!!!! Move the data to the new Entry array, which contains the most important repositioning
    transfer(newTable);    
    // Set the new array created by the current thread to an array of maps
    table = newTable; 
    // Change the threshold
    threshold = (int) (newCapacity * loadFactor);
}
Copy the code

--Transfer (real expansion)

Capacity Expansion policy:

  1. Recalculate all nodes of the original array
  2. Save the original linked list: e saves the current node, next records a node (e.next)
    • New slot nod insert (note: put is tail insert)
      • Connection: e.next = newTab[I]
      • Move down: newTab[I] = e
    • Move to the next node: e = next
void transfer(Entry[] newTable) {  
    // SRC references the old Entry array
    Entry[] src = table;                    
    int newCapacity = newTable.length; 
    // Iterate over the old Entry array
    for (int j = 0; j < src.length; j++) { 
        Entry<K, V> e = src[j];             
        if(e ! =null) {  
            // Releases the object reference of the old Entry array
            src[j] = null;  
            do {  
                // next is used to save the nodes after the current node
                Entry<K, V> next = e.next;  
                / /!!!!! Recalculates the position of each element in the array
                int i = indexFor(e.hash, newCapacity);  
                // Insert the new slot
                e.next = newTable[i]; / / tag [1]
                // Put the element on the array
                newTable[i] = e; 
                // The original list node moves back
                e = next;              
            } while(e ! =null); }}}Copy the code

3. Deadlock analysis during capacity expansion

  • The prerequisite for a deadlock
    • Multiple threads need to be expanded simultaneously
      • Both threads have created arrays in their stack space
      • And a thread just executes until it finishes saving E, next, and suspends
    • E and next are still in the same slot after expansion
do {
  Entry<K,V> next = e.next; // Thread 1 execution is now suspended, thread 2 execution
  int i = indexFor(e.hash, newCapacity);
  e.next = newTable[i];
  newTable[i] = e;
  e = next;
} while(e ! =null);
Copy the code

  • Deadlock cause After three cycles, the loop is formed, and the two nodes on the new slot are a.next = b&&b.next = A

  • Process diagram

    • Thread one records execution status and suspends

    • Thread 2 completes capacity expansion. After capacity expansion, E Next is still in the same slot and in reverse order. Thread 1 records e next unchanged

    • As soon as the thread resumes running, the first loop: insert e (A) into slot (3); And then e is equal to next of B.

    • Next =e.next(A), insert e (B) into slot (3), e=next (A)

    • Next =e.next=null. Insert e (A) into slot (3) to form A loop