First, we know that the underlying implementation of HashMap is the open address + chained address method.

That is, array + linked list implementation, by calculating the hash value, find the corresponding position of the array, if there is already an element, add to the list of this position. After Java 8, long lists can also be converted to red-black trees.

The array does not start out large, but expands as the number of values in the HashMap increases, reaching the LoadFactor threshold. You start out with a small array, 16 by default.

The size of the array must be 2 to the NTH power, because to find the corresponding position in the array you need to do the mod, and the mod of 2 to the NTH power is the sum of 2 to the NTH power minus. So keep the size of the array 2 to the n, so that you can compute places efficiently.

So how does this hash work? So let’s say we just hash the Key directly. Suppose we have two keys with hash values as follows:

key1:

0000 0000 0010 1111 1001 0000 0110 1101
Copy the code

key2:

0000 0000 0010 0000 1001 0000 0110 1101
Copy the code

If you just use the default size of the array, mod key1 and key2 will be at the same index as the array. Key1 and KEY2 have different high values.

Since the array is from small to enlarged, in order to optimize the problem that the high is ignored, the source code of HashMap has optimized the calculation of hash value, using the hash value generated by xor of the high 16-bit number and the source hash value as the hash value used to calculate the array position of HashMap:

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

Why xOR? First, for a number, when converted to binary, the position of 1 represents the properties of the number. For xOR, if a and b have different values, the xOR result is 1. If a and B have the same value, the xOR result is 0. 0 and 0 are different or 0, 0 and 1 are different or 1, which is equivalent to let the characteristics of the high can be reflected in the low, so this algorithm is adopted to reduce collisions.

Wechat search “my programming meow” public account, a daily brush, easy to improve skills, won a variety of offers