At the beginning of a HashMap experience

Such as linear tables, tree and other queries (split search, binary sort tree search, B tree search), this kind of search belongs to the comparison type of search, that is to say, the query efficiency completely depends on the number of comparisons. Why do we compare? Because when we store the positions of the elements, it’s completely random.

Hash table is another way of query, is to store elements and storage location to suggest a corresponding relationship, so that you can not find elements through comparison, similar to the dictionary in life, through the keyword directly find the page number of the keyword.

Hash == relational mapping ==f(x)=x

For example, the keyword is our province, the mapping relationship is to take the first letter of the first letter, according to the alphabetical order, find the corresponding storage subscript

Storage structure

1. If we want to find BEIJING, go through keyword relational mapping, find the subscript 02, find the element
2. For different keys, the corresponding F (x) is the same. For example, If SHANXI and SHANGDONG both correspond to 19, this phenomenon is calledHash conflictHashish conflict cannot be avoided. It has to be managed at the time of conflict
3. A data set consisting of a hash algorithm is a hash table

There are several ways to do this, but I’m only going to focus on the HashMap method, chain address method, when hash conflicts occur, take array + chain (of course HashMap has its own optimization)

In order to understand HashMap, I learned this knowledge in advance to help understand

• Balanced binary trees
• Red and black tree

1. Store node table array

• transient Node
  
  [] table; .
  ,v>

• Node is a linked list type

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

• A Node is a TreeNode that can be converted to a red-black tree. TreeNode is a subclass of Node

  public class LinkedHashMap<K.V> extends HashMap<K.V> implements Map<K.V>
      static class Entry<K.V> extends HashMap.Node<K.V> { Entry<K,V> before, after; . }}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
  	booleanred; . }Copy the code

The table array storage structure is shown below



2. Other attributes

/ / table. Length: capacity
transient Node<K,V>[] table;
// Number of nodes that have been stored in HashMap
transient int size;
// Capacity expansion threshold. When the number of HashMaps reaches this threshold, capacity expansion is triggered
int threshold;
// Load factor, capacity expansion threshold = Capacity x load factor.
final float loadFactor;
Copy the code

The general idea is the above description, the details are different, some important code to illustrate the screenshot

We have reviewed the principle of hash tables, so the four important properties of the above are of course, so it is necessary to master some of the necessary theory.

The default value

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75 f;
Copy the code

3. The array capacity attribute states that the size of the HashMap must be 2 to the power of N. Of course, the HashMap supports passing in an initial capacity. If it is not 2 to the power of N, the code will convert

   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }
   Copy the code

   
   [] transient Node
   
   [] table; The code saves the country through the threshold expansion variable curve. It is used as capacity first, and then changed back when initialized.
   ,v>
   ,v>

       public HashMap(int initialCapacity, float loadFactor) {
           this.loadFactor = loadFactor;
           this.threshold = tableSizeFor(initialCapacity);
       }
   Copy the code

   Threshold and capacity corrected back
   
   

So tableSizeFor how does tableSizeFor convert data that’s not two to the N to two to the N

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
Copy the code

The code is actually pretty simple, and the idea is pretty simple, and it’s actually pretty easy to understand, not as complicated as everyone says, but let me explain the idea

Suppose we are using 32 bits of storage with the highest bit being 1

We can see from the above operation that the number after the highest digit is filled with 1, that is, we just have to control the highest digit, and finally by +1, the number must be 2 to the N

Let me give you an example

• Example 1) If the input parameter is 16 and the binary value is 00010000, runint n = cap - 1;Then 00001111, after the logical operation, the highest bit 1 is followed by 1, 00001111n + 1;, becomes the final capacity size 00010000=16
• Example 2) If the input parameter is 25 and the corresponding binary is 00011001, runint n = cap - 1;Then it will become 00011000. After logical operation, the highest bit 1 will be filled with 1 to become 00011111. Finally, it will be executedn + 1;, becomes the final capacity size 00100000=32

This figure is a reference to the original author, their own draw with the source code, to be honest, if only see this figure is easy to forget, it is best to follow the source code to see it again. Code entry: java.util.hashmap #resize

How to understand(e.hash & oldCap) == 0New hash address judgment

NewCap = oldCap << 1; newCap = oldCap << 1; NewCap = oldCap * 2;

As can be seen from the calculation formula of hash address, since we move the address to the left by one bit, that is to say, cap-1 will add a 1 to the original. For example, oldCap-1 is 0000 1111, newCap-1 is 0001 1111. (e.hash & oldCap) == 0

Since the relationship between the oldCap and the new one is twice that of the old one, the distance between the old one and the new one is one oldCap, which is quite clever

The major optimizations in JDK 1.8 include the following:

1. The underlying data structure is changed from “array + linked list” to “array + linked list + red-black tree”, mainly to optimize the search performance of long linked list when hash conflicts are serious: O(n) -> O(logn).
2. The way to calculate the initial capacity of the table has been changed. The old way is to start from 1 and continue to the left until a value greater than or equal to the input capacity is found. The new method is calculated by “5 shift + or equal operations”.
3. Optimized the way the hash value is computed, the old one is done with a random JB operation, and the new one simply involves the higher 16 bits
4. During capacity expansion, the insertion mode is changed from Head insertion to tail insertion, avoiding dead loops in concurrent scenarios
5. During capacity expansion, the index position of compute nodes in the new table is changed from H & (Length-1) to Hash & oldCap. The performance may not improve much, but the design is more clever and elegant.

other