A, structure,

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

LinkedHashMap inherits from HashMap, but the difference is that when traversing, LinkedHashMap can be traversed in the order of addition, while HashMap can be traversed in the order of addition according to the previous combing, while HashMap can be traversed in the order of addition according to array & linked list, but not in the order of addition. The key here is the LinkedHashMap to wait for the Node Node to add two variables before&After to indicate the nodes before and after the Node. When adding, deleting, modifying, and searching, the corresponding nodes are collated through the three empty methods corresponding to HashMap. The collation of this part is similar to LinkeList that we combed before.

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) {}void afterNodeInsertion(boolean evict) {}void afterNodeRemoval(Node<K,V> p) {}Copy the code

Second, the variable

1, the head,

transient LinkedHashMap.Entry<K,V> head;
Copy the code

This represents the head node.

2, tail

transient LinkedHashMap.Entry<K,V> tail;
Copy the code

End nodes.

3, accessOrder

final boolean accessOrder;
Copy the code

This is the order used for iterating through: true indicates access order, false indicates insert order. For example, the putVal method of HashMap may already have this element when it is added, so this time it is overwriting the original value. This is an access order. If the element is not already present, it is an insert order. In the accessOrder accessOrder = true, the node is inserted back from its original position. If it’s an insert order, it doesn’t reposition the element to the end, where it was before.

3. Construction method

1, LinkedHashMap(int initialCapacity, float loadFactor)

public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
Copy the code

It is initialized by a direct call to the super method, and accessOrder defaults to false, indicating insertion order.

2, the LinkedHashMap (int initialCapacity)

public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
Copy the code

The parent method of the call.

3, the LinkedHashMap ()

public LinkedHashMap(a) {
        super(a); accessOrder =false;
    }
Copy the code

4, a HashMap (Map <? extends K, ? extends V> m)

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(a); accessOrder =false;
    putMapEntries(m, false);
}
Copy the code

These constructors, which can be seen as the parent of the call, basically set accessOrder to the default false.

Inner class

1, Entry

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); }}Copy the code

Inherit hashmap. Node by adding before&After nodes to the inheritance to indicate the previous and next nodes of the Node, thus traversing in insertion order.

2, LinkedKeySet

final class LinkedKeySet extends AbstractSet<K> {
    public final int size(a)                 { return size; }
    public final void clear(a)               { LinkedHashMap.this.clear(); }
    public final Iterator<K> iterator(a) {
        return new LinkedKeyIterator();
    }
    public final boolean contains(Object o) { return containsKey(o); }
    public final boolean remove(Object key) {
        return removeNode(hash(key), key, null.false.true) != null; }... }Copy the code

There are no major differences with HashMap.

3, LinkedValues

final class LinkedValues extends AbstractCollection<V> {
    public final int size(a)                 { return size; }
    public final void clear(a)               { LinkedHashMap.this.clear(); }
    public final Iterator<V> iterator(a) {
        return new LinkedValueIterator();
    }
    public final boolean contains(Object o) { returncontainsValue(o); }... }Copy the code

Other linkedentrySets are not going to be mentioned.

5, LinkedHashIterator

1) Structure & Member variable & constructor

abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next;
    LinkedHashMap.Entry<K,V> current;
    int expectedModCount;

    LinkedHashIterator() {
        next = head;
        expectedModCount = modCount;
        current = null;
    }
Copy the code

This is the traversal iterator for the LinkedHashMap implementation. Next represents the next node, and current represents the current iteration node. In HashMap, we need to go through the array of numbers in order to see which index is the first that is not empty before assigning it to next.

2) Method

public final boolean hasNext(a) {
    returnnext ! =null;
}

final LinkedHashMap.Entry<K,V> nextNode(a) {
    LinkedHashMap.Entry<K,V> e = next;
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
    if (e == null)
        throw new NoSuchElementException();
    current = e;
    next = e.after;
    return e;
}

public final void remove(a) {
    Node<K,V> p = current;
    if (p == null)
        throw new IllegalStateException();
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
    current = null;
    removeNode(p.hash, p.key, null.false.false);
    expectedModCount = modCount;
}
Copy the code

As you can see, nextNode is next by taking e, the after node of Next, which is also different from the HashMap traversal.

6, LinkedKeyIterator

final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next(a) { returnnextNode().getKey(); }}Copy the code

Iterator iterates the key of a node.

7, LinkedValueIterator

final class LinkedValueIterator extends LinkedHashIterator
    implements Iterator<V> {
    public final V next(a) { returnnextNode().value; }}Copy the code

Iterator iterates the value of a node.

8 LinkedEntryIterator.

final class LinkedEntryIterator extends LinkedHashIterator
    implements Iterator<Map.Entry<K.V>> {
    public final Map.Entry<K,V> next(a) { returnnextNode(); }}Copy the code

Traverse on the Node (Entry | Node), you can see its just nextNode packing method for the next.

These are similar to the previous HashMap.

Five, methods,

AfterNodeAccess&afterNodeInsertion & visting emoval

1, afterNodeInsertion (Boolean evict)

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if(evict && (first = head) ! =null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null.false.true); }}Copy the code

This is called after the element is passed in, for example:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {... afterNodeInsertion(evict);return null;
}
Copy the code

And then this method has another function, which is to remove the first element added, which is the head node. There are two decisions to remove it: the removeEldestEntry method, which always returns false on LinkedHashMap that does not remove the first node

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

For example, if you want to store 100 more nodes in the Map, you can override this method to determine whether to delete the first node.

> 2, afterNodeRemoval (Node < K, V, e)

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
Copy the code

This method is called after the delete operation, for example:

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {... afterNodeRemoval(node);returnnode; . }Copy the code

Its operation is similar to that of LinkedList. Join E (the element deleted this time), connect its front node with its back node, and delete e node itself.

3, afterNodeAccess (Node < K, V > e)

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if(accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after =null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if(a ! =null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else{ p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the code

Here is the use of accessOrder we explained earlier, with calls such as:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {...if(e ! =null) { // existing mapping for key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue ==null)
                e.value = value;
            afterNodeAccess(e);
            returnoldValue; }... }Copy the code

AfterNodeAccess is called when the original node E already exists. AccessOrder is also true, indicating that the accessOrder is used. I move this node E to the back. In the operation, connect the front and back nodes of P, i.e. E, and then set p to tail = p.

4, newNode(int hash, K key, V value, Node<K,V> e)

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<>(hash, key, value, e);
    linkNodeLast(p);
    return p;
}
Copy the code

Here is the new node to create the LinkedHashMap. The main thing is to call the linkNodeLast method to add a new node to the end.

5, linkNodeLast (LinkedHashMap. Entry > < K, V p)

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; }}Copy the code

Set p to the tail node, then set the tail node to the front node of P, and p to the rear node of tail.

5, the get (Object key)

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
Copy the code

If accessOrder is true, the queried node will be moved to the back. AfterNodeInsertion method and removeEldestEntry method to delete nodes in the least recently used method.

6, containsValue

public boolean containsValue(Object value) {
    for(LinkedHashMap.Entry<K,V> e = head; e ! =null; e = e.after) {
        V v = e.value;
        if(v == value || (value ! =null && value.equals(v)))
            return true;
    }
    return false;
}
Copy the code

If this value is included, you can see that it is traversed by head and e.footer.