preface

Welcome to our GitHub repository Star: github.com/bin39232820… The best time to plant a tree was ten years ago, followed by now

omg

Now that we’ve covered the most commonly used HashMap, the thread-safe ConcurrentHashMap, this year we’ll take a look at the ordered LinkedHashMap

🔥 Introduction to the most complete Collection of Java containers 🔥 the most complete collection of Java containers the most basic data structures (hand tear list) 🔥 the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers the most complete collection of Java containers 🔥 Equals and hashCode 🔥 🔥 ConcurrentHashMap 🔥 Equals and hashCode 🔥

An overview of the

LinkedHashMap is a subclass of HashMap, and most of its implementation is the same as HashMap. The biggest difference between the two is that HashMap iterates the hash table in disorder, while LinkedHashMap iterates the hash table in order. The default rule for LinkedHashMap is that the output of the iteration remains in the same order as the key-value pair was inserted (although the specific iteration rules can be modified). In addition to organizing data in arrays, single-linked lists, and red-black trees like a HashMap, LinkedHashMap maintains an additional two-way linked list, inserting key-value pairs into the LinkedHashMap each time, in addition to the corresponding position in the hash table, it also inserts them into the end of the two-way circular list.

Here is its data structure:

We can see that it consists of an array + a single necklace list + a bidirectional list. Add a bidirectional linked list to the original HashMap data structure

LinkedHashMap

Inheritance structure

LinkedHashMap also inherits from HashMap, so most HashMap methods can be used directly.

The comments at the top summarize:

  • At the bottom are hash tables and bidirectional linked lists
  • Null is allowed and not synchronized
  • The order of inserts is ordered (the underlying list causes order)
  • The load factor and initial capacity have a significant impact on the LinkedHashMap

Basic attributes

// Transient linkedhashmap. Entry<K,V> head; // Transient linkedhashmap. Entry<K,V> tail; // Final Boolean accessOrder; // Final Boolean accessOrder; AccessOrder controls the order of access. Set to true, each time an element is accessed, the Node where the element is located becomes the last Node, changing the order in which the element is stored in the LinkedHashMap.Copy the code

A constructor

//LinkedHashMap constructor is implemented by calling the parent class constructor, Public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);  accessOrder = false; } public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } public LinkedHashMap() { super(); accessOrder = false; } public LinkedHashMap(Map<? extends K, ? extends V> m) { super(m); accessOrder = false; } public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor);  this.accessOrder = accessOrder; }Copy the code

Above is the LinkedHashMap constructor, passing in initialization parameters and code to show that the LinkedHashMap constructor corresponds to the parent constructor. AccessOrder =false -> Insert order; AccessOrder =false -> insert order; AccessOrder =false -> insert order; AccessOrder =false -> insert order AccessOrder = true -> sort the accessOrder.

Entry to define

This is more important

Private static class Entry<K,V> extends Hashmap. Entry<K,V> {private static class Entry<K,V> extends Hashmap. Entry<K,V> { // The constructor is no different from the HashMap constructor, Entry(int hash, K key, V value, hashmap. Entry<K,V> next) {super(hash, key, value, next); } private void remove() {before.after = after; after.before = before; } private void addBefore(Entry<K,V> existingEntry) {after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; Void recordAccess(HashMap<K,V> m) {LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); Void recordRemoval(HashMap<K,V> m) {remove(); }}Copy the code

LinkedHashMap not only uses the hash table in the HashMap to store entries, but also maintains a separate LinkedHashMapEntry. These linkedhashMapEntries also contain the preceding and subsequent references, confirming that this is a bidirectional list. This LinkedHashMapEntry provides methods for adding and deleting objects by changing the node’s precursor and subsequent pointing.

Put () method

LinkedHashMap does not override the put() method of the parent class, indicating that a call to put actually calls the put method of the parent class. HashMap put, which I won’t talk about here, has a method like that

LinkedHashMap overrides two methods

ode<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; } private void linkNodeLast(linkedhashmap. Entry<K,V> p) {end linkedhashmap. Entry<K,V> last = tail; P tail = p; If (last == null) // head = p; Else {// The original list is not empty, so the top node of the current node points to the original tail node. // The next node of the original tail node points to the current inserted node. }}Copy the code
2 void afterNodeAccess(hashmap.node <K,V> e) {// Move Node to last 3 linkedhashmap.entry <K,V> last; 4 // accessOrder = true and the current node is not equal to the tail node. 5 if (accessOrder && (last = tail)! 7 linkedhashmap. Entry<K,V> p = 8 (linkedhashmap. Entry<K,V>)e, b = p.before, a = P.after;  10 p.after = null; 11 // If (b == null) 13 // Head = next node of the current node 14 head = a; 15 else 16 // otherwise, the last node of B points to A. 18 // If a! = null 19 if (a ! = null) 21 a.before = b; 22 else 23 //b set last = b; 26 if (last == null) 27 // Set the first node to p. 28 head = p; 31 p.before = last; 31 p.before = last; 32 last.after = p; 33} 35 tail = p; 36 // Number of LinkedHashMap operations +1, used for quick failure verification 37 ++modCount; 38}} 39Copy the code

Maintain a bidirectional linked list by overriding the PUT method to keep access ordered.

The get () method

public V get(Object key) { Entry<K,V> e = (Entry<K,V>)getEntry(key); // Call getEntry() if (e == null) return null; e.recordAccess(this); // If accessOrder = true, delete the current e node return e.value; }Copy the code

The fifth and sixth lines of code are added to the HashMap get method, which, when accessOrder = true, means that the accessed elements are placed at the end of the list in the most recently accessed iteration order.

conclusion

LinkedHashMap has one more bidirectly-linked list maintenance than HashMap, which is more complex in terms of data structure and easier to read source code, since most of it is implemented by HashMap..

When we read the source code, we will find that polymorphism is everywhere ~ subclass with the parent class method, subclass overrides the parent class part of the method can achieve a different effect!

For example, LinkedHashMap does not override the PUT method, but the newNode() method inside the put method does. LinkedHashMap calls the parent class’s PUT method, which calls back the overwritten newNode() to do the job!

LinkedHashMap can be set in two traversal orders:

  • Access order

  • Insertion order

  • The default is insertion order

For access order, it is an implementation of the LRU(least recently used) algorithm, To use it, either rewrite the LinkedListMap methods (removeEldestEntry(map.Entry <K,V> eldest) and afterNodeInsertion(Boolean evict)), or extend it to LRUMap, Otherwise, access-ordered is not very useful. There is no further insight into the LRU of LinkedHashMap because it is not used much, but you can delve into it if you are interested.

LinkedHashMap traversal is an internally maintained two-way linked list, so initial capacity is unaffected by LinkedHashMap traversal

In a word. LinkedHashMap is a HashMap that descends from HashMap plus a bidirectional list, so there’s not much to talk about

Release notes

  • The source code here is JDK8 version, different versions may vary, but the basic principle is the same.

  • The Map family, the whole Set system, we still need a Set. Set to begin tomorrow

I have a goal to write two or three articles a week. I hope I can keep it up for a year. I hope you can give me more suggestions so that I can learn more and make progress together.

Daily for praise

All right, everybody, that’s all for this article. All the people here are talented.

Creation is not easy, your support and recognition, is the biggest motivation for my creation, we will see in the next article

Six pulse excalibur | article “original” if there are any errors in this blog, please give criticisms, be obliged!