To review the previous article, we introduced the PUT related functions. You learned how to put a HashMap, when to expand, and when to turn a list into a red-black tree. The HashMap GET functions and common interview questions will be covered next.

Get related functions

    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    /**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if((tab = table) ! =null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) ! =null) {/ / comment 1
            if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))/ / comment 2
                return first;
            if((e = first.next) ! =null) {
                if (first instanceof TreeNode)/ / comment 3
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {/ / comment 4
                    if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
                        return e;
                } while((e = e.next) ! =null); }}return null;
    }
Copy the code

GetNode (int Hash, Object key) the main logic of get(Object key) is in getNode(int hash, Object key), which is relatively simple.

  1. TAB [(n-1) & hash]) is null
  2. Note 2: Check if first is the node we are looking for, return if it is, otherwise continue
  3. Note 3: If first is a red-black tree, call getTreeNode(hash, key), otherwise continue
  4. Note 4: Iterate through the list looking for nodes we need and return if found
  5. Return null for all of the above

Common interview questions

  1. The data structure of HashMap? Hash table structure (hash list: array + linked list) implementation, combining the advantages of array and linked list. When the list length exceeds 8, the list is converted to a red-black tree.

  2. What is the underlying principle behind HashMap? Based on the principle of hashing, JDK8 uses array + linked list + red-black tree data structure. We use put and GET to store and get objects. When we pass the key and value to the put() method, we first do a hashCode() calculation of the key to get its position in the bucket array to store the Entry object. When an object is fetched, the bucket location is retrieved by get, the correct key-value pair is found through the equals() method of the key object, and the value object is returned.

  3. A HashMap calculates the first power of 2 greater than that number using unsigned right shifts and bitwise or operations, based on the initialized capacity passed in by the user. When length is 2 to the n power, h&(Length-1) is equivalent to modulo length, and is much faster in speed and efficiency than directly modulo Length.

  4. Handling hash collisions (left to the reader)

  5. HashMap capacity expansion mechanism

  6. Difference between HashMap and Hashtable