The HashMap addition method mentioned above, now continue the link above

In the previous source code analysis article, if put is used, if the number of elements exceeds threshold, resize will be called for expansion

1. Capacity expansion mechanism

To understand the HashMap scaling mechanism you need to have these two questions

  • 1. When will capacity expansion be required
  • 2. What is the HashMap expansion

When adding elements, if the threshold is exceeded, the capacity will be expanded. Simply speaking, the capacity of a kettle is two liters, and then it is already full, but you still need to add more water. What should I do? Let me get a bigger one. So the expansion of HashMap is just like your water bottle, which is already full, so I will change to a larger water bottle and continue to add water. But there are a lot of conditions when you change your kettle.

When I looked at the source code of this resize, I was also confused. Finally, I asked the big guy and got the answer that it was because 1.8 added red black tree, it was troublesome to look at 1.7. Then I went to the Internet and looked at other people’s articles, which were basically based on 1.7 resize. Therefore, the resize of 1.7 is used for analysis.

Take a look at the implementation of resize in JDK1.7.

The copy operation is the transfer method called

In combination with our small example, we can understand the resize in 1.7 as follows: go to the supermarket and buy a larger kettle, and then pour the water from the previous kettle into the new kettle. Then replace the capacity of our current kettle and tell people I have a bigger capacity. (Forced metaphor hahahaha)

Resize in 1.7 is as simple as that, so let’s take a look at resize() in 1.8 so we don’t get confused

I’ve divided the 1.8 resize method into two parts here

  • 1. Calculate the new newCap(new capacity) and newThr(new threshold point)
  • 2. Copy the new array

The first part

The second part

Compare 1.7

  • 1.7 Elements do not need to be replaced. The position of the 1.8 element is either in its original position, or moved by a power of 2
  • There is no need to recalculate hashes like 1.7

2. Delete the

If you delete it, you first find the location of the element, and if it’s a linked list, you go through the list and you find the element and then you delete it. If you’re using a red-black tree, you go through the tree and you find it and you delete it, and if the tree is less than 6, you roll the list.

Delete method:

Call removeNode:

3. Find elements

A lookup method that finds the Value by the element’s Key.

Call the getNode() method

The logic is to calculate the index position by Key, and then check the first node to see if it is the desired node, if not to see if it is dead red black tree and linked list.

4. Traversal

Let’s use the following examples to demonstrate how a HashMap traverses

1. Iterate Key and Values respectively

 		for (String key:map.keySet()){
            System.out.println(key);
        }
        for (Object value : map.values()) {
            System.out.println(value);
        }
Copy the code

2. The iteration

 		Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Object> mapEntry = iterator.next();
            System.out.println(mapEntry.getKey() + "= = = =" + mapEntry.getValue());
        }
Copy the code

3. Obtain the key set

 	Set<String> keySet = map.keySet();
        for (String str : keySet) {
            System.out.println(str + "= = = =" + map.get(str));
        }
Copy the code

4. Obtain the Entry collection and iterate over the Entry collection

	Set<Map.Entry<String, Object>> entrySet = map.entrySet();
        for (Map.Entry<String, Object> entry : entrySet) {
            System.out.println(entry.getKey() + "= = = =" + entry.getValue());
        }
Copy the code

By contrast, it is best to use the iterative method, which can also delete the elements of the collection during the iteration

conclusion

Jdk1.8-based HashMap is composed of array + linked list + red-black tree. When the length of the linked list exceeds 8, it will be automatically converted into a red-black tree, and when the number of red-black tree nodes is less than 6, it will be converted into a linked list. Compared with the earlier version of JDK HashMap implementation, red-black tree is added as the underlying data structure, which can greatly increase the efficiency of retrieval when the data volume is large and the hash collision is large. A HashMap is not thread-safe. It supports null values for K and V, K is overridden by repetition, V can be repeated, and the data traversed by a HashMap is not ordered or unordered