LinkedHashMap

1、概述

LinkedHashMap是在HashMap的基础上维护一个双向链表来记录元素添加的顺序，使得遍历的结果遵从插入的顺序，所以LinkedHashMap是有序的。
下面拿哈希表中一个桶中的红黑树作为示例：
假设添加的顺序是：37、21、31、41、97、95、52、42、83

image.png
图中只画出了next的指向，没有画出prev的指向，但是使用的双向链表来维护元素添加的顺序。
很明显需要在元素的添加和删除时维护双向链表中的元素。

2、LinkedNode类

由于是双向链表所以要维护prev和next指针，所以这里创建一个Node的子类LinkedNode，而且LinkedHashMap类中还要维护first和last

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

    private LinkedNode<K, V> first;
    private LinkedNode<K, V> last;
    
    private static class LinkedNode<K, V> extends Node<K, V> {
        LinkedNode<K, V> prev;
        LinkedNode<K, V> next;

        public LinkedNode(K key, V value, Node<K, V> parent) {
            super(key, value, parent);
        }
    }
}

3、put()

LinkedHashMap是继承HashMap的，添加元素使用HashMap的添加逻辑即可，然后在节点创建时维护节点的next和prev即可。在HashMap中定义一个createNode()方法，LinkedHashMap中实现如下：

/**
 * 添加元素时维护链表中元素的next和prev属性
 */
@Override
protected Node<K, V> createNode(K key, V value, Node<K, V> parent) {
    LinkedNode<K, V> node = new LinkedNode(key, value, parent);
    if (first == null)
        first = last = node;
    else {
        last.next = node;
        node.prev = last;
        last = node;
    }
    return node;
}

4、remove()

在删除节点时，只需要将链表中对应的节点删除即可。当删除的节点度为2时，需要注意最终删除的节点的前驱节点或后继节点，在度为2时需要交换一下要删除的节点和真实删除节点的位置，然后再将对应的节点删除即可。注意：这里并不是交换树中两个点的位置，只是交互在双链表中的位置。

image.png
image.png
具体的实现如下：

@Override
protected void afterRemove(Node<K, V> willNode, Node<K, V> node) {
    LinkedNode<K, V> node1 = (LinkedNode<K, V>) willNode;
    LinkedNode<K, V> node2 = (LinkedNode<K, V>) node;
    if (node1 != node2) {
        // 交换linkedWillNode和linkedRemovedNode在链表中的位置
        // 交换prev
        LinkedNode<K, V> temp = node1.prev;
        node1.prev = node2.prev;
        node2.prev = temp;

        if (node1.prev != null)
            node1.prev.next = node1;
        else
            first = node1;

        if (node2.prev != null)
            node2.prev.next = node2;
        else
            first = node2;

        // 交换next
        temp = node1.next;
        node1.next = node2.next;
        node2.next = temp;

        if (node1.next != null)
            node1.next.prev = node1;
        else
            last = node1;

        if (node2.next != null)
            node2.next.prev = node2;
        else
            last = node2;
    }

    LinkedNode<K, V> prev = node2.prev;
    LinkedNode<K, V> next = node2.next;
    if (prev != null)
        prev.next = next;
    else
        first = next;

    if (next != null)
        next.prev = prev;
    else
        last = next;
}

5、其他方法

• 1、相比于HashMap增加了一个双向链表，所以在清空时需要做如下修改

@Override
public void clear() {
    super.clear();
    first = null;
    last = null;
}

• 2、在HashMap中遍历需要将哈希表中所有红黑树取出，并遍历红黑树的每一个元素，而LinkedHashMap已经使用双向链表维护了元素插入的顺序，所以这里修改下遍历方式

/**
 * HashMap中的遍历是遍历哈希表取出每一个桶中的红黑树 然后再遍历红黑树中的每一个节点，对于LinkedHashMap来说完全可以直接遍历链表即可
 */
@Override
public void traversal(Visitor<K, V> visitor) {
    if (visitor == null)
        return;
    LinkedNode<K, V> node = first;
    while (node != null) {
        visitor.visitor(node.key, node.value, node.color);
        node = node.next;
    }
}