jdk8 HashMap extends a clever piece of code about a chain table

First look at the code

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) {
            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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                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;
    }

Focus on the link list section

 else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                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;
                        }
                    }
                }

There's a piece of code If ((e.hash & oldCap) === 0) I believe that many people see this as a bit of a fool
Now let's examine it:
First, the hash value is fixed for the same key, whether before or after expansion, we get or put the position using hash & (n-1). To make full use of the capacity of the entire array, the value binary value of n-1 must be *1111111, that is, 2^n-1.
Then the capacity of the array must be 2^n.OK, for data on a list of chains, after expansion, we recalculate the location hash & (newCap-1), the hash value is unchanged, newCap is twice oldCap because the expansion capacity is doubled as the array.Converting to binary is one more 1, and one more 1 is another case.
For example, suppose hash equals 0011 1101, oldCap-1=0000 11111, newCap-1=0001 1111 after expansion
hash&(oldCap-1)=0000 1101 hash&(newCap-1)=0001 1101 If the hash value is equal to 0010 1101, the expanded values are the same as those obtained after expansion.
So for data on a chain table, when doubled, it is either in its new location or in its original location plus the size of the old array.As long as the hash value added after expansion is 0 or 1, the best way to distinguish between the two cases is &2^n, which happens to be oldCap, not e.hash &(oldCap)

hashMap calculates capacity from a number

Source code

  static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

Assuming the value passed is 9, corresponding to binary 0000 1001
int n = cap-1 n=8 0000 1000
n|=n>>>1 n=12 0000 1100
n=|n>>>2 n=15 0000 1111
n=|n>>>4 n=15 0000 1111
n=|n>>>8 n=15 0000 1111
n=|n>>>16 n=15 0000 1111
The final n=16.
So to find the first 2^n whose number is larger or equal than it is to convert this data to binary first, then all the low 0's of the high 1 to 1, and then add this number + 1, which is the final 2^n square.
Once you know your goal, how do you change 0 to 1?Move the highest bit 1 one to the right, and then do or operate with the original number so that there are 2 1 of the highest bits, 4 1 of the next two bits to the right, 8 1 of the next 4 bits to the right, 16 1 of the next 8 1 to the right, 321 of the next 16 bits to the right, and 32 of the int s to the end.

Posted on Sat, 21 Mar 2020 21:10:47 -0700 by Ayien