Analysis of LinkedHashMap in simple terms (pictures and text)

1. Summary

In the first chapter of the collection series, we learned that the implementation class of Map has HashMap, LinkedHashMap, TreeMap, IdentityHashMap, WeakHashMap, Hashtable, Properties, etc.

#This article mainly discusses the implementation of LinkedHashMap from the data structure and algorithm level.

(Recommended learning: Java video tutorial)

2. Introduction

LinkedHashMap can be considered as HashMap LinkedList. It not only uses HashMap to operate the data structure, but also uses LinkedList to maintain the order of inserted elements. Internally, it uses a doubly-linked list (doubly-linked list) to All elements (entries) are connected.

LinkedHashMap inherits HashMap, allowing elements with a null key to be put in, and elements with a value being null to be inserted. As can be seen from the name, this container is a mixture of LinkedList and HashMap, which means that it meets certain characteristics of both HashMap and LinkedList. LinkedHashMap can be regarded as a HashMap enhanced with Linked list.

Open the LinkedHashMap source code and you can see the three main core attributes:

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

    /**双向链表的头节点*/
    transient LinkedHashMap.Entry<K,V> head;

    /**双向链表的尾节点*/
    transient LinkedHashMap.Entry<K,V> tail;

    /**
      * 1、如果accessOrder为true的话，则会把访问过的元素放在链表后面，放置顺序是访问的顺序
      * 2、如果accessOrder为false的话，则按插入顺序来遍历
      */
      final boolean accessOrder;
}

LinkedHashMap In the initialization phase, the default is to traverse in the insertion order

public LinkedHashMap() {
        super();
        accessOrder = false;
}

The Hash algorithm used by LinkedHashMap and The same as HashMap, but the difference is that it redefines the element Entry saved in the array. In addition to saving the reference of the current object, the Entry also saves the reference of its previous element before and the next element after, thus in the hash table. Basically, a two-way linked list is formed.

The source code is as follows:

static class Entry<K,V> extends HashMap.Node<K,V> {
        //before指的是链表前驱节点，after指的是链表后驱节点
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
}

It can be seen intuitively that the data inserted at the head of the doubly linked list is the entry of the linked list, and the iterator traversal direction is from the linked list starts from the head of the linked list and ends at the end of the linked list.

In addition to preserving the iteration order, this structure has another advantage: when iterating LinkedHashMap, you don’t need to traverse the entire table like HashMap, but only need to directly traverse the header pointed to. A doubly linked list is sufficient, which means that the iteration time of LinkedHashMap is only related to the number of entries and has nothing to do with the size of the table.

3. Introduction to common methods

3.1. Get method

The get method returns the corresponding value according to the specified key value . The process of this method is almost exactly the same as the HashMap.get() method. By default, it is traversed in insertion order.

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;
}

If accessOrder is true, the visited elements will be placed at the end of the linked list, and the placement order is the order of access

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;
        }
}

Test case:

public static void main(String[] args) {
        //accessOrder默认为false
        Map<String, String> accessOrderFalse = new LinkedHashMap<>();
        accessOrderFalse.put("1","1");
        accessOrderFalse.put("2","2");
        accessOrderFalse.put("3","3");
        accessOrderFalse.put("4","4");
        System.out.println("acessOrderFalse："+accessOrderFalse.toString());
        
        //accessOrder设置为true
        Map<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderTrue.put("1","1");
        accessOrderTrue.put("2","2");
        accessOrderTrue.put("3","3");
        accessOrderTrue.put("4","4");
        accessOrderTrue.get("2");//获取键2
        accessOrderTrue.get("3");//获取键3
        System.out.println("accessOrderTrue："+accessOrderTrue.toString());
}

Output results:

acessOrderFalse：{1=1, 2=2, 3=3, 4=4}
accessOrderTrue：{1=1, 4=4, 2=2, 3=3}

3.2. Put method

The put(K key, V value) method adds the specified key, value pair to the map. This method first calls the insertion method of HashMap, and also searches the map to see if it contains the element. If it is included, it returns directly. The search process is similar to the get() method; if it is not found, the element is inserted into the collection.

/**HashMap 中实现*/
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

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)
            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.next) == null) {
                        p.next = newNode(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 mapping for 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;
}

Overridden methods in LinkedHashMap

// 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);
    // 将 Entry 接在双向链表的尾部
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    // last 为 null，表明链表还未建立
    if (last == null)
        head = p;
    else {
        // 将新节点 p 接在链表尾部
        p.before = last;
        last.after = p;
    }
}

3.3, remove method

remove(Object key) The function is to delete the entry corresponding to the key value. The implementation logic of this method is mainly based on HashMap. First, find the entry corresponding to the key value, and then delete the entry (modify the corresponding reference of the linked list). The search process is similar to the get() method. Finally, The overridden method in LinkedHashMap will be called and deleted!

/**HashMap 中实现*/
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

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 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode) {...}
            else {
                // 遍历单链表，寻找要删除的节点，并赋值给 node 变量
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode) {...}
            // 将要删除的节点从单链表中移除
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);    // 调用删除回调方法进行后续操作
            return node;
        }
    }
    return null;
}

The afterNodeRemoval method overridden in LinkedHashMap

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    // 将 p 节点的前驱后后继引用置空
    p.before = p.after = null;
    // b 为 null，表明 p 是头节点
    if (b == null)
        head = a;
    else
        b.after = a;
    // a 为 null，表明 p 是尾节点
    if (a == null)
        tail = b;
    else
        a.before = b;
}

##4. Summary

LinkedHashMap inherits from HashMap. Most of the functional features are basically the same. The only difference between the two is that LinkedHashMap uses a doubly-linked list to connect all entries based on HashMap. This is to ensure that the iteration order of elements is the same as the insertion order. .

The main part is exactly the same as HashMap, with the addition of header pointing to the head of the doubly linked list, and tail pointing to the tail of the doubly linked list. The default iteration order of the doubly linked list is the insertion order of the entry.

Эта статья взята с китайского веб-сайта PHP, колонка Java Tutorial, добро пожаловать на обучение!

The above is the detailed content of Analysis of LinkedHashMap in simple terms (pictures and text). For more information, please follow other related articles on the PHP Chinese website!