debug is familiar with HashMap's source code

1. New HashMap, when adding the first data

(1) Execute new HashMap<>();

• Call the constructor and set the load factor to the default load factor (0.75): static final float DEFAULT_LOAD_FACTOR = 0.75f;

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

(2) Execute map.put(key,value);Method

• put() method calls putVal()

public V put(K key, V value) {
    return putVal(public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }, key, value, false, true);
}

• Calculate hash:

  • If key is null, set hash = 0 for key
  • If not null, the String.hashCode() method is called to calculate the hash value (Object.hashCode() - > String.hashCode())

  public int hashCode() {
      int h = hash;
      if (h == 0 && value.length > 0) {
          char val[] = value;
  
          for (int i = 0; i < value.length; i++) {
              h = 31 * h + val[i];
          }
          hash = h;
      }
      return h;
  }	
  

  • The calculated hash is then XOR (^) with the unsigned right shift of 16 bits, and XOR with itself to get the final hash value.

  static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
  

• Execute putVal()

  • The first step is to determine if a new HashMap is created, and if so, resize() is called to initialize it

  //putVal()
  if ((tab = table) == null || (n = tab.length) == 0)
      n = (tab = resize()).length;
  

  • The part used by resize():
    • Transient Node<K, V>[] table;The table in this case is the container where HashMap stores data
    • Default capacity: static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //Aka 16
    • Load factor: static final float DEFAULT_LOAD_FACTOR = 0.75f;
    • newThr: Initialization gets a threshold of 12

  //resize()
  else {               // zero initial threshold signifies using defaults
      newCap = DEFAULT_INITIAL_CAPACITY;
      newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  }
  
  threshold = newThr;
  Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
  table = newTab;
  //Because newTab is null, return newTab
  return newTab;
  

  • After initializing the storage container, calculate the storage location of the data: (n - 1) & hash and determine if there are elements in that location

    • We added it for the first time, and there are no elements at this time, so we put the elements directly in that position

    //putVal()
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    /*
    	Node Is the node that stores data on HashMap
        // Create a regular (non-tree) node
        Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
            return new Node<>(hash, key, value, next);
        }
    */
    

  • Then add 1:++ modCount to the counter of the number of statistical modifications (hash counts);

• putVal() end, put() end, storage complete

2. Add Follow-up Data

(1) map.size is less than the threshold after adding data

<1>When hash conflicts do not occur, add directly succeeded

//putVal()
if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

<2>When a hash conflict occurs

• Will determine if the same key already exists, if the same will overwrite the previous ode Node

//p = tab[i = (n - 1) & hash]
Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

• It then determines whether it is a tree node and, if so, whether it exists in a red-black tree.

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

• If not, then hang the new Node after the node at that location

else {
    for (int binCount = 0; ; ++binCount) {
        //Determine if a node at the current location has children
        if ((e = p.next) == null) {
            //If there are no child nodes, then hang the new node on p->next
            p.next = newNode(hash, key, value, null);
            //Determine if it is greater than the tree threshold, and if it is greater, perform the tree operation
            if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                treeifyBin(tab, hash);
            break;
        }
        //Determines if the key of the child node is the same as that of the new node, and if it is the same, ends the loop directly, overwriting the previous value
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            break;
        //If there are currently child nodes, loop the new node to the next of the child nodes
        p = e;
    }
}

(2) After adding data, map.size is greater than the threshold value

<2>When container storage reaches threshold

if (++size > threshold)
    resize();

• Call resize() expansion

  • If the current capacity reaches the default maximum capacity, set the threshold to the maximum of Integer type without changing the maximum capacity

    if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
    }
    

  • If the maximum capacity is not reached, the capacity is bitwise right shifted by one bit (doubled), and the threshold is bitwise right shifted by one bit (doubled)

     else if ( (newCap = oldCap << 1) < MAXIMUM_CAPACITY 
              && oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold
    

  • Once the expansion is complete, copy the data first, and then migrate the copied data to the appropriate location of the new array (a clever algorithm in the migration process: (e.hash & oldCap)== 0, when 0, the data node does not need to move, not 0, the node will move backwards a position of the length of the old capacity, the specific algorithm is somewhat complex to understand, it is recommended that Baidu look at the analysis of the lao)

  • Determine whether there are child nodes and whether they are root nodes of the tree during migration

    • If there are child nodes and they are converted to a red-black tree, they are passed ((TreeNode<K, V>) E. split (this, newTab, j, oldCap);To complete data migration

    • If you have child nodes that have not been converted to a red-black tree, do the following:

      • The two Node:lo and hi defined have different meanings, the lo node is placed in place and the hi node is placed after the offset

        Node<K,V> loHead = null, loTail = null;
        Node<K,V> hiHead = null, hiTail = null;
        

      • Data Copies (Take one case for analysis, because the storage location offset has no effect on data copies)

        do {
            next = e.next;
            if ((e.hash & oldCap) == 0) {
                if (loTail == null)
                	loHead = e;
                else
                	loTail.next = e;
            	loTail = e;
            }
            else {
                if (hiTail == null)
                	hiHead = e;
                else
                	hiTail.next = e;
                hiTail = e;
            }
        } while ((e = next) != null);
        

      • data migration

        if (loTail != null) {
            loTail.next = null;
            newTab[j] = loHead;
        }
        if (hiTail != null) {
            hiTail.next = null;
            newTab[j + oldCap] = hiHead;
        }
        

• The above steps perform the number of times the old capacity size is used to migrate all the data to the array and return the new array when the migration is complete

3. Expansion of tree and tree nodes

Part of the content of red and black trees has not been studied in depth yet, involving the data structure of red and black trees, and dig this block when you have learned the principle of red and black trees in depth.

treeifyBin(tab, hash);	//Tree
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);	//Expansion