LinkedHashMap is a subclass of HashMap, so it also has many features of HashMap. The difference is that LinkedHashMap also maintains a two-way linked list to ensure that the traversal order through Iterator is consistent with the insertion order. In addition, it supports Access Order, which is sorted according to the order in which the elements are accessed, on which the LRUCache underlying layer, as we know it, depends. The following points need our attention in the document:

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map.

A special LinkedHashMap(int,float,boolean) constructor is provided to create a linked hash map whose order of iteration is the order in which its entries were last accessed, from least-recently accessed to most-recently (access-order). This kind of map is well-suited to building LRU caches.

The removeEldestEntry(Map.Entry) method may be overridden to impose a policy for removing stale mappings automatically when new mappings are added to the map.

Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for this class than for HashMap, as iteration times for this class are unaffected by capacity.

Next, we start with the constructor and member variables to analyze their implementation.

Constructor and member variables

Member variables

Before analyzing member variables, let's look at the structure of their storage elements.

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

This Entry has been referenced in HashMap, mainly to enable LinkedHashMap to support tree. Here it is used to store elements.

// The head of a two-way linked list, which is also the oldest element when used as an AccessOrder
transient LinkedHashMap.Entry<K,V> head;

// The end of a two-way linked list is also the latest element when used as an AccessOrder
transient LinkedHashMap.Entry<K,V> tail;

// true is the order of access and false is the order of insertion
final boolean accessOrder;

Constructor

We only focus on one of the constructors for LinkedHashMap, and the others are similar to HashMap, except that the accessOrder is set to false. As mentioned in the document above, initial Capacity is not as important as in HashMap, because linked lists do not need to declare enough space first, as arrays do. The following constructor supports access order.

public LinkedHashMap(int initialCapacity,
                    float loadFactor,
                    boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

Important method

LinkedHashMap does not implement a whole set of methods of adding, deleting and modifying, but is implemented by copying several methods defined by HashMap in the process. Unfamiliar with this can be seen at the end of the article on HashMap analysis, or compared with the source code of HashMap.

Insert an element

When HashMap inserts, it calls newNode to create a new node, or replacementNode to replace the value. There are also two corresponding methods for tree formation: new TreeNode and replacementTreeNode. After completion, the afterNodeInsertion method is also called, which allows us to do something after the insertion is completed, and the default is empty implementation.

To facilitate analysis, we will compare the implementation of HashMap with that of LinkedHashMap to find out how it works.

// Implementation in HashMap
Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
    return new Node<>(hash, key, value, next);
}

// Implementation of LinkedHashMap
Node<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;
}

// Implementation in HashMap
Node<K, V> replacementNode(Node<K, V> p, Node<K, V> next) {
    return new Node<>(p.hash, p.key, p.value, next);
}

// Implementation of LinkedHashMap
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
    LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
    LinkedHashMap.Entry<K,V> t =
        new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
    transferLinks(q, t);
    return t;
}

// New TreeNode and replacementTreeNode and similar

From the above comparison, we can see that LinkedHashMap calls linkNodeLast when it is added, and transferLinks when it is replaced. The following are the implementations of these two methods.

// That's to hang the element at the end of the chain.
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

// Replacing src with dst
private void transferLinks(LinkedHashMap.Entry<K,V> src,
                            LinkedHashMap.Entry<K,V> dst) {  
    LinkedHashMap.Entry<K,V> b = dst.before = src.before;
    LinkedHashMap.Entry<K,V> a = dst.after = src.after;
    if (b == null)
        head = dst;
    else
        b.after = dst;
    if (a == null)
        tail = dst;
    else
        a.before = dst;
}

Finally, let's look at what afterNode Insertion has done.

// As evict said in HashMap, representing false is the creation phase
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // Not the Creation Phase
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        // Automatically delete the oldest element, the head element
        removeNode(hash(key), key, null, false, true);
    }
}

RemoveEldest Entry is a method that requires duplication when you want to automatically delete the oldest element when inserting it. Its default implementation is as follows:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

query

Because access order is supported, the method of getting elements is also different from HashMap. Now let's look at its implementation:

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        // Data is accessed and needs to be moved to the end
        afterNodeAccess(e);
    return e.value;
}

The getNode method is implemented in HashMap, so it wraps up the HashMap method and adds an afterNodeAccess, which is implemented as follows:

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    // e element is not at the end
    if (accessOrder && (last = tail) != e) {
        // p is e, b is the former element, a is the latter element
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        // e is at the end, so there is no after
        p.after = null;

        // Get rid of e and connect b with a.
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;

        //Connect e to the end
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

That's all for LinkedHashMap. Other Iterator content is similar to Collection, so you can check the source code if you're interested.

Thank you for seeing it. If you can help me, please give me a compliment.

More experience and technology are welcome to come and learn together. A Little Classroom - Online Learning Platform for Dreams http://www.yidiankt.com/

[Pay attention to the public number and reply to "1" for free - [java Core Knowledge Points]

QQ discussion group: 616683098

QQ: 3184402434

Students who want to study in depth can study and discuss with QQ ~and have a full set of resources to share, experience to explore, wait for you!