The HashMap JDK1.7

Important member attributes
Static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // Maximum hash table capacity static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; static final float DEFAULT_LOAD_FACTOR = 0.75f; // Empty hash table static final Entry<? ,? >[] EMPTY_TABLE = {}; // To expand the hash table, the length must always be a power of 2. transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;Copy the code
The constructor
Map<String, String> map = new HashMap<String, String>(); Or Map<String, String> Map = new HashMap<String, String>(11);Copy the code



If no parameter is passed, the default initial capacity is 16 and the load factor is 0.75.



If you take an initialization argument, it says that the initial capacity has to be a power of two, but what if it’s not passed to a power of two?

Put () method



In the put() method of a HashMap, the hash table is initialized if it is empty.



While doing the initialization,The initial capacity passed in is converted to the nearest power of 2.

And then we’re going to hash the key.



The length has to be a nonzero power of 2, so why length-1?

H = 0001 0101 0111 0010 1111 length = 0000 0000 0000 0000 0000 0000 16 length = 0000 0000 0000 0000 1111 (16 minus 1=15Copy the code



Then, the for loop, replaces the value of the same key.



Then we move on to the important method, where we expand the hash table.

Check whether the capacity of the current hash table is greater than threshold(capacity x expansion ratio 0.75) and expand the hash table. Capacity expansion is performed by using the current hash table capacity x 2. Create a new array.



Once you have a new array, you start transferring data, which is done in the Transfer () method.



To transfer data in the Transfer () method, looping requires rehashing the key, which means that the key’s position in the old array is not necessarily the same as that in the new array. Then move the data from the old array to the new array.

Single-thread capacity expansion

Assuming thatThe hash algorithm is simply the remainder of key and length. Hash table length 2, if not expanded, then elements 3,5, and 7 should be collided into table[1] by calculation (key%table.length).

capacity: The length of the hash table will be expanded to 4, and key=3 will be rehash on table[3] (3%4=3). The current e.ext is key(7). Continue the while loop to rehash, key=7 will be rehash on table[3] (7%4=3), resulting in a collision. The while loop rehashes the key=5 into the table[1] (5%4=3). If e.ext is null, the while loop is broken, and resize ends.

Multithreaded capacity expansion
while(null ! = e) { Entry<K,V> next = e.next; Int I = indexFor(e.hash, newCapacity); // line 2 e.ext = newTable[I]; NewTable [I] = e; // Line 4 e = next; // Line 5}Copy the code

As you can see from the figure above, since e of thread 1 points to key(3) and next points to key(7), after thread 2 rehash, it points to the linked list after thread 2 rehash. Thread 1 is then woken up:

  1. E.next = newTable[I]; next for key(3) points to the new Hash table for thread 1.
  2. Execute newTable[I] = e, so the first element of thread 1’s new Hash points to key(3) of thread 2’s new Hash. All right, e is done.
  3. Say e = next, point e to next, so the new e is key(7).

Next key(7) for key(3) :

  1. Now the e node is key(7), so the first Entry next = e.next is key(3)
  2. E.next = newTable[I] next for key(7) is key(3)
  3. If newTable[I] = e is executed, the first element of thread 1’s new Hash table becomes key(7) 4. Say e = next, point e to next, so the new e is key(3).

The state is:



Next key(3) for key(7) :

  1. Now the e node is key(3), so the first Entry next = E.next is null
  2. E.ext = newTable[I], next for key(3) becomes key(7)
  3. If newTable[I] = e, the first element of thread 1’s new Hash table becomes key(3).
  4. Say e = next, point e to next, so the new e is key(7).

The state at this time is shown in the figure:



We have circular linked lists.

The HashMap JDK1.8

Important member attributes
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 static final int MAXIMUM_CAPACITY = 1 << 30; Static final float DEFAULT_LOAD_FACTOR = 0.75f; Static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; static final int UNTREEIFY_THRESHOLD = 6; Static final int MIN_TREEIFY_CAPACITY = 64; static final int MIN_TREEIFY_CAPACITY = 64;Copy the code

In jdk1.8, the hashmap is optimized, the introduction of the red and black tree, in the list too long time, also is the threshold of 8, not on behalf of the length of the list, said the list length is greater than the 8 9 when turn red and black tree, and turn the red-black tree there is a condition, namely the array capacity greater than or equal to 64 will turn red and black tree, Otherwise, capacity expansion is preferred. Why is the threshold for list to red black tree 8?

(exp(-0.5) * pow(0.5, k)/factorial(k)).0:0.60653066 1: 0.30326533 2: 0.07581633 3: 0.01263606 4: 0.00157952 5: 0.00015795 6: 0.00001316 7: 0.00000094 8: 0.00000006 More: less than 1 in ten millionCopy the code

Poisson distribution, the probability of the chain reaching 8 is low, so it’s 8.

Put () method



The comparison shows that HASHMap is optimized for JDK1.8. Let’s look at the conditions for turning a red-black tree.



If the length of the array is less than 64, the array is expanded first. Java8 HashMap expansion skips Jdk7 expansion pit, optimized the source code, usingHigh and low split transfer modeTo avoid the generation of linked list rings.

final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab ! = null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) ! = null) { oldTab[j] = null; if (e.next == null) newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; If ((e.hash & oldCap) == 0) {// use the low pointer 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); if (loTail ! = null) { loTail.next = null; newTab[j] = loHead; // Move to the same index position on the new array} if (hiTail! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }Copy the code

The rehash operation is completely circumvented from the source code, but the array size must be a power of two to allow for high and low movement.

As shown in the figure:



Put method in jdk8