编程知识 cdmana.com

Let's see the HashMap that you must ask for. Once you can get the HashMap source code completely done

HashMap structure

Array + Linked list + Red and black trees
Linked list greater than 8 Turn the red and black tree , The number of nodes in the red and black tree is less than 6 Return list .

Deposited key-value Of Node node

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

Tree shaped Node node

 static 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
        boolean red;
 }

His inheritance structure is like this , You can see the inheritance Node node

Understand a sentence

 hash & tab.length-1

You can see this code in many places in the code , In fact, this sentence only makes a remainder (%) The action of . One & How to do the residual operation :
HashMap The capacity of is 2^n Its binary structure is as follows

Any number &2^n-1(01111…) The result is 0xxxx, We have done the operation of quick surplus . Later, you will see that the statement appears frequently

Several core parameters

  • Node<K,V>[] table: Deposit Node Array of
  • int size: At present HashMap Number of key value pairs contained
  • int threshold: At present HashMap The maximum number of key value pairs that can withstand , Once that number is exceeded HashMap It's going to expand
  • final float loadFactor: Load factor , For expansion
  • int DEFAULT_INITIAL_CAPACITY = 16: default table Initial capacity
  • float DEFAULT_LOAD_FACTOR = 0.75f: Default load factor
  • int TREEIFY_THRESHOLD = 8: If the length of linked list is greater than this parameter, it will be converted to red black tree
  • int UNTREEIFY_THRESHOLD = 6: When the number of nodes in the tree is less than or equal to this parameter, it is converted into a linked list

Initialization method

Specified specific capacity , And the initialization method of load factor . When you know the number of elements that need to be put in, you can specify it first to avoid performance waste caused by multiple expansion .

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

The core approach public V get(Object key)

Parameters key, And it's time to key Of hash
First determine whether the array has been initialized , And the array length .
In judging tab[(n - 1) & hash], The sentence mentioned above , use key Of hash Take the length of the remainder array to determine whether there are elements in the position of the array .

  • There is no element
    There is no element in the array , There must have been no hash Conflict , Then the element must not exist
  • There are elements in the current position of the array
    Judge key Of hsah Equal and (key The address is equal to or equals equal ). Then you can make sure that the elements are in the array .
  • There are elements in the current position of the array , however key It's not equal
    The next step is to determine whether the current position in the array exists next Elements (Node The node structure ), If there is next Indicates that there is a linked list or tree structure .
    Then judge Node Whether it is TreeNode, If so, the result is obtained by traversing the tree , If not, the result is obtained by traversing the linked list .
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab = table; 
        Node<K,V> first = tab[(n - 1) & hash]; 
        Node<K,V> e = first.next; 
        int n = tab.length; 
        K k;
        // Whether the array has been initialized 
        if (tab!= null && n > 0 && first != null) {
            //table Whether there are nodes in ,key Whether it is equal or not 
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //key It's not equal , To determine if there is next, And determine whether it is the node of the tree or the node of the linked list , And then traverse in different ways to get 
            if (e != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

The core approach public V put(K key, V value)

put The method is longer , Analyze in several cases

  • for the first time put Elements , Array is not initialized yet : call resize() Initialize array , Put it directly in table Corresponding position .(resize The expansion method is very important )
  • table This position does not produce Hash Conflict : Construct nodes into table in
  • produce Hash Conflict , First judge table Middle node element key Whether it is equal or not , If equal, replace value
  • produce Hash Conflict , Node is TreeNode: Insert nodes in the way of a red black tree
  • produce Hash Conflict , Node is Node: Construction nodes are inserted in the form of a linked list , And check whether it reaches the threshold of turning to red black tree after inserting 8
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K,V>[] tab; 
        Node<K,V> p; 
        int n;
        int i;
        // for the first time put Elements , Array is not initialized yet 
        if ((tab = table) == null || (n = tab.length) == 0)
            // call resize() Initialize array 
            n = (tab = resize()).length;
         //table This position does not produce Hash Conflict 
        if ((p = tab[i = (n - 1) & hash]) == null)
            // Construct nodes into table in 
            tab[i] = newNode(hash, key, value, null);
        else {
            // produce Hash Conflict 
            Node<K,V> e; K k;
            //table Middle node element key Whether it is equal or not 
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
                // Record the node references , Follow up replacement E The value of the node 
                e = p;
            else if (p instanceof TreeNode)
                // Node is TreeNode: Insert nodes in the way of a red black tree 
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // Node is Node, List situation 
                for (int binCount = 0; ; ++binCount) {
                    // Traversing to the end of the list has not found the same key, Then the construction node is inserted into the linked list 
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            // Check whether the threshold value of turning to red black tree is reached after insertion 8
                            treeifyBin(tab, hash);
                        break;
                    }
                    // Check if there is the same key, Quit if you have one ,e = p.next It has been recorded E References to 
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // In each of these cases , If it's not an insertion node 
            // There is key In the same case , Complete the replacement of a value 
            if (e != null) {
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                return oldValue;
            }
        }
        // Check whether expansion is needed   Number of existing >hashmap Capacity * The load factor needs to be expanded 
        if (++size > threshold)
            resize();
        return null;
    }

The core approach Node<K,V>[] resize()

The most important part is coming , It's also the interviewer's favorite question HashMap Expansion of

  1. Called the first time it is initialized
  2. Number of key value pairs stored >hashmap Capacity * The load factor needs to be expanded

Call... At initialization time resize

After expansion, we get a Node Array . Because of the first initialization , There must be no linked list , Red and black trees , as well as Node Node . It's just assigning values to some properties , And return an empty Node Array .
threshold:HashMap The maximum number of key value pairs that can withstand ; If capacity and load factor are specified , be threshold = Specified capacity * Load factor ;
Node<K,V>[] table: Deposit Node Array of , Created a capacity for 16( When no specific capacity is specified , The default is 16) Of Node Array .

Omit parts of code that are irrelevant to the first initialization, unimportant code

final HashMap.Node<K,V>[] resize() {
        //16*0.75=12
        threshold = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        //16
        HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[DEFAULT_INITIAL_CAPACITY];
        table = newTab;
        return newTab;
    }

Expand call resize The key is coming.

First delete some code that has nothing to do with the expansion

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) {
            // The capacity and threshold are doubled 
            newCap = oldCap << 1;
            newThr = oldThr << 1;
        }
        // Set threshold properties 
        threshold = newThr;
        // The new one is twice the size of the previous one Node Array 
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        // Attribute assignment 
        table = newTab;
        // Finish some preparation , Start preparing for migration before nodes 
        if (oldTab != null) {
            // Cycle migration of each node data 
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                // Not every position in an array has elements 
                if ((e = oldTab[j]) != null) {
                    // Data needs to be migrated ,table The corresponding position is empty 
                    oldTab[j] = null;
                    // There is no linked list 
                    if (e.next == null)
                        // Fast recovery of new capacity , Put it in the right place 
                        newTab[e.hash & (newCap - 1)] = e;
                    // Tree structure ( More complex, follow-up analysis )
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    // Chain table structure 
                    else {
                        // Do not need to move the head and end of the list pointer 
                        Node<K,V> loHead = null, loTail = null;
                        // The head and tail pointer of the linked list that needs to be moved 
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        // Traversing the linked list will split a list into two linked lists , Here we mainly analyze the basis of splitting 
                        do {
                            next = e.next;
                            // The remainder after expansion is the same as before , Nodes that don't need to move .
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            } else {
                                // The remainder after expansion is inconsistent with the previous one , Nodes that need to be moved .
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // Put the list back in table Array 
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

Here we mainly analyze the basis of the split .
When you want to split the data in the linked list , And assigned to different table In the subscript . What is clear is that , The expansion should not affect get Method , So according to get Method key Of hash Take the remaining capacity to get the following two pictures .
Before dismantling

After dismantling

Read a line of code in the expansion

(e.hash & oldCap) == 0

When the element of hash &oldCap( As mentioned above, the capacity is 2^n, Its binary is 1000…).
Take a few examples
5&16 ==0

21&16 !=0

69&16 ==0

Hash Values are structured around the red box : Can be seen as On the left Y+table Capacity + On the right X,Y It's an even multiple of capacity ,X Less than the capacity value , From the above example, we can see whether the result is 0 Depending on where the red box is 0 still 1.

  • by 0 The result is always 0
    Y Is an even multiple of the capacity. After expansion, the remainder remains unchanged 0, Remainder is X, The remainder is the same as before , No need to move .
  • by 1 The result is not 0
    Y Is an even multiple of the capacity. After expansion, the remainder remains unchanged 0, The remainder is the capacity value +X, The remainder after expansion is inconsistent with the previous one , Need to move , The position after moving is the capacity +X( The value of the previous position ).

Last

Welcome to the official account : Bright future , Receive the first tier factory Java Interview question summary + Learning and thinking guidance of each knowledge point + One copy 300 page pdf Document Java Summary of core knowledge points !

版权声明
本文为[Bright future]所创,转载请带上原文链接,感谢

Scroll to Top