From: www.jianshu.com/p/8f4f58b4b…

1 introduction

LinkedHashMap descends from HashMap. If you don’t know how HashMap works, please read the following article

2 LinkedHashMap usage and implementation

Let’s start with a LinkedHashMap structure, don’t be empty, read the article and then look at this diagram, you will understand in seconds, first mix a familiar face:


The structure of LinkedHashMap. PNG

2.1 Application Scenarios

Hashmaps are unordered, and we use LinkedHashMap when we want to store key-values sequentially.

        Map<String, String> hashMap = new HashMap<String, String>();
        hashMap.put("name1"."josan1");
        hashMap.put("name2"."josan2");
        hashMap.put("name3"."josan3");
        Set<Entry<String, String>> set = hashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
Copy the code

image.png

We insert in order xxx1, xxx2, xxx3, but the output is not in order.

For the same data, let’s try LinkedHashMap

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name1"."josan1");
        linkedHashMap.put("name2"."josan2");
        linkedHashMap.put("name3"."josan3");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
Copy the code

image.png


As it turns out, the LinkedHashMap is ordered and defaults to the insertion order.

2.2 Simple Use

Like HashMap, it provides key-value storage and provides put and GET methods for data access.

        LinkedHashMap<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name"."josan");
        String name = linkedHashMap.get("name");
Copy the code

2.3 define

LinkedHashMap inherits HashMap, so they have a lot in common.

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
Copy the code

2.4 Construction method

image.png


LinkedHashMap provides several constructors, starting with the constructor for empty parameters.

    public LinkedHashMap() {// call the HashMap constructor, which initializes Entry[] table super(); // Sort by accessfalse
        accessOrder = false;
    }
Copy the code

First, the constructor of the parent class HashMap is called using super. In fact, Entry[] table is initialized according to the initial capacity and load factor. See HashMap parsing for details.

AccessOrder is set to false. This depends on the order in which the data is stored. LinkedHashMap stores data in an ordered order and in two types: insert order and accessOrder.

Here accessOrder is set to false to indicate that the order stored in the LinkedHashMap is sorted by the order inserted by calling the PUT method, which is also the default. LinkedHashMap also provides a constructor that can set accessOrder. Let’s look at the order in this mode.

Map<String, String> linkedHashMap = new linkedHashMap <>(16, 0.75f,true);
        linkedHashMap.put("name1"."josan1");
        linkedHashMap.put("name2"."josan2");
        linkedHashMap.put("name3"."josan3");
        System.out.println("Starting order:");
        Set<Entry<String, String>> set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
        System.out.println("Cause an Entry with a key of name1 to be at the end of the table via get.");
        linkedHashMap.get("name1");
        Set<Entry<String, String>> set2 = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator2 = set2.iterator();
        while(iterator2.hasNext()) {
            Entry entry = iterator2.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
Copy the code

image.png


The call to GET (“name1”) caused the Entry corresponding to name1 to move to the end.

Remember that in the constructor of a HashMap, init is called. In a HashMap, init is an empty implementation, but LinkedHashMap overrides that method, so in the constructor of a HashMap, Init (); init ();

    /**
     * Called by superclass constructors and pseudoconstructors (clone,
     * readObject) before any entries are inserted into the map.  Initializes
     * the chain.
     */
    @Override
    void init() {// create onehashHeader = New Entry<>(-1, NULL, null, null); Before = header.after = header; // Create a list with only header nodes. }Copy the code

This is a bit different from Entry in our last HashMap article, where the static inner class Entry is defined like this:

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
Copy the code

There are no before and after attributes. Originally, LinkedHashMap has its own static inner class Entry, which inherits hashMap. Entry, defined as follows:

    /**
     * LinkedHashMap entry.
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        Entry<K,V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }
Copy the code

So the LinkedHashMap constructor, which basically calls the HashMap constructor to initialize an Entry[] table, then calls its own init to initialize a two-way list with only heads. The following operations are complete:


LinkedHashMap constructor. PNG

2.5 put method

LinkedHashMap does not override the PUT method, so call HashMap to get the put method as follows:

Public V put(K key, V value) {// Handle null keysif (key == null)
            returnputForNullKey(value); / / calculatehash
        int hash = hash(key); Int I = indexFor(int I = indexFor(hash, table.length); // Iterate over the table[index] to see if the key already exists. If so, replace the key and return the old valuefor(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                returnoldValue; } } modCount++; // If the key does not already exist in the table, call addEntry. LinkedHashMap overwrites this method addEntry(hash, key, value, i);
        return null;
    }
Copy the code

Let’s look at the addEntry method of LinkedHashMap:

    void addEntry(int hash, K key, V value, int bucketIndex) {// Add an Entry to the HashMap super.addEntry(hash, key, value, bucketIndex); // The removeEldestEntry method returns by defaultfalseJohn = younger = header.after;if(removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); }}Copy the code

The addEntry method of the parent HashMap class is called as follows:

    void addEntry(int hash, K key, V value, int bucketIndex) {// Capacity expansion relatedif((size >= threshold) && (null ! = table[bucketIndex])) { resize(2 * table.length);hash= (null ! = key) ?hash(key) : 0;
            bucketIndex = indexFor(hash, table.length); } // LinkedHashMap is rewritten to createEntry(hash, key, value, bucketIndex);
    }
Copy the code

Here is the code related to capacity expansion, which was covered in the previous HashMap parsing. Here we’re looking at the createEntry method, and the LinkedHashMap is overwritten.

   void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // Add the newly created Entry to the bidirectional list. size++; }Copy the code

Let’s look at the addBefore method for linkedhashMap.Entry:

        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }
Copy the code

When you add a LinkedHashMap to a HashMap, you add the LinkedHashMap to a HashMap and add the LinkedHashMap to a list. The red part is a bidirectional linked list, the black part is a HashMap structure, and the header is an Entry type bidirectional linked list header that does not store data itself.

Entry1 = Entry1; Entry1 = Entry1;


LinkedHashMap structure an element. PNG

When adding another element Entry2, assume index is 15:


LinkedHashMap structure two elements. PNG

When adding another element Entry3, assume index is also 0:


LinkedHashMap structure three elements. PNG


That’s all the LinkedHashMap put is, in general, similar to the HashMap put, except that it adds new entries to the two-way list.

2.6 capacity

In the put method of HashMap, if the number of previous elements exceeds the expansion threshold, the resize method is called as follows:

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash= oldAltHashing ^ useAltHashing; Table transfer(newTable,rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
Copy the code

LinkedHashMap overwrites the transfer method, the data migration, which is implemented as follows:

    void transfer(HashMap.Entry[] newTable, boolean rehashInt newCapacity = newtable.length; int newCapacity = newtable.length; // Iterate through the bidirectional linked list and re-calculate all entries in the bidirectional linked listhashAnd add it to the new tablefor(Entry<K,V> e = header.after; e ! = header; e = e.after) {if (rehash) e.hash = (e.key == null) ? Zero:hash(e.key); int index = indexFor(e.hash, newCapacity); e.next = newTable[index]; newTable[index] = e; }}Copy the code

As you can see, when LinkedHashMap is expanded, the rehash of data is different from that of HashMap.

A HashMap is a one-way linked list that first iterates through the old table and then each element in the old table. After obtaining an Entry, the hash value is recalculated and then stored in the corresponding position of the new table.

LinkedHashMap is a two-way linked list traversed through, taking each Entry, recalculating the hash value, and storing it in the corresponding location of the new table.

In terms of traversal efficiency, traversing bidirectional linked list is more efficient than traversing table, because traversing bidirectional linked list is N times (N is the number of elements); Traversing a table is N+ the number of empty tables (N is the number of elements).

2.7 Reordering of bidirectional linked lists

The previous analysis is mainly about new entries when the current LinkedHashMap does not have the current key. If the key already exists, the value of the Entry is updated. This is the code in the HashMap PUT method:

        for(Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k;if (e.hash == hash&& ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; // reorder e.reordAccess (this);returnoldValue; }}Copy the code

E.recordaccess (this), which depends on the access order, and HashMap is unordered, so the recordAccess method in hashmap.entry is empty. But LinkedHashMap is ordered, and linkedhashmap.entry overwrites the recordAccess method.

void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // If the accessOrder of LinkedHashMap istrueFor example, the accessOrder attribute of the LinkedHashMap used in LruCache istrue
            if(lm.accessOrder) { lm.modCount++; // Remove the updated Entry from the two-way list. Remove (); // Add the updated Entry to the end of the bidirectional list addBefore(lm.header); }}Copy the code

In LinkedHashMap, the updated entries are reordered only when accessOrder is true, i.e. when accessing the order schema. In LinkedHashMap, the updated entries are reordered only when accessOrder is true. In insert order schema, the reordered entries are not reordered.

Here’s an example: Started, HashMap Entry1, Entry2, Entry3, and set the LinkedHashMap to access order is updated Entry1, will put Entry1 is removed from the two-way linked list, and then add Entry1 to two-way chain table footer, However, the storage position of Entry1 in the HashMap structure remains unchanged, as shown in the figure below:


LinkedHashMap reorder. PNG

2.8 the get method

LinkedHashMap rewrites the get method as follows:

Public V get(Object key) {// Call genEntry to getEntry Entry<K,V> e = (Entry<K,V>)getEntry(key);if (e == null)
            returnnull; // If the LinkedHashMap is accessed sequentially, then get will also need to reorder e.reordAccess (this);return e.value;
    }
Copy the code

LinkedHashMap does not override the getEntry method, so it calls the getEntry method of the HashMap. We analyzed the getEntry method of the HashMap in the last article: The hash value is calculated using the key, and then the index stored in the table is calculated based on the hash value. Then the one-way linked list of the table[index] is traversed to compare keys, and Entry is returned if it is found.

Then call the recordAccess method of linkedhashMap.Entry. This method is used in the put process. After the get operation is performed on the LinkedHashMap, reorder the get Entry to the end of the bidirectional linked list.

2.9 Obtaining Data in Traversal Mode

Let’s take a look at how HashMap iterates:


HashMap traversal. PNG

Obviously, the order in which the entries are extracted is different from the order in which the entries are inserted. Since the LinkedHashMap is ordered, how is this implemented? Let’s look at the code for the LinkedHashMap traversal method:

        Map<String, String> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("name1"."josan1");
        linkedHashMap.put("name2"."josan2");
        linkedHashMap.put("name3"."josan3"); // LinkedHashMap does not override this method, calling entrySet in HashMap Set<Entry<String, String>>set = linkedHashMap.entrySet();
        Iterator<Entry<String, String>> iterator = set.iterator();
        while(iterator.hasNext()) {
            Entry entry = iterator.next();
            String key = (String) entry.getKey();
            String value = (String) entry.getValue();
            System.out.println("key:" + key + ",value:" + value);
        }
Copy the code

LinkedHashMap does not override entrySet. Let’s look at entrySet in HashMap, as follows:

public Set<Map.Entry<K,V>> entrySet() {
        return entrySet0();
    }

    private Set<Map.Entry<K,V>> entrySet0() {
        Set<Map.Entry<K,V>> es = entrySet;
        returnes ! = null ? es : (entrySet = new EntrySet()); } private final class EntrySet extends AbstractSet<Map.Entry<K,V>> { public Iterator<Map.Entry<K,V>>iterator() {
            returnnewEntryIterator(); } // extraneous code...... }Copy the code

As you can see, the entrySet method of a HashMap returns an entrySet object.

We get EntrySet calling its iterator method to get the iterator. As you can see from the above code, newEntryIterator is called directly from the iterator method and returns, while LinkedHashMap overwrites the method

    Iterator<Map.Entry<K,V>> newEntryIterator() { 
        return new EntryIterator();
    }
Copy the code

This returns an EntryIterator directly, just as newEntryIterator did in the previous HashMap. They return their own inner classes. Let’s look at the definition of EntryIterator in LinkedHashMap:

    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { 
          returnnextEntry(); }}Copy the code

This class inherits LinkedHashIterator and overwrites the next method; In a HashMap, you inherit a HashIterator. Let’s look at the definition of LinkedHashIterator:

Private abstract class LinkedHashIterator<T> implements Iterator<T> {// by default, the nextEntry returned is the nextEntry <K,V> nextEntry  = header.after; Entry<K,V> lastReturned = null; public booleanhasNext() {
            returnnextEntry ! = header; } Entry<K,V>nextEntry() {
            if(modCount ! = expectedModCount) throw new ConcurrentModificationException();if (nextEntry == header)
                throw new NoSuchElementException();

            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            returne; } // Irrelevant code...... }Copy the code

Instead of looking at the entire class implementation, just know that in LinkedHashMap, Iterator<Entry<String, String>> Iterator = set.iterator(), This code returns an Iterator that inherits LinkedHashIterator, with a different traversal rule than HashIterator.

Next, we loop through while(iterator.hasNext()) to determine if there is a next element. The EntryIterator in LinkedHashMap did not override this method, so hasNext in LinkedHashIterator is still called. As follows:

        public boolean hasNext() {// If the next Entry that should be returned is the head of the bidirectional list // there are two cases: 1. 2. Return to the head after traversing the bidirectional listreturnnextEntry ! = header; }Copy the code

NextEntry represents the nextEntry that should be returned. The default value is header.after, which is the next element in the bidirectional linked list header. When initializing a LinkedHashMap, init is called to initialize an Entry that both before and after point to itself. However, the put process adds the new Entry to the end of the list, so as long as there are elements in the LinkedHashMap, The first call to hasNext will definitely not be false.

We then call the next method to retrieve Entry, which the EntryIterator in LinkedHashMap overwrites as follows:

 public Map.Entry<K,V> next() { 
    return nextEntry(); 
}
Copy the code

It doesn’t override the nextEntry method itself, so it’s still the nextEntry method in the LinkedHashIterator call:

        Entry<K,V> nextEntry() {// Save the Entry that should be returned Entry<K,V> e = lastReturned = nextEntry; // take after of the current Entry that should be returned as the nextEntry that should be returned nextEntry = e.after; // Returns the current Entry that should be returnedreturn e;
        }
Copy the code

So there is no need to find the next one-way list in a HashMap. It starts with the next node of the Entry header, and just takes after of the currently returned Entry as the next node that should be returned. Until the end of the bidirectional list is reached, after is the Entry header of the bidirectional list, at which point hasNext returns false, indicating that there is no next element. The traversal value of LinkedHashMap is as follows:


LinkedHashMap traversal. PNG


Entry1, Entry2… Entry6. As it turns out, the LinkedHashMap is ordered and the order is guaranteed by a two-way linked list.

2.10 the remove method

LinkedHashMap does not provide the remove method, so the remove method of HashMap is called as follows:

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash= (key == null) ? Zero:hash(key);
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while(e ! = null) { Entry<K,V> next = e.next; Object k;if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k)))) { modCount++; size--;if (prev == e)
                    table[i] = next;
                elseprev.next = next; // linkedhashmap.entry overwrites the method e.recordremoVal (this);return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }
Copy the code

In the last HashMap article, we examined the remove process, which essentially disreferences you from other objects. For example, if the deleted Entry is at the head of a one-way linked list, place its next at the head so that it is not referenced. If it is not in the header and is referenced by the next of another Entry, make the next of the previous Entry point to its own Next, and it is not referenced.

In Hashmap.entry the recordRemoval method is an empty implementation, but linkedhashmap.entry overwrites it as follows:

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }
Copy the code

This is to delete the Entry from the bidirectional list, that is, to disconnect the Entry to be deleted from the reference of other objects by after and before.

So, the remove operation of LinkedHashMap. Remove it from the table first, that is, remove it from the table or other objects referenced by next, and remove it from the bidirectional list as well, and remove the other corresponding references to it by after and before.

3 Structure comparison of HashMap and LinkedHashMap

Let’s look at the structure of HashMap and LinkedHashMap. LinkedHashMap is basically a HashMap with a bidirectional list to maintain order.


Structure of a HashMap. PNG

The structure of LinkedHashMap. PNG

4 LinkedHashMap in Android

When using images in Android, LruCacha is generally used to do the memory cache of images, which uses LinkedHashMap to realize the storage.

public class LruCache<K, V> {
    private final LinkedHashMap<K, V> map;
    public LruCache(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0"); } this.maxSize = maxSize; // Notice the third argument, accessOrder, wheretrueThis. Map = new LinkedHashMap<K, V>(0, 0.75f,true);
    }
Copy the code

As mentioned earlier, accessOrder is true to indicate that the LinkedHashMap is the accessOrder. When you get and put an Entry from an existing LinkedHashMap, the Entry is moved to the end of the bidirectional list (in fact, it is deleted first and then inserted). Let’s take the LruCache put method as an example:

    public final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null"); } V previous; Synchronized (this) {putCount++; size += safeSizeOf(key, value); previous = map.put(key, value);if (previous != null) {
                size -= safeSizeOf(key, previous);
            }
        }

        if(previous ! = null) { entryRemoved(false, key, previous, value); } // defragment the memory to see if we need to remove the element trimToSize(maxSize) from the LinkedHashMap;return previous;
    }
Copy the code

As mentioned earlier, HashMap is thread unsafe, and LinkedHashMap is thread unsafe as well. Therefore, synchronized is used first when the LinkedHashMap PUT method is called.

We care most about the last line of code, where maxSize is the maximum cache size we set for LruCache. Let’s look at the method:

    /**
     * Remove the eldest entries until the total of remaining entries is at or
     * below the requested size.
     *
     * @param maxSize the maximum size of the cache before returning. May be -1
     *            to evict even 0-sized elements.
     */
    public void trimToSize(int maxSize) {
        // whileAn infinite loop until the current cache size is less than or equal to the maximum cacheable sizewhile (true) { K key; V value; Synchronized (this) {synchronized (this) {if(size < 0 || (map.isEmpty() && size ! = 0)) { throw new IllegalStateException(getClass().getName() +".sizeOf() is reporting inconsistent results!"); } // If the current size of the cache is less than or equal to the maximum cacheable size, return // without removing the data in the LinkedHashMapif (size <= maxSize || map.isEmpty()) {
                    break; Entry<K, V> toEvict = map.entryset ().iterator().next(); key = toEvict.getKey(); value = toEvict.getValue(); // Remove the currently removed Entry map.remove(key); Size -= safeSizeOf(key, value); evictionCount++; } entryRemoved(true, key, value, null); }}Copy the code

As you can see from the comments, this method continually removes elements from the LinkedHashMap header until the current cache size is less than or equal to the maximum cacheable size.

As we know from the previous reordering, both put and get operations on LinkedHashMap move the Entry to the end of the bidirectional list, while removal starts with map.entryset ().iterator().next(). That is, after the header of the bidirectional linked list, which meets the requirements of the LRU algorithm.

The following figure shows the delete, add, get/put existing Entry operations in the LinkedHashMap. Red indicates the initial state. Purple indicates that Entry1 can only be removed if the cached image size exceeds the maximum cacheable size. Blue indicates that Entry3 has been get/put and moved to the end of the two-way linked list. Insert to the end of a bidirectional linked list (regardless of position in the HashMap for now)


The Lru LinkedHashMap. PNG

5 concludes

  1. LinkedHashMap is derived from HashMap and is based on HashMap and bidirectional linked lists.
  2. A HashMap disorder; The LinkedHashMap is ordered and can be divided into insert order and access order. In access order, both put and GET operations on existing entries move the Entry to the end of the bidirectionally linked list.
  3. LinkedHashMap accesses data in the same way that HashMap uses Entry[], two-way lists only for order.
  4. LinkedHashMap is thread unsafe.





Author: Yi Xu jia


Link: https://www.jianshu.com/p/8f4f58b4b8ab


Source: Jane Book


Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.