What is the function of the expansion operation of HashMap?

This article mainly introduces "what is the role of the expansion operation of HashMap". In the daily operation, I believe that many people have doubts about the role of the expansion operation of HashMap. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts about "what is the role of the expansion operation of HashMap?" Next, please follow the editor to study!

Let's first understand the basic data structure of HashMap. In fact, the description of the above figure is not complete, because apart from the fact that TreeNode and TreeNode are located in the red-black tree, TreeNode actually has pre and next pointers, that is, TreeNode and TreeNode have sequence.

The expansion operation of HashMap doubles the capacity of table so that Node can be reassigned to the new table later.

Set the size of table to n, then the size of newTable is 2n.

The Node in table [j] slot must satisfy Node.hash% n = j. Recalculate position index = Node.hash% 2n.

It is simply speculated that Node.hash% 2n = j or nimj.

Prove: let hash = kn + j

Index = hash% 2n = (kn + j)% 2n

When k is even, index = j, then Node should be in the newTable [j] slot.

When k is odd, Node should be in the slot of newTable [index j].

And because of n=0b000000001000000. The m bit is 1, and the rest bits are 0.

Kn must be expressed as n when k is even.