Shulou(Shulou.com)06/02 Report--

This article introduces the knowledge of "the introduction of HashMap and why the expansion is the nth power of 2". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. What is HashMap?

HashMap is a collection class in Java that stores data in the form of key-value pairs (Key and Value), such as QQ accounts and QQ passwords. The QQ account is Key and the password is Value. As shown below (if the QQ account is 123456 and the password is abcdef)

The running result is as follows

If you store the same Key, then the Value will be overwritten, similar to QQ changing the password, the account will not change, only the password will be changed.

The running result is as follows

two。 Why expand 2 to the nth power?

First of all, let's take a look at the putVal method (stored value) and resize method (capacity expansion) in HashMap. The reason why HashMap expansion is the n power of 2 and the two methods are inextricably linked.

Through the putVal method, we can see that when storing the value, HashMap will first perform a bitwise sum operation on the hash value of key and the length after expansion, where hash is the result of calculating key in the hash method, and n is the length of the expanded capacity (that is, the length of the array, default is 16), and then determine whether hash collisions are stored differently. The source code is shown in the following figure.

Through the resize method, we can see that the expansion will create a new tab, then traverse the old tab, and add the old elements to the new tab for the calculation of e.hash & (newCap-1), that is, (n-1) & hash, where n is the capacity of the collection and hash is the hash value calculated by the hash function of the added elements. The source code is shown in the following figure.

The reason why this 2n expansion has a great relationship with the above two methods, first of all, they all use bitwise and operation, that is, the bitwise and operation is to change the value into binary first, and then the operation is carried out. If there is 0, it is 0, and if both are 1, the default capacity of HashMap is 16, so when it is stored in the array, it is 15, and the binary 15 is 1111. After expansion, it is 32-1 and 11111111.

If it is all 1, it can greatly reduce the hash collision and increase the efficiency.

Take a look at the bitwise sum results when the capacity is 11111111. Through the following results, we can see that the results are very scattered, greatly reducing the occurrence of hash collisions.

Again, when the capacity is not 11111111 but other values, you can see that 1, 2, 4 perform hash operations with different values, but the result is the same, that is, a hash collision occurs.

From the above comparison, we can see that 11111111 and other values

It greatly reduces the occurrence of hash collisions, which is why

The reason why the expansion of HashMap adopts the n-power of 2.

This is the end of the introduction of HashMap and why the expansion is the nth power of 2. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.