1. Proposed several problems of HashMap

Read JDK8 source code small torch certainly in the first read after there will be a doubt, the main question in the following several problems:

2. Why hashCode()?

    static final int hash(Object key) {
        int h;
        return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
    }
Copy the code

2.1 Time of deposit

Once you get the hash, you can directly locate the index in the array with a simple bit operation. O(1) is the fastest way to store the index of an array (if there is a hash conflict, then call equals()).

if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
Copy the code

2.2 Fetching time

(first = tab[(n - 1) & hash]) ! =null) {
Copy the code

2.3 hashCode ()

Using hashCode() is the fastest way to access both sides of the plane. No one, if you use the way of traversing the number group to find, the day lily is cold, O(n) brother.

3. Why is the initial capacity 16? Or why, given an initial capacity size in the constructor, does it still modify it to be greater than or equal to the lowest power of two to the NTH?

tab[i = (n - 1) & hash]
Copy the code

i = (n - 1) & hash
Copy the code

3.1 In order not to let the subscript out of bounds

When capacity = n to the power of 2, this is the case for n-1 binary. Let’s look at binary: n= 1000… // start with 1 followed by n zeros. The n – 1 = 0111… // Start with 0 and end with 1

(n-1) & hash :& means and. If both values are 1, the result of the ampersand operation can never be greater than the value of (n-1), i.e., never greater than or equal to capacity. The maximum index is Capacity-1.

3.2 To distribute hash evenly

4. TableSizeFor () method parsing

Source:

    /** * Returns a power of two size for the given target capacity. */
    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;
    }
Copy the code

Is greater than or equal to cap to the NTH power of 2:

• First, why cap-1:

int n = cap - 1;
Copy the code

The purpose of reassigning cap-1 to n is to find a target value greater than or equal to the original value. For example, the value is 1000 in binary and 8 in decimal. If you don’t subtract 1 from it, you get the answer 10000, which is 16. Obviously not the result. If you subtract 1 from the binary to 111, you get the original value of 1000, or 8. To reanalyze the highlight, here are the lines:

n |= n >>> 1; Said: n = (n | n > > > 1) | or: corresponding for as long as there are several 1Copy the code

• Analysis begins: hypothesis

1. The binary value of n is 01XXXXXXXXxxxxxx…
2. Move right one bit: 001XXXXXXXXXXXXXX…
3. And n or the value of n: 011XXXXXXXXXXxxxx…
4. By the same token, the n | = n > > > 2. After the row of n = 01111 XXXXXXXXXXXXXXXXXXXXXXXXXXXX
5. By the same token, the n | = n > > > 4. After the row XXXXXXXXXXXXXXXXXXXXXXXX n = 011111111
6. By the same token, the n | = n > > > 8; After the row of n = 01111111111111111 XXXXXXXXXXXXXXXX
7. By the same token, the n | = n > > > 16; After the row of n = 011111111111111111111111111111111
8. If you’re familiar with this, the return is incremented by 1, and you’re back to 100000… , followed by all zeros, that is, this method returns 2 to the NTH power.

4 times 31

public int hashCode(a) {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }
Copy the code