1. HashMap data structure

The jdK8 data structure is array + linked list

Jdk8 and later data structures are arrays + linked lists + red-black trees

Avoid using HashMap in a concurrent environment because it is possible to create a looped linked list when capacity expansion occurs, which can cause 100% CPU problems when performing get

2. Why does HashMap choose array + linked list + red-black tree data structure

  • Array: the storage and retrieval efficiency is the highest, time complexity isO(1)
  • Linked list: To solve the hash collision problem, the search operation needs to traverse all data in the linked list, and the time complexity isO(n)
  • Red-black tree: optimizes the performance of linked lists. The time complexity of operations such as search, insert, and delete isO(logN)

3. Why not use a red-black tree instead of switching to a red-black tree after the chain expression reaches a specified length?

If the number of elements is small, the efficiency of red-black tree is not as good as that of linked list, and the balance of red-black tree is broken, and spin (left and right) is needed to maintain the self-balance of the tree

4, linked list to red black tree threshold is the origin and linked list to red black tree conditions

Origin of the threshold: The threshold for converting a linked list to a red-black tree is calculated by the probability of the poisson distribution (probability statistics) appearing a list of (1 element, 2 elements, 3 elements)

Conversion condition: The conversion is performed only when the array length is greater than or equal to 64 and the list length of an array element is greater than or equal to 9

5. Why is it possible to convert an array to a red-black tree if the array length reaches 64?

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // Todo arrays with a length less than 64 will not be converted to a red-black tree
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) ! =null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while((e = e.next) ! =null);
        if((tab[index] = hd) ! =null) hd.treeify(tab); }}Copy the code

6. Why is the threshold for list to red black tree 9 instead of 8?

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    //todo initializes the size
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Todo hashes to determine if the array element has a value
    if ((p = tab[i = (n - 1) & hash]) == null)
        // Todo does not insert elements directly
        tab[i] = newNode(hash, key, value, null);
    else {
        //todo note that there is already one element in the array element corresponding to the hash value
        Node<K,V> e; K k;
        //todo checks whether the key exists and overwrites the old value
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        //todo determines whether it is a red-black tree
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        //todo enters the list logic
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    //todo creates a Node
                    p.next = newNode(hash, key, value, null);
                    // If the list length is greater than or equal to 7, loop 8 times to create 8 nodes, plus the existing node, the list length is 9 before the red-black tree conversion
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                    break; p = e; }}if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

7. Why does HashMap recommend an array with a power of 2

Capacity initialization: The incoming capacity is not an exponential power of 2 and is converted to the nearest exponential power of 2 greater than that number

In order to improve efficiency, the efficiency of hashcode%length modulus is low, and the efficiency of bit operation hashcode&(leng-1) is high. Jdk1.7 array expansion will generate a large number of Rehashes

8. Why is the load factor 0.75?

To solve the hash collision problem

  • If the load factor is greater than or equal to1, the collision probability is higher, the linked list length is longer, the search time complexity is higher (time space)
  • If the load factor is less than or equal to0.5, fast query (space for time), low hash collision

The value 0.75 is based on Newton binomial overthrown out, in time and space for compromise processing