Categories
Uncategorized

JDK1.7 HashMap died in the ring in question and JDK1.8 source code optimized for the HashMap Detailed

A, JDK1.7 HashMap expansion in deadlock

We first look at JDK1.7 source in put method
    
    We open addEntry follows, it is determined whether the threshold array for the current capacity has been exceeded, for example, assumed that the current array capacity 16, load factor is 0.75, i.e. more than 12, and just to insert index all elements, this time the need for expansion of operations, you can see resize expansion is twice the size of the original array, the array is still in line with a length of 2 to the power index
    
    We then enter the resize follows, it will first array capacity before the judge to see if the array has reached the maximum capacity, and if not, will be behind the transfer operation of the array, namely transfer method
    
    Methods We first look at the transfer operation carried out, because there is deadlock in the JDK1.7 also focused on this HashMap
    Suppose we have such a HashMap, as follows
    
    Now it needs to be expansion of operations (assuming that the expansion has reached a threshold value, additional elements are ignored)

The source, in which case even a pointer is generated, e a pointer to the current node, another node is next, the next node point e, i.e. e.next, as shown in FIG.

if the judge in the source code implementation is re-hash, indexFor operation to achieve is to reposition the new location of the current node in the array, we look at new array
    
    Assuming that the array is positioned to No. 3

Then look at the source code e.next = newTable [i], No. 3 after an array of upcoming e.next node points to expansion, because this is a new array just created, or an empty array, so e.next = null, this time point as shown below
    
    Then the next step newTable [i] = e, the current new node just about to be found in the new array is assigned to e, as shown in FIG.
    
    The final step e = next, namely:
    
    Thus, first pass the while loop ends, at this time point e Yang Guo this node, it is clear that is not empty, the second cycle will repeat the above operation, the final effect is produced by:
    
    Yang Guo and Helen of Troy can position two nodes of the changed (and this is the reason why the HashMap disorder)

The above is a single-threaded down for expansion, and will not produce thread-safety issues, but if it is multi-threaded for expansion

We assume there are two threads of the expansion of the array, there are two pointers for each thread, and the thread 1 is e next, thread 2 and e2 next2
    
    When assuming that the following code to run the thread 2 thread blocked the red box, the corresponding figure is a point e2 Maid, pointing Yang Guo Next2
    
    2 because the thread is blocked, behind it can not continue execution of the code, but this time also the thread 1 into the expansion method, the result of the expansion is the result of expansion single thread, as shown above, this time with than before the expansion HashMap, Yang Guo and Helen of Troy location has been replaced

At this time, just the blocked thread is awakened 2. Note that the two pointers to the thread 2, as shown in FIG.
    
    At this time, the thread 2 executes e.next = newTable [i] of the line, i.e. the next node of its new array e2 point of expansion, as shown below:
    
    Then execute the following newTable [i] = e, the node soon Maid filled array, as follows
    
    Now points to the last step e = next, since at this time a thread is also directed to Yang Guo next2 node array 1 after expansion, and so now next2 e2 point node Yang Guo
    
    Then the second cycle, the results are as follows:
    
    Now for the third cycle, is still e.next = newTable [i] this line, this time newTable [i] is Yang Guo node, so the result of this step is the node Maid Yang Guo also pointed back to the node
    
    At this time we perform e = newTable [i], the following results:
    
    The final step after the implementation of two pointers are pointing to empty
    
    At this time, the new expansion array also form a ring
    
    These are the cause of a deadlock when the HashMap expansion

Two, JDK1.8 the optimization of the HashMap

JDK8 look at the source code in HashMap

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node[] tab; Node p; int n, i;
        // 容量为空时重新赋值
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 元素不存在,则直接插入数组即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node e; K k;
            // 原值已存在,直接替换
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 如果是 LinkedHashMap 实现的话,会使用红黑树作为数据结构,调用其 putTreeVal()
            else if (p instanceof TreeNode)
                e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 找到最后一个 next 不会 null 的位置,插入元素
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 如果树的深度大于阀值-1, 则重新调整,平衡二叉树
                        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;
                // LinkedHashMap 预留
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改+1
        ++modCount;
        // 容量超过阀值,扩容
        if (++size > threshold)
            resize();
        // LinkedHashMap 预留
        afterNodeInsertion(evict);
        return null;
    }

When the operation for expansion capacity exceeds the threshold value, we enter resize method, the following source

    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node[] resize() {
        Node[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        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[] newTab = (Node[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //这里定义了两组头和尾指针
                        Node loHead = null, loTail = null;
                        Node hiHead = null, hiTail = null;
                        Node next;
                        do {
                            next = e.next;
                            //使用当前结点的hash值与就数组的长度做与运算,如果是0则是低位
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {//如果是16则是高位
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

It can be seen that when migrating array, defined here two pointers, respectively, and the lower end of the head, the head and tail high, for example can be seen why to do, assuming that the length of the old array 16

数组长度       0000 0000 0000 1000
hash值        0101 1011 1111 1011 (随机)
与运算结果只有两种
              0000 0000 0000 1000 ---------16
              0000 0000 0000 0000 ---------0

Calculation results and the presence of only 0 16 two possible, then the following source code to see if it is 0 is low, and if it is high 16
    
    Results here assumed operation is 0, then this becomes a pointer to the array:
    
    Then execute the code below, the low head loHead assigned to the new array, we can see that in front of the old j to iterate the array index, so that all nodes will be high are moved to a new array

Next, newTable [j] = loHead blanking the upper tail, and then into the head of the high index j + oldCap new array (index current + the length of the old array), for example, the index is now 3, plus the length of the array 16, the last is the high index into an array of new places to 19, so that became the location map below:
    
    This, the end of the transfer, to avoid the problem JDK1.7 dead ring using two pointers that may arise

Summary: After JDK1.8, an array of methods to migrate after the expansion of the underlying HashMap has been optimized. To a list divided into two groups, divided into high and low, respectively, to migrate, to avoid the death ring problem. And in the process of migration and did not make any rehash (re-record count hash), improving performance. It is directly linked list to be broken, for almost an equal split, then by pointing to the head pointer will migrate over the whole, thus reducing the length of the list.

Leave a Reply