“This is the 17th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
The HashMap was changed in JDK 1.8, but the general flow of the put method is still the same.
A flowchart
So we get the index of the array
Whether it’s 1.7 or 1.8, they first hash the hashCode by putting the key passed in, then perform the hashCode and the array length calculation to get the array index.
Array subscript is null and encapsulates the object into the HashMap
After obtaining the array index, it will determine that the current array index position element is empty, and will directly wrap the passed key and value into a Node object (note: in JDK1.7 it is an Entry object, and after 1.8 it is a Node object), which can be regarded as a key and value object.
Wrapping the object will place the current object in the previous array subscript, thus storing the key and value into the HashMap.
In JDK1.7, hashMap is implemented using an array + a linked list, while in JDK1.8, hashMap is implemented using an array + a linked list + a red-black tree.
Array subscripts are not empty
If the array subscript is not empty, we need to discuss cases:
If it is jdk1.7, it will determine whether it needs to be expanded first, if it needs to be expanded first, if it does not need to be expanded, then generate an Entry object, and then use the header method to add to the current location of the list.
If it is JDK1.8, the Node object type in the current location will be determined first, and whether it is a linked list or a red-black tree. 1. If it is a red-black tree: The key and value will be encapsulated as a red-black tree node and added to the red-black tree. Then, in the process of adding a red-black tree, go back to the tree and determine whether the current key exists in the tree. 2. If it is a linked list: Encapsulates the current key and value into a linked list Node and inserts them into the linked list by tail insertion. Since it is a tail interpolation method, it will traverse the list first and determine whether the key is repeated during the traversal. If the key is repeated, the value will be directly updated. If the value is not repeated, the new Node object will be inserted into the list after traversal.
If the number of nodes is greater than 8 and the length of the hash table is greater than 64, the current linked list is converted to a red-black tree. After inserting objects into the linked list or tree, the system determines whether to expand capacity. If necessary, the system expands capacity.
That’s how the PUT method works in a HashMap.