If the table length of a HashMap is M, the number of key-value pairs stored in all the HashMap is N, and if the hash function meets the requirement of uniformity, then the length of each linked list is approximately N/M, so the complexity of average lookups is O(N/M).

In order to improve the efficiency of searching, the length of each linked list needs to be reduced, that is, the table should be as large as possible. HashMap adopts dynamic expansion to adjust M value according to the current N value, so that both spatial efficiency and time efficiency can be guaranteed.

Java container 03–HashMap source code analysis

JAVA7 rehash uses the single-linked list header method. New elements in the same position are always placed at the head of the list. This differs from JAVA8 in that if a hash conflict occurs, elements placed first on an index will end up at the end of the Entry chain.

JAVA8 takes advantage of the following feature in the Rehash algorithm: The HashMap is expanded by a power of 2, so elements are either in their original position or moved by a power of 2. What does that mean? Let’s take an example.

Assume that capacity is 16 and new capacity is 32 after capacity expansion:

old capacity : 00010000

new capacity : 00100000

How do you calculate the subscript of an Entry in a bucket based on a HashMap? Key1 = 0001 1001 KEY2 = 0000 1001 Hash & (Leng-1) : key1: 0001 1001 & 0000 1111 -> 0000 1001 key2 : 0000 1001 & 0000 1111 -> 0000 1001

After expansion hash & (Leng-1) : KEY1:0001 1001 &0001 1111 -> 0001 1001 KEY2:0000 1001 &0001 1111 -> 0000 1001

Therefore, when we extend the HashMap, we do not need to recalculate the hash as we did in JDK1.7. ** we only need to see if the hash value is 1 or 0. If it is 0, the index is unchanged, and if it is 1, the index becomes old index +oldCap.

If ((e.hash & oldCap) == 0). If ((e.hash & oldCap) == 0). If (e.hash & oldCap) == 0).

This algorithm not only saves the time of recalculating the hash value, but also the chance of the new bit being 0 or 1 is random. Therefore, the resize process evenly distributes the previously conflicting nodes to the new bucket. This is a new optimization point in JAVA8: in JAVA7, when rehash an old list to migrate a new list, the list elements will be inverted if they are in the same array index position in the new table, but as you can see from the figure above, inversion is not the case in JAVA8.

Reference: www.importnew.com/20386.html www.cnblogs.com/csslcww/p/9…