This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Brief description of nouns:

  • Capacity Capacity. The default value is 16
  • LoadFactor loadFactor. The default value is 0.75
  • Threshold Threshold threshold = capacity x load factor, default 12, empty parameter when constructing hashMap. When the number of map elements exceeds the threshold, expansion is triggered

When will the capacity be expanded (JDK7 and JDK8 are different)

  • Generally, the capacity is expanded when the number of elements exceeds the threshold. Each expansion is twice the previous capacity.
  • A HashMap has a maximum capacity of 1>>3​0, calculate the size by oneself baidu. Beyond this value there is no increase and the threshold is set to, that is, the threshold will never be exceeded

Compare the capacity expansion mechanism of JDK7 and JKD8

The capacity expansion mechanism of JDK7 is relatively simple and has the following features:

  • Empty parameter constructor: initializes array with default capacity, default load factor, default threshold, internal array is empty array
  • Parameter constructors: Determine capacity, load factor, threshold, and so on based on the parameters
  • The array is initialized the first time it is put, and its capacity is at least a power of 2 of the specified capacity. The threshold is then determined based on the load factor
  • If it is not the first capacity expansion, new capacity = old capacity x2 New threshold = New capacity x load factor

Note:Jdk7 expansion condition: only in arrayThe capacity exceeds the threshold. ProcedurewhenandhappenedHash conflict, capacity expansion is performedThere will be subordinates:

  1. Assume a default hashMap of length 16, a threshold of 12, and a load factor of 0.75. If no hash conflict occurs when the 12th or 13th element is added, the expansion will not occur. A default initialized hashMap can hold up to 16 elements without hash collisions.
  2. The default HashMap can hold up to 26 (11+15) elements. At this time, the number of elements is 11 and not more than 12, so expansion will not occur. The subsequent 15 elements are all stored in other locations. At this time, because the newly added elements do not have hash conflicts, so expansion will not occur. When the 27th element is added, hash conflicts are bound to occur, and the number of elements exceeds the threshold and expansion occurs

​

​

JDK8 expansion mechanism (with many tweaks)

  1. HashMap expansion in JDK8 requires only one condition: when a new value is stored, the number of existing elements is greater than the threshold (if the existing elements are equal to the threshold, the next storage must trigger expansion mechanism).

Note: (1) Expansion must be when the new value is inserted, the new value is not to replace the previous position. (2) Capacity expansion occurs after the storage of elements. After the storage of data (storage first, capacity expansion later), judge the number of objects currently stored. If the number exceeds the threshold, capacity expansion will be performed

  1. The capacity of a HashMap usually varies in the following ways:
  • Empty parameter constructor: The instantiated HashMap defaults to null when the internal array is not instantiated. The first initial expansion starts when the PUT method is called for the first time. The length is 16
  • Parameter constructor: Used to specify capacity. The specified positive integer finds a power of 2 that is not less than the specified capacity and assigns this to the ** threshold. ** The first time the PUT method is called, the threshold is copied to the capacity, and then the threshold = the capacity x load factor. (Therefore, it does not mean that if we manually specify the capacity, the capacity will not be expanded. If the capacity exceeds the threshold, the capacity will be expanded.)
  • If the capacity is not expanded for the first time, the capacity is doubled and the threshold is also doubled

Note:

  • During the first put, capacity expansion is triggered (considered as initialization), data is saved, and capacity expansion is determined
  • If the device is not put for the first time, the device does not initialize the device, saves data directly, and determines whether to expand the capacity

Background knowledge

In Java7, the underlying HashMap uses an array of time Entry pairs, and each Entry pair extends down into a linked list. Each Entry pair in the linked list not only stores its own K/V value, Java8 also stores the address of the last and last Entry pairs. The underlying structure of the HashMap has been changed somewhat. It still uses an array, but the object of the array is an Entry pair. Java8 becomes a combination of a linked list and a red-black tree. When a small amount of data is stored, the linked list takes precedence over the linked list. When the length of the linked list is greater than 8 and the total amount of data is greater than 64, the linked list is converted to a red-black tree. So Java8’s data store is a combination of linked lists and red-black trees. If the amount of data is less than 64, there is only a linked list, if the amount of data is greater than 64, and an array subscript is greater than 8, then it is a red-black tree.

Think about:

  1. The capacity expansion mechanism of Java8 lacks the judgment of hash conflicts compared with That of Java7, so all hash conflicts will occur, resulting in 12 elements in the same position of the hashMap array. So a good hash algorithm is important for Java8, and it needs to be evenly distributed
  2. Why is the load factor 0.75

Finally: this article is summarized through baidu search content! Have written wrong place, welcome to correct, hope can bring you help ~

Reference links 1:zhuanlan.zhihu.com/p/114363420

Reference links 2:blog.csdn.net/pange1991/a…