The data structure

The Node structure

static class Node<K.V> implements Map.Entry<K.V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}
Copy the code

A HashMap structure

public class HashMap<K.V> extends AbstractMap<K.V>
    implements Map<K.V>, Cloneable.Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final int MAXIMUM_CAPACITY = 1 << 30;
    static final float DEFAULT_LOAD_FACTOR = 0.75 f;
    static final int TREEIFY_THRESHOLD = 8;
    static final int UNTREEIFY_THRESHOLD = 6;
    static final int MIN_TREEIFY_CAPACITY = 64;
    /* ---------------- Fields -------------- */
    transient Node<K,V>[] table;
    transient Set<Map.Entry<K,V>> entrySet;
    transient int size;
    transient int modCount;
    int threshold;
    final float loadFactor;
}
Copy the code

Red-black tree structure

static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}
Copy the code

Get the query

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key);
Copy the code

1. Compares keys hash, reference addresses (==), equals, and returns if they are equal.

2. If not, then check whether it’s a linked list or a red-black tree. ((TreeNode
   
   )first).getTreenode (hash, key); .
   ,v>

Calculate the hash value

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

XOR with the high 16 bits at the low 16 bits reduces the probability of hash collisions because the high hash bits are not used due to the limited length of the hash table. Using this approach is a trade-off between speed of execution, utility, and quality of extension.

Put adds elements

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

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict);
Copy the code

1. If the table is null or its length is 0, expand resize().

2. Hash table (n – 1) hash table (n – 1) hash table (n – 1) hash table (n – 1) hash table

   • If it is empty, create a new node and place the node in that location.

   • If the position is not empty:

     • Check whether the key of the first Node is consistent. If so, assign the Node to the local variable Node
       
       e.
       ,v>

     • If the node is a TreeNode, e = ((TreeNode
       
       )p). PutTreeVal (this, TAB, hash, key, value); .
       ,v>

     • If it is a linked list, iterate over the list and record the number of nodes on the list. If it finds a node that matches the key to be added, assign that node to variable E. If it does not find one, create a new node and insert it into the end.

3. If (e! AfterNodeAccess (e) = null), afterNodeAccess(e); , returns the old value.

4. ++modCount is executed if the hash table does not already have a key to add. ; If the size is larger than the threshold, expand the capacity. AfterNodeInsertion (EVICT); , returns null (because there is no old value).

Initialization or capacity expansion

final Node<K,V>[] resize();
Copy the code

1. First calculate the new capacity newCap and the new threshold newThr:

   • DEFAULT_INITIAL_CAPACITY = 1 << 4. The new threshold is equal to (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);

   • If the initial capacity is set and initialized (there is no field in the HashMap that sets the total capacity, and the set initial capacity is initially assigned to the threshold variable), set newCap and calculate the new newThr.

   • For capacity expansion, both the new capacity and the threshold are doubled. If the original capacity is greater than MAXIMUM_CAPACITY, the threshold is set to the maximum integer value.

2. Create a new hash array and rehash the old array by iterating over it:

   • If there is only one node in this position, newTab[e.hash & (newcap-1)] = e; ;

   • If it’s a linked list, because the new array is twice the size of the old one, a node will either rehash at the same index or at the same index +oldCap. Then use the tail insertion method to migrate the nodes in the linked list, so set the high and low head and tail nodes, and then use (e.hash & oldCap) == 0 to calculate whether the new bit is 0 or 1 to add to the high or low tail node. Finally, the high and low head nodes are placed in their respective positions in the array.

   • If the location is a TreeNode, split the tree final void split(HashMap
     
     map, Node
     
     [] TAB, int index, int bit)
     ,v>
     ,v>