The source code to read

  • The HashMap source code has six important attributes

    • Initialize length 16:static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
    • The maximum length is 1073741824:static final int MAXIMUM_CAPACITY = 1 << 30;
    • The default load factor is 0.75:Static final float DEFAULT_LOAD_FACTOR = 0.75f;
    • Conditions for expanding a red-black tree (whenThe list is longer than 8And the capacity is greater than 64) :static final int TREEIFY_THRESHOLD = 8;
    • Conditions for expanding a red-black tree (whenThe element is less than 6) :static final int UNTREEIFY_THRESHOLD = 6;
    • Minimum tree capacity:static final int MIN_TREEIFY_CAPACITY =

  • Query: If Hash Hash conflicts, check whether key values are equal

    public V get(Object key) {
    Node<K,V> e;
    // Hash the key
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // Non-null judgment
    if((tab = table) ! =null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) ! =null) {
        // Determine if the first element is the element to be queried
        if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
            return first;
        // The next node is not null
        if((e = first.next) ! =null) {
            // If the first node is a tree, use getTreeNode to get the corresponding data directly
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do { // Non-tree structure, loop node judgment
                // If the hash is equal and the key is the same, this node is returned
                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

  • new

    public V put(K key, V value) {
    // Hash the key
    return putVal(hash(key), key, value, false.true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // Create table if the hash table is empty
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // Calculate the index I of the array to be inserted based on the hash of the key
    if ((p = tab[i = (n - 1) & hash]) == null)
        If table[I] = null, insert directly
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // Override value if key already exists
        if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
            e = p;
        // If the key does not exist, determine whether it is a red-black tree
        else if (p instanceof TreeNode)
            // The red-black tree inserts key-value pairs directly
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // For the linked list structure, loop ready for insertion
            for (int binCount = 0; ; ++binCount) {
                // When the next element is empty
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Convert the list to a red-black tree for processing
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // Key already overwrites value
                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 the capacity exceeds the maximum, expand the capacity
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

  • capacity

    final Node<K,V>[] resize() {
    // Array before expansion
    Node<K,V>[] oldTab = table;
    // The size and threshold of the array before expansion
    int oldCap = (oldTab == null)?0 : oldTab.length;
    int oldThr = threshold;
    // Pre-define the size and threshold of the new array
    int newCap, newThr = 0;
    if (oldCap > 0) {
        // If the maximum value is exceeded, the expansion is no longer performed
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // Expand the capacity to double the current capacity, but not more than MAXIMUM_CAPACITY
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // The current array has no data, use the initialized value
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        // If the initialization value is 0, the default initialization capacity is used
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // If the new capacity equals 0
    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];
    // Start capacity expansion and assign the new capacity to the table
    table = newTab;
    // Copy the original data to the new table if the original data is not empty
    if(oldTab ! =null) {
        // Loop through the array by capacity, copying non-empty elements to the new table
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if((e = oldTab[j]) ! =null) {
                oldTab[j] = null;
                // If there is only one list, direct assignment is performed
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // Operations related to red-black trees
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    // Linked list copy, JDK 1.8 expansion optimization part
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        / / the original indexes
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // The original index + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            elsehiTail.next = e; hiTail = e; }}while((e = next) ! =null);
                    // Put the original index into the hash bucket
                    if(loTail ! =null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // Put the old index + oldCap into the hash bucket
                    if(hiTail ! =null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}
Copy the code

    • For expansion, JDK1.7 recalculates the hash value of each element, while JDK1.8 recalculates the hash value of each element directly through the high order operation (e.hash & oldCap) to determine whether the element is moved or not. Key1 has the following information:

      • key1.hash = 10 0000 1010
      • oldCap = 16 0001 0000

      The result of e.ash & oldCap is 0. When the result is 0, the position of the element will not change during expansion. The key 2 information is as follows:

      • key2.hash = 10 0001 0001
      • oldCap = 16 0001 0000

      When the result is 1, it indicates that the position of the element has changed during expansion. The new subscript position is equal to the original subscript position + the original array length

  • A HashMap infinite loop

    In JDK1.7, assuming that the default size of the HashMap is 2 and that the original HashMap has a key(5), we use two threads: T1 adds element key(3) and T2 adds element key(7). After both elements key(3) and key(7) are added to the HashMap, thread T1 executes Entry

    next = e.ext; The CPU usage is surrendered
    ,v>

    void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null! = e) { Entry<K,V> next = e.next;// Thread one to execute here
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            inti = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }}}Copy the code

    So e in t1 points to key(3), and next points to key(7); After t2 rehashes, the order of the list is reversed, and the position of the list becomes key(5) → key(7) → key(3).

    When t1 regains the right to execute, first run newTalbe[I] = e to set next to key(7), and then run next to key(7), and then run next to key(3). This creates circular references to key(3) and key(7), thus causing an infinite loop to occur

    The reason for this infinite loop is that JDK 1.7 inserts lists in reverse order at the beginning. In JDK 1.8, this problem is changed to positive order at the end

    Note: HashMap is not thread safe. In multithreading, use ConcurrentHashMap

The interview questions

1. What is the underlying implementation of HashMap? What optimizations have been made in JDK 1.8

In JDK1.7, a HashMap is in the form of an array ➕ linked list

After JDK1.8, the red-black tree structure was added. When the length of the list is greater than 8 and the capacity is greater than 64, the list structure will be converted to the red-black tree structure

The reason for adding red-black trees is that if the list is too long, the performance of HashMap will be seriously affected, and red-black trees are quick to add, delete, and check

2. Why is the loading factor 0.75?

The load factor, also known as the expansion factor, is used to determine when to expand. In the source code, the load factor is 0.75, so if the initial length is 16, the HashMap will expand if there are 16*0.75=12 elements in the HashMap

Why is the loading factor 0.75? , mainly for capacity versus performance considerations

  • If the load factor is set to a small value, the threshold for capacity expansion is lowered, and more space is occupied. In this case, the storage of elements is sparse, and Hash conflicts are less likely to occur. Therefore, the operation performance is higher
  • If the load factor is set to a large value, the threshold for capacity expansion is increased, the capacity expansion occurs at a low frequency, and the space occupied is small. However, the probability of Hash conflicts is increased. Therefore, more complex data results are required to store elements, which increases the operation time on elements and reduces the operation efficiency
  • The capacity of a HashMap has a fixed requirement that it must be a power of two, so when the load factor is 0.75,Capacity * 0.75The product of is an integer

Therefore, considering comprehensively, 0.75 is selected as the loading factor