If you want to get a high-paying job, and jdK1.8 is now popular in the market, I believe that more and more interview process will ask the source code knowledge. All the source code is we have to understand, next we will come together to learn hashMap1.8 source code before the assumption of the problem to think about the problem
- What is the initial size of the hashMap
- What does a hashMap structure look like
3. If we already know that the data structure of hashMap is linked list addend, how can we avoid hash collisions
- When will hashMap be expanded
5. What is the way to expand the structure of the official chapter hashMap 1? In 1.8, the structure of hashMap is divided into addend group of linked list and array + red-black tree. Because the author of 1.8 considers that the linked list has no index and the traversal efficiency is low, when the length of the linked list is greater than 8-1, that is, 7, it will be converted into red-black tree. Then, when the length is less than 6, A transient Node
[] table; Node is a single list object, so the structure is array + list
[Java] Plain text view copy code? 1 2 static final int TREEIFY_THRESHOLD = 8; Static final int UNTREEIFY_THRESHOLD = 6; Non-tree critical points
1. Now that we know the structure of a hashMap, let’s look at how we can place hash collisions. We can imagine that we can make it modulo the length of the array, for example, if the array is 16, we can use the hash value of key to modulo the array. The values from 0 to 15 are good enough to fall on the array, but this way does not guarantee that the numbers will be scattered across the array as much as possible. Too many elements on the same node will result in a long linked list, which will affect the speed of the hashMap
[Java] Plain text view copy code?
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
} i
f ((p = tab[i = (n – 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
Option2: the length of the array -1 then the length of the array is, and as indicated in the source code comment, the length of the array needs to be 2 to the NTH power, i.e., an even number. An int hash value can be assumed randomly: 010101010101001010101010101010 it with an even number or an even number pick up what the result is & operation? And if it is an odd number of & then get results that may be an odd number, may also be an even number, and if even one & answer can only be an even number, so the answer is obvious, it is only when the length of the array is an even number is 2 n times the power, the number can ensure that may be even may be an odd number Then we look at the first value, The first value is the hash value, and the hash value can only be computed with the length of the array -1. If the hash value is computed directly with the array, it means that only a few bits of the hash value are computed and the other bits are not. This may also result in the same result for different elements (i.e. the last few bits are equal). In the source code, the method is to move the hash value 16 bits to the right to get its high 16 bits, and take xor with the low 16 bits. This ensures that the entire hash value is involved in the operation. Because different or can be 0, 1 binary to make, on average, for example take 1 0 0 0 1 1 0 1 & 1 0 0 0 0 11 probability and the probability of 0.25 0.75 1 0 0 0 0 1 take | 0 1 1 1 0 the probability of the probability of 0.75 0.25 1 Probability of taking ^ 0 1 1 0 probability of taking ^ 0 1 1 0 0.5 Probability of taking 1 0.5 Expansion method of hash In 1.8 hashMap expansion method is determined by resize method. This method has two functions 1. Initialization 2. Expand the capacity
[Java] Plain text view copy code?
{ 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; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } e lse { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) ! = null); if (loTail ! = null) { loTail.next = null; newTab[j] = loHead; } i f (hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } }
The method is to decide to expand the core code by first iterating through the array with three pieces of logic 1. Check whether the element in the array is null. If it is null, then use the tail interpolation method. If there are elements in the array, we should recalculate the position of the key in the array: E. hash & oldCap we find that when it evaluates, it does not evaluate directly with oldcap-1, but with the length of the array
[Java] Plain text view copy code?
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} e
lse if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
Now I’ve doubled the size of my array and the new length is 32, Old length is 16, 0101010101010010101010101 1 0 0 0 0 1 1 1 1 1 1 old length / / 1 1 / / 2 0 0 0 0 0 old length 1 1 1 1 1-1 / new length / 3 in 1, 3, we can find that, If the array is 0, the new length is greater than the original value. If the array is 0, it is not moved. If the array is 0, the new length is greater than the original value. And move 16 -> fifth 0, do not move 2,3 -> fifth non-0, know to move, and can be found in the source code, moved 16 fifth 0, do not move
[Java] Plain text view copy code? if (hiTail ! = null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
So if you want to move or not, you only need to look at the fifth from the bottom. I have to say that the design of hashMap is very elegant. I believe that through the study just now, students have a concrete understanding of the collision problem of hash and the expansion method of hash.