This is an article written a long time ago, was published on another platform, moved to nuggets today.
structure
Let’s start by looking at the constructor of a hashMap
HashMap hashMap = new HashMap();
Copy the codeThe no-argument constructor for a hashMap is very simple, internally just an initialization of default values, loading factor 0.75f
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Copy the codeTableSizeFor Controls the size of the hashMap when the default value is initialized. TableSizeFor controls the size of the hashMap.
public HashMap(int initialCapacity, float loadFactor) {...// Some check judgments
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
Copy the codeLet’s see what this method does by enumerating several cap values:
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 codeTableSizeFor is used to ensure that the hashMap size is a power of 2. For example, if we new hashMap (7), the actual size allocated at the bottom is not 7, but 2^3^ = 8. Why this is so, see below.
put
Let’s take a look at the put methods of a hashMap. Of course, key and value can be of type Object
hashMap.put("key"."value");
Copy the codeFirst, the underlying key is used to retrieve a hash value, which is not just key.hashcode (), but also moves 16 bits to the right and does the or. The reason for the right shift is to include the high part of hashCode in the calculation when fetching the subscript TAB [I = (n-1) & hash] to prevent frequent collisions of results. Why would n minus 1 hash be a subscript, is it in the range of 0, n minus 1? Not necessarily. So you have to restrict n, which is the power of 2. 2^n^ -1 is 1 in the low order of n (excluding) segmentation, and the high order is 0. When the & operation is performed, the low order 1 is useful, and the combination of the low order results range is (0, n-1).
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeThe bottom layer then calls putVal, where all the hashMap expansion logic is. When the oldTable array is null or capacity 0 for the first time, size is initialized DEFAULT_INITIAL_CAPACITY = 16. OldTable. Length * 2; oldTable. Length * 2; oldTable. See below
final Node<K,V>[] resize() {
...
// table ! = null, update size and threshold
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // threshold * 2.else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); }...// Update threshold = 16 * 0.75f
threshold = newThr;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}
Copy the codeWhen oldTable is not null:
When there is no collision on oldTab array index, that is, there is no linked list, we directly place oldTab[j] randomly in newTab, and its subscript position is in the range e.hash & (newcap-1), that is, (0, newcap-1).
When there is a linked list, when a random index collides at index == 0, insert the element at the end of the new list. When e.ext is null, move the new list to newTab[j] (note that j is in the original position j). When the random subscript does not collide, the element is also inserted to the end of a new list until e.ext null moves the new list to newTab[j + oldCap]. The value range of j + oldCap (0, 2 * oldCap).
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;
elsehiTail.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; }}Copy the codeIn JDK8, the red black tree is introduced. In this case, we will determine whether the current oldTab[j] has been converted from the list to a red black tree. If so, we will split. Split code will not be posted, there is an internal method to note, when the number of red-black tree elements < UNTREEIFY_THRESHOLD, i.e. Lc < 6, the red-black tree will be converted to a linked list. After all, linked lists have an advantage when it comes to inserts.
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
Copy the codeHash (0, n-1). If there are no elements in the current index, create a Node object and place it under the index. So at the bottom, although we’re putting in keys and values, we’re actually saving Node objects.
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
Copy the codeIf the index of (n – 1) & hash collides. If the current key already exists, then e.value = value will be returned to the user. If the hash value is the same, then there will be a collision, but the hash value is not necessarily the same value. It may be a linked list with multiple elements under the current array index.
If the number is red and black, p instanceof TreeNod, putTreeVal is put.
Now look at the judgment: If e is the end of the linked list, insert the Node constructed by the value of the current put directly into the end of the linked list. If the same key is found in the traversal process, break the loop, reference the address replacement, and return the oldValue to the user.
Node<K,V> e; K k;
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break; p = e; }}if(e ! =null) { // existing mapping for key
V oldValue = e.value;
if(! onlyIfAbsent || oldValue ==null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
Copy the codeIn the above code, we need to pay attention to the next treeifyBin method, that is, when the number of elements in the current list is greater than 8, we need to make the decision and operation of converting the list into a red-black tree. To look down
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
Copy the codeAs you can see here, the conversion is conditional. If we tab.length >= 64, we will convert the number, otherwise we will expand the number. After the expansion, the hash of the entire TAB is increased and the linked list is too long. When the number is larger than 64, the number is converted to red and black for memory sake, which improves the query efficiency.
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) ! =null) {.../ / conversion}}Copy the codeget
The hashMap get operation is much simpler. First we’re going to get the hash of the key.
If TAB length > 0 and the current subscript has a value, if TAB [(n-1) & hash] subscript is the key value, the value is returned directly; otherwise, the current structure is a red and black number. If so, run getTreeNode to obtain the value, If the current structure is a linked list, it iterates to find the same key and returns the corresponding value
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if((tab = table) ! =null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) ! =null) {
if (first.hash == hash && // always check first node((k = first.key) == key || (key ! =null && key.equals(k))))
return first;
if((e = first.next) ! =null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
return e;
} while((e = e.next) ! =null); }}return null;
}
Copy the codeOk, end of article.