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

This article mainly introduces what HashMap is in the java data structure, which has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.

What is HashMap?

HashMap is the implementation of the Map interface based on the hash table. This implementation provides all optional mapping operations and allows the use of null values and null keys. This class does not guarantee the order of the mapping, especially it does not guarantee that the order is permanent. This implementation assumes that the hash function distributes elements appropriately between buckets, providing stable performance for basic operations (get and put). The time required to iterate through the collection view is proportional to the "capacity" (number of buckets) and its size (key-value mapping correlation factor) of the HashMap instance.

Break down the above description one by one, which is as follows:

1. HashMap allows null values and null keys

2. This kind of mapping does not guarantee the order of mapping, that is, HashMap is disordered, but this disorder may be different from the understanding of many people, and it is not the disorder understood by many beginners (in fact, HashMap is actually ordered at some time), which will be explained in detail later.

3. This implementation assumes that the hash function distributes elements appropriately between buckets, providing stable performance for basic operations (get and put). Note that this sentence is important and a potential danger in use, that is, "this implementation assumes that the hash function will properly distribute elements between buckets" is assumed, not affirmed, that it is possible that it is not properly distributed, but in fact it is not properly distributed, and that someone will do hash collision attacks by constructing special hash values (although generally do not think about it) We will talk about it later.

4. The time required to iterate through the collection view is proportional to the "capacity" of the HashMap instance (the number of buckets) and its size (key-value mapping correlation coefficient). This sentence gives us a hint that if you need better iterative performance, do not set the initial capacity too high, as to why, a detailed analysis will be given later.

There is no need to talk about the first, the first is the second, why is HashMap disordered? Why can't this class guarantee the order of mapping?

In terms of the storage structure of HashMap, HashMap will not directly use the key set by the user as the key, but will use the hash value of the key set by the user as the actual key. This sentence may be a bit of a mouthful. Let's take the put method as a starting point and analyze it from the source code.

Public V put (K key, V value)

The source code of the put method is as follows:

You can see that the put method calls the hash method, and then the putVal method. First look at the source code of the hash method:

As you can see, the hash method is very simple, judge whether key is equal to null, if it is equal to null, return 0, otherwise return the latter string, which is a simple hash algorithm, interested students can take a look at some notes on why the hash algorithm is adopted, here do not introduce too much (the hash algorithm is very important, it is suggested that students with certain abilities should see why they choose the hash algorithm and try to verify it. Then those who are interested can write their own hash algorithm to compare whether it is better than his-- remember, the system is not necessarily optimal, but in most cases it is better.

Then there is putVal. The source code of putVal is as follows:

The first step is to determine whether the current table is empty or null. If so, call the resize method (this method is a very core method, which will be described separately later) to initialize, and then assign the size of the initialized tab to n, and then the next line will be used. See this line below:

For some students with poor foundation, this line may not seem so easy to understand, the core of which is:

I = (n-1) & hash

Why is this paragraph written in this way? Because the hash value may be larger than tab's size, and if you don't handle it, the array may be out of bounds, so you need to treat the hash value as a number smaller than size, and this operation can do it, and it's not difficult to think about why you can think for yourself (modular arithmetic can also achieve this effect, but bit operations are faster).

Then it is judged that if the subsequent operations for null are easy to understand, build a new node and insert it into table. If it is not for null, it will be a little more complicated, which will be explained in the next section.

Thank you for reading this article carefully. I hope the article "what is HashMap in java data structure" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

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.