I What do you know?

HashMap, TreeMap, ConcurrentHashMap, LinkedHashMap

II What are the characteristics of HashMap?

1. Null Key and Value are allowed, but only one record Key can be null

2. Thread unsafe

3. disorder

4. The data structure is array + linked list / red black tree (JDK1.8)

III JDK1. Why does HashMap in 8 introduce red black tree?

Linked list query time complexity O(n), insertion time complexity O(1)

The time complexity of red black tree query and insertion is O(lgn)

IV Why can HashMap length only be a multiple of 2

1. When calculating Hash value, bit operation is used instead of modulus, which can calculate the position of elements more efficiently.

The index corresponding to the element is assigned by the following code, that is, index = hash & HashMap table length - 1

if ((p = tab[i = (n - 1) & hash]) == null)

1. During capacity expansion, the index of the key can be calculated faster to improve the capacity expansion efficiency

2. For example, if the map size is 16, the index where the key is 2 is 2, and the index where the key is 18 is also 2

3. However, after the capacity expansion, it becomes 32. The index where the key is 2 is still 2, and the index where the key is 18 becomes · 2 + 16 = 18.

Here 4ye we have directly intercepted the recalculation index of the linked list in resize, and there is similar code in the red black tree TreeNode

V When will HashMap be expanded

When the value of (hash table size), > (hash table size * load factor) is, the capacity is expanded

Vi Size of load factor

The size of the load factor determines the capacity expansion and hash conflict of the hash table. It should be checked after each put * * new element * *, java training See if you need to expand the capacity. The expansion is twice the original by default.

Increasing the load factor will increase the probability of hash conflict, also increase the time-consuming, and the capacity expansion itself will also take time.

VII How to calculate hash value

Calculate the hashCode value of the key, and then XOR this value with its upper sixteen bits

This is done to reduce hash conflicts

//      >>>Shift the unsigned bit to the right, that is, regardless of the positive or negative of the number, fill 0 in the high position / / > > means shift to the right. If the number is positive, fill 0 in the high position. If it is negative, fill 1 in the high position / / < < shift left, fill 0 in the low position directly without positive or negative

Under verification~

int hashCode = "Java4ye".hashCode();System.out.println((hashCode ^ (hashCode >>> 16))&15);// Print out 0hashmap put("Java4ye","1")

VIII Solutions to hash conflicts

1. Open addressing

2. Chain address method (zipper method) is adopted by HashMap

3. double hashing

4. Public spillover area method

IX Implementation of put and get

put time

First calculate the hash value of the key and the index of the bucket where it is located. If there is no collision, it will be directly put into the array.

If there is a collision, first judge whether the key is the same key. If so, directly overwrite it.

If not, judge whether it is a linked list or a red black tree, and insert it according to different situations. If the key is the same, it will be replaced or the original value will be retained according to the value of onlyIfAbsent or whether the original value is null.

If the corresponding key is found, the old value will be returned and the execution will not continue

If a new element is added, the size of the hash table will be judged finally. If the value is greater than the size of the hash table * load factor, the capacity will be expanded; Finally, null is returned

put source code:

/** * Implements Map.put and related methods * * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    // When creating a Hashmap, the capacity of the bucket is not initialized. The capacity is expanded only during the put operation if ((tab = table) = = null | (n = tab. Length) = = 0) n = (tab = resize()) length;    //  Here, check whether the corresponding index has data. If not, put it directly here. If ((P = tab [i = (n - 1) & hash]) = = null) tab [i] = newnode (hash, key, value, null)// If there is data, go to the following to judge. First judge whether it is the same key, and then judge which data structure it belongs to, Red black tree or linked list else {node < K, V > e; K, K; / / judge whether it is the same key if (p.hash = = hash & & ((k = p.key) = = key | (key! = null & & key. Equals (k))) e = p; / / judge whether it is red black tree else if (P instanceof treenode) e = ((treenode < K, V >) P). Puttreeval (this, tab, hash, key, value);         Else {/ / in the linked list, the tail insertion method is used here! Find the key in the linked list, break if any, and keep looking until the last element in the linked list, and add the tail of the linked list for (int bincount = 0; + + bincount) {if ((E = p.next) = = null) {p.next = newnode (hash, key, value, null) ;                    //  If the threshold 8 is exceeded, it will be transformed into a red black tree if (bincount > = tree_threshold - 1) / / - 1 for 1st treeifybin (tab, hash); break;                }                //  Judge whether it is the same key. If yes, skip if (e.hash = = hash & & ((k = e.key) = = key | (key! = null & & key. Equals (k))) break; p = e;            }        }        //  A value of e indicates that the current key has a corresponding value. If the value of onlyifabsent is false or the current value is null, overwrite it, and then return the old value. if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    //  If the put is a new element, you will go to this step and + 1 to judge whether you need to expand + + modcount; if (++size > threshold)        resize();     afterNodeInsertion(evict);     return null;}

When get ting, you must first calculate the hash value of the key, then calculate its index, and then judge whether there is a hash conflict. If there is no conflict, it will be returned directly. If there is a conflict, you need to judge whether the current data structure is a linked list or a red black tree, and then take the value from the corresponding structure respectively

This picture is from meituan technical team~

X How to judge whether an element is the same

First judge whether their hash values are the same. If they are the same, then judge whether the equals method | = = method of the key is the same. If they are the same, they are the same element

Xi Under what circumstances will red and black trees be used?

You can refer to the above put source code. The main code is shown in the figure:

You can see that when the size of the array is greater than 64 and the length of the linked list is greater than 8, the linked list will be converted into a red black tree.

When the size of the red black tree is less than or equal to 6, it will be converted into a linked list. Refer to the resize source code

XII Head and tail interpolation

Because jdk1 In 7, HashMap uses header interpolation, so new elements will always be placed at the head of the linked list.

For example, the HashMap size is 4, and the index of key 2, 6 and 10 is 2

Then when it expands, the order will become

index: 2，key: 10 ，2

index: 6，key: 6

In a multithreaded environment, it may cause an endless loop~

For example, thread a still stays at 2 next 6，6.next 10, thread b has finished resizing and becomes 10 Next2 will then enter an endless cycle.

This is one of the reasons why HashMap threads are unsafe.

The same example: tail interpolation does not lead to dead cycles

For example, thread a still stays at 2 next 6，6.next 10, thread b has finished resizing and becomes 2 Next10.

Using tail interpolation does not mean that HashMap is thread safe, because you can't guarantee the value put in, and the value get out or put in, because it may have been modified by other threads.