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

How to analyze part of the source code of HashMap, in view of this problem, this article introduces the corresponding analysis and answer in detail, hoping to help more partners who want to solve this problem to find a more simple and easy way.

HashMap implementation of Map interface based on hash table. This implementation provides all optional mapping operations and allows the use of null values and null keys. The HashMap class is roughly the same as Hashtable except that it is out of sync and allows the use of null. This class does not guarantee the order of mappings, especially since it does not guarantee that the order is permanent The structure of HashMap is as follows:

We can see that the structure of HashMap is mainly divided into two parts: the table on the left and the linked list on the right. The following focuses on the analysis of the source code of HashMap.

1. Constant

two。 Common construction methods

3. Common methods

(1), final int hash (Object k), this method is used to calculate the hash value of key. As you can see from the last few lines of the method, in order to ensure the uniform hash of key, the hashCode%length method is not used, because the shift operator not only has a more uniform hash, but also has a faster uniform speed than hashCode%length.

(2), public V get (Object key)

We see that the get method first determines whether key is null, and if it is null, call getForNullKey (), otherwise call the getEntry (key) method to get value. Let's continue to analyze the source code of getForNullKey:

Private V getForNullKey ()

Visible: loop through the linked list of table [0] until you find the Entry of key==null, otherwise why does the return null; be table [0]? Because in put, if you key==null, store the entry directly in the location of table [0], we will analyze the put method later. Next, analyze the getEntry (key) method:

Calculate the subscript of the table where the Entry is located through the key hash value. Please note that the subscript calculation method is obtained by the indexFor () method, and then traverses the Entry until an Entry with equal hash and equals is returned, otherwise null is returned.

All right, the get method is basically like this, and then let's analyze the put method.

(3), public V put (K key, V value)

The general flow of the put method is:

①, first determine whether key is null. If it is null, call the putForNullKey (value) method. Please note that the logic of putForNullKey and the above getForNullKey correspond one to one.

②, calculate the hash value of key, and use the indexFor () method to locate the location of the element stored in table table [I].

③, loop through table [I], if the new value and the old value are equal, overwrite the old value and return the old value

The number of ④ and modCount++, operations is + 1, and call addEntry to insert the new value into the linked list.

Let's analyze the putForNullKey (value) method source code:

Look, here is table [0] again, which is symmetrical with table [0] in getForNullKey. It is easy to understand by traversing-- > the new value overwrites the old value-- > returning the old value-- > Operand + 1 color-> inserting the new element.

Next, let's analyze a series of logic in the addEntry method:

First of all, threshold=capacity * load factor, that is, the critical value = capacity * load factor = 1600.75f, if the usage in map exceeds threshold, the capacity will be doubled. Resize is a very complex process, involving rehash and so on, which I will introduce later, and now let's focus on addEntry (). BucketIndex is the subscript where the element is stored in table, that is, the element is stored in table [bucketIndex]. Finally, call createEntry to store the new element in HashMap. The source code of createEntry is as follows:

Through new Entry (hash,key,value,e), insert the new element into the table [bucketIndex], let's take a look at the construction method of Entry:

The focus is on the line next = n. When you see the header insertion method used to insert elements into the linked list, it is estimated that the purpose of no tail insertion is to save the cost of traversing the linked list.

Well, that's what the put method is, and it's easy to understand, so let's analyze the Entry type.

4.Entry inner class

HashMap has a variable: transient Entry [] table, you can see that table is an array of Entry, and Entry itself is an element of a linked list. Entry implements Map.Entry, while Map.Entry is an interface. Entry contains four elements, final K key; V value; Entry next;int hash;hash is the hash value of this element, and the remaining three elements are not interpreted. The methods of the Entry class are basically very simple. You can understand them by reading the source code. I will focus on explaining the two methods equals and hashCode. The source code is as follows:

Comparing whether even Entry is equal is through the conditions in if, which is easier to understand. HashCode source code:

Finally, focus on the rehash method. When analyzing rehash, I first explain what rehash is: when our HashMap usage exceeds threshold=capacity * load factor, that is, the critical value = capacity * load factor = 1600.75f, rehash occurs, doubling the capacity, and then all the elements are re-hashed into different table [I] according to the new hash rules. But rehash has a lot of performance consumption, so if we can predict the number of elements when using HashMap, it's best to specify the size of the HashMap at construction time. The source code of rehash is as follows:

Entry [] newTable = new Entry [newCapacity], a new table is common, which consumes a lot of memory! The previous one is easy to understand. Focus on the transfer method, which is the way to re-hash elements. The source code is as follows:

Loop through table (old array), calculate the subscript of newTable, and store the old element e in newTable. There is a detail to note here. When I talked about the put method, I mentioned that when inserting an element, the insertion method is that the new element is added to the head of the linked list, but we can analyze through the transfer method: in rehash, the element before the head will be rehash first, and the element at the tail will be the last rehash, so when the rehash ends The previous element in the head will sink to the tail, and the element in the tail will rise to the head.

On how to HashMap part of the source code analysis questions to share the answers here, I hope the above content can be of some help to you, if you still have a lot of doubts have not been solved, you can follow the industry information channel to learn more related knowledge.

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.