LinkedHashMap source code read briefly

LinkedHashMap source code read briefly

1. LinkedHashMap descends from HashMap, which has all the features of HashMap.

2. In fact, LinkedHashMap is implemented using a combination of two-way linked lists and hash tables. “Linked” in LinkedHashMap actually refers to bidirectional Linked lists, not “hash conflict resolution using Linked lists”.

3. LinkedHashMap supports traversal of data not only in insert order, but also in access order. This is done by setting the accessOrder property to true. That is, it is itself a caching system that supports LRU cache obsolescence.

Query, insert, delete methods.

LinkedHashMap inherits from HashMap, which is implemented using hash tables, so LinkedHashMap adds a two-way linked list to HashMap to store data. So where was it added? We analyze get, PUT, and remove methods one by one.

First LinkedHashMap variable definition for bidirectional linked list:

/**
 * The head (eldest) of the doubly linked list.
 */
transient LinkedHashMapEntry<K,V> head;

/**
 * The tail (youngest) of the doubly linked list.
 */
transient LinkedHashMapEntry<K,V> tail;
Copy the code

LinkedHashMap# get (Object key) method

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

LinkedHashMap rewrites the Get (Object key) method in HashMap by adding accessOrder operations. The core lookup is still done through methods in the HashMap.

LinkedHashMap#put(K key, V value) method

LinkedHashMap completely inherits HasMap’s get(K key, V value) method without any changes. How does it add new data to the bidirectional list?

In HashMap, the put method calls the putVal method as follows:

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null) // Comment a TAB [I] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash&& ((k = p.key) == key || (key ! = null && key.equals(k)))) e = p;else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if((e = p.ext) == null) {hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash&& ((k = e.key) == key || (key ! = null && key.equals(k))))break; p = e; }}if(e ! = null) { // existing mappingfor key
            V oldValue = e.value;
            if(! onlyIfAbsent || oldValue == null) e.value = value; // afterNodeAccess(e);return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}
Copy the code

As shown above, when inserting data, the HashMap first looks to see if the data already exists. If not, the newNode method is called to create a new element; If it does, the afterNodeAccess method is called. Note that both newNode and afterNodeAccess have been overwritten by LinkedHashMap to do the extra work of adding data to the two-way list.

To explain the details: Note 1: Here a node is created and inserted into an array. In addition, the newNode method is overwritten by LinkedHashMap, which adds node to the bidirectional list as well as new. LinkedHashMap#newNode():

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

LinkedHashMap#linkNodeLast(): links node to the end of the two-way list.

// link at the end of list
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
    LinkedHashMapEntry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else{ p.before = last; last.after = p; }}Copy the code

Note 2: Same as above.

Note 3: The afterNodeAccess method in HashMap is clearly defined. The following three methods are specifically for LinkedHashMap to override.

 // 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

Take a look at the afterNodeAccess method in LinkedHashMap, which moves nodes to the end of the list.

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMapEntry<K,V> last;
    if(accessOrder && (last = tail) ! = e) { LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<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

LinkedHashMap# remove (Object key) method

LinkedHashMap is also inherited from

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false.true)) == null ?
        null : e.value;
}
Copy the code

LinkedHashMap# removeNode method:

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if((tab = table) ! = null && (n = tab.length) > 0 && ...if(node ! = null && (! matchValue || (v = node.value) == value || (value ! = null && value.equals(v)))) { ... afterNodeRemoval(node);returnnode; }}return null;
}
Copy the code

As you can see, the visting emoval method was empty in the HashMap and overwritten in the LinkedHashMap. Remove the Node element from the two-way list

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMapEntry<K,V> p =
        (LinkedHashMapEntry<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

Conclusion:

The bottom layer of HashMap is implemented with arrays. We can use hash tables to achieve fast access and access to elements, but the order of elements can not be guaranteed. LinkedHashMap adds elements to a two-way linked list on the basis of HashMap, so that elements can be accessed quickly and in order at the same time. Additionally, LinkedHashMap is a caching system by nature that supports an LRU cache elimination strategy.

Reference: time.geekbang.org/column/arti…