HashMap, as the most commonly used data structure for programmers, contains many ingenious ideas of the designer. After reading the source code, people call me how I didn’t think of it.

1. Is there a data structure that can be added, deleted, modified and checked quickly?

We all know that array queries are faster because the addresses are contiguous and you can find the elements directly by the subscript. But adding and deleting is slow, and every time you add or delete an element in the middle of the array, you’re copying the array. The clever thing about HashMap design is that it uses hashCode instead of array index access. It no longer requires that the elements be stored continuously, so you do not need to copy the array when adding or deleting elements. The linked list is used to resolve hash conflicts. The default threshold is 75% to control the capacity. This prevents excessive elements and hash conflicts from degrading into linked list storage and affecting query performance. HashMap in general, the efficiency of adding, deleting, modifying, and checking is order one.

2. What if I quickly find the HashMap array index?

In computer, the performance of and operation is higher than that of remainder. HashMap directly uses hashCode logic and (length-1) to get array subscripts.

static int indexFor(int h, int length) {
    return h & (length-1);
}
Copy the code

To test, the hashCode is 10 (1010 for the second order) and 17 (100001 for the second order), the length of the HashMap is 16, and the binary of (length-1) is 1111.

3. How to compute the smallest power of 2 greater than the current value?

If the initial capacity of HashMap is 10, since HashMap requires that the capacity be a power of 2, how do we compute the smallest power of 2 that is greater than 10, 16?

// number is the initial capacity of 10, calculate capacity=16
int capacity = highestOneBit((number - 1) < <1);

public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}
Copy the code

At first look at this section of source code is not meng, diagram is clear.

>> indicates a binary right shift. >> 1 indicates a binary right shift. >> 2 indicates a binary right shiftCopy the code

Number = 10, first calculate I = (number 1) < < 1 number 1 = 9, 9 binary is 1001, left a into a 0001, 0010, and then execute highestOneBit () method Finally the result should be 16, As is shown in

i - (i >>> 1)