LinkedHashMap source code details

Preface

I didn't intend to talk about map first, but with the understanding of set set, I found that if I don't understand all kinds of maps first, I can't understand set. Because there are many sets, the bottom layer is stored with map. For example, HashSet uses HashMap, and linkedhashset uses LinkedHashMap. So I'm going to finish the map.

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　---WZY

1、 LinkedHashMap

Let's talk about its characteristics first, and then verify its implementation principle by analyzing the source code one by one

1. Ensure the sequence of inserting elements. In depth, there are two ways to iterate elements. One is to iterate in the order in which the elements are inserted. For example, if a, B and C are inserted, then the iteration is also a and C. the other is to iterate in the order of access. For example, if B is accessed before the iteration, then the iterative order is a, C and B. for example, if B is accessed before the iteration, and then a is accessed, then the iterative order is C and a, for example, B is accessed before the iteration, then B is accessed, and then a is accessed. The iteration order is still C and a. It means that the most recent visits are not placed in the last iteration, but depends on the length of time visited before the iteration.

3. Model of internally stored elements. Entry is as follows. Compared with HashMap, it has two more attributes, one before and one after. Next and after sometimes point to the same entry. Sometimes next points to null and after points to entry. This will be analyzed later.

4. LinkedHashMap and HashMap are the same in storage operation, but LinkedHashMap has many things that will remember the elements inserted before. These elements are not necessarily drawn in a bucket.

In other words, the basic operation of LinkedHashMap is the same as that of HashMap. Two attributes are added to it, that is, to record the element inserted before and the element inserted after. That is, just set the values of these two attributes after the same operation as HashMap. Note that there will be a header entity to record who is the first inserted element and find the first element during traversal.

In fact, the storage looks like the figure above. It should be clearly distinguished here. In fact, the storage method is the same as HashMap, but a new thing is added at the same time, which is a two-way circular linked list. It is because of this two-way circular linked list that LinkedHashMap is different from HashMap.

5. Others, such as how to implement the circular two-way linked list, and how to implement the insertion order and access order, are explained in detail below.

2、 Source code analysis

2.1. The storage structure source code of internal storage elements and understand the LinkedHashMap two-way circular linked list,

Check the entry of LinkedHashMap to verify the above feature 3

2.2 construction method

There are five construction methods.

2.3. Verify the existence of header

2.4 how does LinkedHashMap share some methods with its parent class HashMap. For example, put operation, etc.

1, after the LinkedHashMap construction method is completed, call put to add elements to view the put source in the parent class.

　　　　　　　　　　　　　　　　put

Void addentry (int hash, int bucketindex) and void createentry (int hash, int bucketindex) are rewritten

At this point, you should have a certain understanding of the stored procedure of LinkedHashMap. And you should also know how to store it. What's special about storage.

2.5. Let's look at the use of iterators. Traversal of bidirectional circular linked list. However, this iterator is abstract and cannot be used directly by objects, but can be used indirectly through keyset() Interleaver () is the iterator used

How does keyset () indirectly use linkedhashiterator

Keyset () in HashMap

Found newkeyiterator()

It is called by the LinkedHashMap object, and the keyiterator method is overridden in the LinkedHashMap, so the LinkedHashMap iterator is used indirectly

2.6. Let's see how the access order is implemented during iteration. In fact, the key is which recordaccess method is used to see the process

There is a get method in LinkedHashMap, and the get method in the parent class will not be used

2.7. If the default insertion order is used, there is no need to analyze it. That is, if the code under the above if does not take effect, the insertion order will be used.

3、 Verify the function of LinkedHashMap

Note that the map cannot only get the iterator, but only the keyset () iterator(); That is, the iterator cannot iterate over the map, and the iterator can be used indirectly. For example, first get the iterator of the key, and then find the corresponding value value through the key, or directly use the values () method to get the values of all maps. The underlying layer of the values () method is also the iterator used.

1. Using the access order, the result is indeed as we expected

Note: if you use the for loop to traverse, this is definitely not the result. The reason is that the for loop is searched in the order of key values. From 1 to 6, if you need to verify the access order, you must use the iterator. There are two ways to use the iterator for map, one is to use values() and the other is to use keyset() Iterator()； You can try it yourself.

4、 Summary

1. Know the implementation principle of LinkedHashMap.

1.1, the realization principle as like as two peas HashMap. LinkedHashMap basically has some features of HashMap.

1.2. See the two diagrams at the beginning for the specific storage implementation. Although the second picture is messy, if you look carefully, you can understand the truth.

2. Know the access order and insertion order of LinkedHashMap iteration

2.1. Key attribute accessorder

2.2 key methods recordaccess

3. Know the difference between linekdhashmap and HashMap.

3.1. LinkedHashMap is a subclass of HashMap. Its implementation principle is similar to that of HashMap. The only difference is that LinkedHashMap has a two-way circular linked list.

3.2. Because there is a two-way circular list, LinkedHashMap can record the order of inserting elements, but HashMap cannot,

4. Map uses two methods of iteration to know how to use iterators internally.

　　　　　　　　　　keySet(). iterator()

　　　　　　　　　　values()