JDK collection source: HashMap

The PUT method is quite complex, and the implementation steps are as follows:

1. Calculate the bucket to which the key is mapped using the hash value.

2. If there is no collision on the bucket, insert the bucket directly.

3. If a collision occurs, the collision needs to be handled:

   A If the bucket uses a red-black tree to handle conflicts, the bucket uses the red-black tree method to insert data.

   B Otherwise, the traditional chain method is used. If the chain length reaches a critical value, the chain is transformed into a red-black tree;

4. If duplicate keys exist in the bucket, the new value value is substituted for that key.

5. If the size is greater than threshold, expand the capacity.

Specific methods are as follows:

public V put(K key, V value) {
    // Call hash(key) to compute the hash value of the key
    return putVal(hash(key), key, value, false.true);
}
Copy the code

Description:

1. HashMap only provides put for adding elements. The putVal method is just a method called by the PUT method and is not provided to the user. So let’s focus on the putVal method.
2. So we can see that in the putVal method key is performing a hash method here, so let’s see how the hash method is implemented.

static final int hash(Object key) {
    int h;
    // If key is null, hash value is 0,
    // Otherwise, call the key hashCode() method to calculate the hash value of the key and assign it to h,
    // Perform bitwise xor with the unsigned 16 bit right shift to get the final hash value,
    // This is done to make the calculated hash more diffuse
    // Why more diffuse? Because the more dispersed, the shorter the list length of a bucket is, the fewer red-black trees are generated later, and the more efficient it is
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the code

If a HashMap uses a key to obtain a hashCode, an exception will be thrown.

Read the above hash method:

Let’s first look at how the hash of key is computed. The hash value of the key is calculated using the above method.

This hash method first computes the hashCode of the key assigned to H, and then performs bitwise xor with the unsigned 16-bit right-shifted binary of H to get the final hash value.

The hash value calculated by the above hash function is used in putVal:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {...if ((p = tab[i = (n - 1) & hash]) == null) // Where n represents the array length 16, formula
    // (length-1) &hash = bucket subscript when array length is 2 to the NTH power,
    // This formula is equivalent to: hash % length Mod the array length
    // For example: hash % 32 = hash & (32-1). }Copy the code

The calculation process is as follows:

Description:

1. The key. The hashCode ();Return the hash value that is hashcode, let’s say a random generated value.
2. N indicates that the length of the array initialization is 16.
3. & (bitwise and operation) : Operation rule: the result of the same binary digit is 1 if it is 1, otherwise it is 0.
4. ^ (xor operation by bit) : Operation rule: in the same binary digit, the same digit, the result is 0, different is 1.

Finally get 0101==> stab with subscript 5.

To put it simply:

The high 16bits remain the same, the low and high 16bits do an xor (the resulting hashCode is converted to a 32-bit binary, the first 16 bits and the last 16 bits do an xor for the low and high 16bits).

Question: Why do you do this?

If n is a small array, let’s say 16, then n-1 is 1111, and such a value does bitwise and bits with hashCode directly, actually using only the last four bits of the hash value. If the high hash values change a lot and the low hash values change a little bit, then you’re going to have a hash conflict, so you’re going to use both the high and the low hash values, and you’re going to solve that problem.

Now, let’s take a look at the putVal method and see what it does.

Main parameters:

• Hash: Hash value of the key
• Key: indicates the original key
• Value: indicates the value to be stored
• OnlyIfAbsent: True does not change the existing value
• Evict: False indicates that the table is created

The putVal method source code is as follows:

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

static final int hash(Object key) {
    int h;// If the key is null then the hash value is 0, otherwise the key's hashCode() method is called and the high 16 bits participate in the xor of the whole hash, or if the array length is small, the high 16 bits participate in the address,
    // the addressing formula :(leng-1) & hash
    // This makes the calculated results more scattered and less prone to hash collisions
    return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    /* 1) Transient Node
      
       [] table; Represents an array that stores elements in the Map collection. 2) (TAB = table) == null N = (TAB = resize()).length; n = (TAB = resize()).length; Initialize the array and assign the initialized array length to n. 4) execute n = (TAB = resize()).length, array TAB each space is null. * /
      ,v>
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    /* 1) I = (n-1) &hash evaluates the index of the array assigned to I, i.e. determines which bucket the element is stored in. 2) p = TAB [I = (n-1) & hash] means to obtain the calculated position of the data assigned to node P. 3) (p = TAB [I = (n-1) & hash]) == null; New nodes are created based on key-value pairs and placed into buckets at that location. Summary: If the bucket has no hash collisions, the key-value pair is inserted directly into the spatial location. * / 
    if ((p = tab[i = (n - 1) & hash]) == null)
        // create a new node and store it in the bucket
        tab[i] = newNode(hash, key, value, null);
    else {
         // Else TAB [I] does not equal null, indicating that this position already has a value
        Node<K,V> e; K k;
        /* Compare the hash value of the first element (node in array) in the bucket with the key. 1) p.hash == hash: p.hash specifies the hash value of the existing data. P represents TAB [I], which is the Node object returned by the hash, key, value, null (newNode) method. Node
      
        newNode(int hash, K key, V value, Node
       
         next) { return new Node<>(hash, key, value, next); } The Node class has a hash member variable that records the hash value of the previous data. 2) (k = P. key) == key: P. key obtains the key of the original data, assigns the value to k key, and compares the address values of the two keys. 3) the key! = null && key. Equals (k) : to perform here show the address of the two key values are not equal, then the judgment before adding the key whether is equal to null, if is not equal to null to invoke the equals method to judge whether the content of the two key equal. * /
       ,v>
      ,v>
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
                /* The hash values of the two elements are equal, and the key value is also equal. Assign the old element whole object to e, and use e to record */ 
                e = p;
        // Hash value is not equal or key is not equal; Determine whether P is a red-black tree
        else if (p instanceof TreeNode)
            // Put it in the tree
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // it is a linked list node
        else {
            /* 1) If it is a linked list, it is necessary to iterate to the last node and insert 2) It is necessary to iterate to check whether there are duplicate keys */ in the linked list
            for (int binCount = 0; ; ++binCount) {
                /* 1)e = p.next gets the next element of p and assigns it to e. 2)(e = p.ext) == null Determine whether p.ext is equal to null, equal to null, p has no next element, then the tail of the linked list has been reached, and no duplicate key has been found, then the HashMap does not contain the key, insert the key value pair into the linked list. * /
                if ((e = p.next) == null) {
                    /* 1) create a newNode and insert it into the end. Node
      
        newNode(int hash, K key, V value, Node
       
         next) { return new Node<>(hash, key, value, next); } Notice that the fourth argument next is null, because the current element is inserted at the end of the list, so the next node must be NULL. 2) This method also meets the characteristics of the linked list data structure, adding new elements backwards each time. * /
       ,v>
      ,v>
                    p.next = newNode(hash, key, value, null);
                    /* 1) After the node is added, determine whether the number of nodes is greater than TREEIFY_THRESHOLD critical value 8. If so, convert the linked list to red-black tree. 2) int binCount = 0: indicates the initialization value of the for loop. Count from 0. It keeps track of the number of nodes traversed. The value is 0 for the first node, 1 for the second node... Seven is the eighth node, plus one element in the array, which is nine. Treeify_threshold-1 -- "8-1 --" 7 If the value of binCount is 7(plus one element in the array, the number of elements is 9), the value of treeify_threshold-1 is also 7, and the red-black tree is converted. * /
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // Convert to a red-black tree
                        treeifyBin(tab, hash);
                    // Break the loop
                    break;
                }
                 
                /* e = p.ext is not null and is not the last element. Continue to determine whether the key value of the node in the list is the same as the key value of the inserted element. * /
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    // equal, out of the loop
                    /* If the element to be added has the same key as the existing element in the list, the for loop is broken. Instead of continuing the comparison, execute the following if statement to replace if (e! = null) */
                    break;
                /* Indicates that the newly added element is not equal to the current node. Proceed to the next node. Used to iterate over the linked list in the bucket, combined with the previous e = p.ext to iterate over the linked list */p = e; }}/* = insert key (hash) = insert key (hash) = insert key (hash) = insert key (hash
        if(e ! =null) { 
            // Record the value of e
            V oldValue = e.value;
            // onlyIfAbsent Is false or the old value is null
            if(! onlyIfAbsent || oldValue ==null)
                // Replace the old value with the new value
                // e.value indicates the old value. Value indicates the new value
                e.value = value;
            // Callback after access
            afterNodeAccess(e);
            // Return the old value
            returnoldValue; }}// Number of times to modify records
    ++modCount;
    // Check whether the actual size is greater than threshold. If so, expand the capacity
    if (++size > threshold)
        resize();
    // Callback after insertion
    afterNodeInsertion(evict);
    return null;
}
Copy the code

(1) Compute the hash value of the key.

(2) If the number of buckets (array) is 0, initialize the bucket;

(3) If there is no element in the bucket where key resides, insert it directly.

(4) If the key of the first element in the bucket where the key resides is the same as that of the key to be inserted, the element is found, and proceed to the subsequent process (9).

(5) If the first element is a tree node, putTreeVal() is called to find the element or insert the tree node;

(6) If it is not in the above three cases, the linked list corresponding to the bucket is traversed to find whether the key exists in the linked list;

(7) If the element corresponding to the key is found, proceed to the subsequent process (9);

(8) If no element corresponding to the key is found, insert a new node at the end of the list and judge whether tree is needed;

(9) If the element corresponding to the key is found, it determines whether the old value needs to be replaced and directly returns the old value;

(10) If an element is inserted, the number is increased by 1 and the need for expansion is determined;

Delete method is to first find the location of the element, if it is a linked list to traverse the list to find the element and then delete. If you’re using a red-black tree, you go through the tree and you find it and you delete it, and if the tree is less than 6, you roll the list.

Remove remove() method:

RemoveNode removeNode removeNode removeNode removeNode removeNode removeNode
// Delete by key
public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null.false.true)) = =null ?
            null : e.value;
    }
// Delete according to key,value
@Override
public boolean remove(Object key, Object value) {
    return removeNode(hash(key), key, value, true.true) != null;
}
Copy the code

RemoveNode () method:

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    / / parameters:
    // matchValue This parameter is true when deleted based on key and value
    // movable can be ignored for now
    
    // TAB: references the hash table in the current haashMap
    // p: current node element
    // n: the current hash table array length
    // index: indicates the addressing result
    Node<K,V>[] tab; Node<K,V> p; int n, index;
	// Find the location based on the hash
	// If the bucket mapped to the current key is not empty
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) ! =null) {
        // If the bucket contains data and needs to be queried and deleted
        // node: the element to be removed by lookup
        // e: indicates the next element of the current node
        / / k, v key values
        Node<K,V> node = null, e; K k; V v;
        
        // In the first case, the element in the current bucket is the element we want to delete
        // If the node on the bucket is the key, point node to that node
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            node = p;
        // If the first element in the bucket is not the element we are looking for and e = p.ext in the bucket is not null
        // Indicates that the node in the bucket has the next node
        else if((e = p.next) ! =null) {
            // Description: The current bucket is either a linked list or a red-black tree
            
            // Check whether a red black tree has been formed in the bucket
            if (p instanceof TreeNode)
                // If the conflict is handled by the red-black tree, the node to be deleted from the red-black tree is obtained
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            // The bucket has a linked list
            else {
                // Determine whether to handle hash conflicts as linked lists
                // If it is, the list is traversed to find the node to delete
                do {
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while((e = e.next) ! =null); }}// Compare the value of the found key with that of the deleted key
        if(node ! =null&& (! matchValue || (v = node.value) == value || (value ! =null && value.equals(v)))) {
            // If the bucket is a red-black tree, delete the node by calling the red-black tree method
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            // If the bucket is a linked list
            else if (node == p)
                // Delete the list
                tab[index] = node.next;
            // If the bucket is in
            else
                // Set the next element of the current element P to the next element of the element to be deleted
                p.next = node.next;
            // Record the number of changes
            ++modCount;
            // The number of changes
            --size;
            afterNodeRemoval(node);
            returnnode; }}return null;
}
Copy the code

1. Iterate through Key and Values respectively

for (String key : map.keySet()) {
	System.out.println(key);
}
for (Object vlaue : map.values() {
	System.out.println(value);
}
Copy the code

1. Use the Iterator to iterate

Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Object> mapEntry = iterator.next();
    System.out.println(mapEntry.getKey() + "-" + mapEntry.getValue());
}
Copy the code

1. Using GET (not recommended)

Set<String> keySet = map.keySet();
for (String str : keySet) {
	System.out.println(str + "-" + map.get(str));
}
Copy the code

Description:

According to the Ali development manual, this approach is not recommended because of two iterations. KeySet gets Iterator once and iterates through get again, reducing performance.

1. After jdk8, use the default method in the Map interface:

default void forEach(BiConsumer<? super K,? super V> action) 
// Methods in the BiConsumer interface:
	void accept(T t, U u)Perform this operation on the given parameter. Parameter t - first input parameter u - second input parameterCopy the code

Traversal code:

HashMap<String,String> map = new HashMap();
map.put("001"."zhangsan");
map.put("002"."lisi");
map.forEach((key, value) -> {
    System.out.println(key + "-" + value);
});
Copy the code