签名

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

可以看到LinkedHashMapHashMap的子类。
LinkedHashMap方法很少,大部分都复用的父类的方法。

原理

继承自HashMap,一些方法直接使用的父类的方法,比如put等,底层是基于双向链表实现的,
除基本的HashMap结构外,他自己还维护了一个双向链表,来维持Key的顺序。

<注>:

默认情况下,LinkedHashMap 是按插入顺序维护链表。不过我们可以在初始化 LinkedHashMap,指定 accessOrder 参数为 true,即可让它按访问顺序维护链表。访问顺序的原理上并不复杂,当我们调用get/getOrDefault/replace等方法时,只需要将这些方法访问的节点移动到链表的尾部即可。相应的方法是:afterNodeAccess

注释解读

LinkedHashMap 是一种实现了 Map 接口的哈希表和链表结构。与 HashMap 不同,LinkedHashMap 通过双向链表连接所有条目,定义了迭代顺序(通常是插入顺序)。它可以产生一个与原始映射相同顺序的副本,适用于需要保持顺序的场景。
LinkedHashMap 提供了按访问顺序排序的特殊构造方法,适用于构建 LRU 缓存。通过 put、putIfAbsent、get、compute 等方法访问条目会影响访问顺序。它提供了所有的 Map 操作,并允许空元素。
该实现的性能接近 HashMap,但迭代集合视图的性能优于 HashMap。LinkedHashMap 的性能受初始容量和负载因子参数影响,但迭代时间不受容量的影响。
LinkedHashMap 不是线程安全的,如果多个线程并发访问并进行结构性修改,需要外部同步。它的迭代器是快速失败的,可以及时检测到并发修改。

在先前的版本中,LinkedHashMap 的内部结构略有不同。由于超类 HashMap 现在在某些节点上使用了树结构,类 LinkedHashMap.Entry 现在被视为中间节点类,也可以转换为树形式。当前上下文中,LinkedHashMap.Entry 这个类名在几个方面都具有一定的混淆性,但无法更改。否则,尽管它没有在此包之外导出,但已知某些现有的源代码依赖于对 removeEldestEntry 方法调用的符号解析角落情况规则,以抑制由于模糊使用而导致的编译错误。因此,为了保持名称不变以保持编译的兼容性。
节点类的更改还要求使用两个字段(head、tail)来维护双向链表的 before/after 列表,而不是指向头节点的指针。这个类以前还使用了不同风格的回调方法来处理访问、插入和删除操作。

基本属性及节点

LinkedHashMap节点继承自HashMapNode,还多了 before, after;用来指向它的前一个节点和后一个节点。

    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    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);
        }
    }
    /**
     * The head (eldest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> head;    // 双向链表头结点

    /**
     * The tail (youngest) of the doubly linked list.
     */
    transient LinkedHashMap.Entry<K,V> tail;    // 双向链表尾结点

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     *
     * @serial
     */
    final boolean accessOrder; // true:访问顺序 false:插入顺序

代码

put

没有进行重写,复用了父类的putVal,这里你会有疑问,为啥我复用父类的put却能保持顺序?
其实他是重写了newNode方法

hashmap newNode

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

linkedHashMap newNode

看到差别了吧,他是吧这个新来的新兵蛋子放入了链表尾部

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

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

remove

remove也是使用的父类的remove,但不同的是调用了afterNodeRemoval方法,这个方法在HashMap中是空实现, 会先删除这个在HashMap中的节点之后,删除双向链表中的节点。

HashMap afterNodeRemoval

void afterNodeRemoval(Node<K,V> p) { }

LinkedHashMap afterNodeRemoval

    void afterNodeRemoval(Node<K,V> e) { // unlink 调用的hashmap的afterNodeRemoval, 这个在hashmap中是一个空实现
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // p=e; b=p.before; a=p.after    eg:  b<=> p <=>a
        p.before = p.after = null;
        if (b == null)  // b是空,则头结点就为a,因为p移除了
            head = a;
        else            // b的后一个是a,就正常情况
            b.after = a;
        if (a == null)  // a==null,和第一个if判断的是相反的,这个判断的是结尾
            tail = b;   // 结尾赋值
        else
            a.before = b;   // 连接双向链表
    }

get

get方法在子类中被重写了,他调用了HashMap中的getNode方法

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)      // 调用了hashmap的getNode方法!
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {        // 判断数组不为空,并且找到了这个元素的坑位,==永远检查第一个节点,不能为空鸭==
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))    // 如果第一个就是,那运气爆棚啊
                return first;
            if ((e = first.next) != null) {                 // 判断他的下一个节点是不是空,不是的话看是链表还是红黑树
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {                                        // 说明是链表
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))    // 这里的判断狠巧妙,巧妙的避免了空指针
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;                                        // 都没有找到,小hashmap失望极了,呜呜呜~~~
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {        // last是尾结点
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // b <-> p <-> a
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;   // TODO:这个分支一般进不来,不知道有什么用,如果进来的话,那就和方法开头的if冲突了,就说明e是tail了
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

afterNodeInsertion

这个方法平常调用是不会进到if分支的,因为removeEldestEntry返回的是false
在特定需求场景下,比如使得链表固定长度并保持最新插入当节点数据,可以通过重写removeEldestEntry 来实现:

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

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

感悟

哎我去,这代码写的,太强了,恰当其时的hook,几乎完美的继承,没有冗余,却为后续开发留足了接口!!


参考文献

LinkedHashMap(JDK1.8)源码解析
LinkedHashMap 按插入/访问迭代排序


0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

ICP备案号: 辽ICP备20003309号