深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

LinkedHashMap 内部通过双向链表来维护节点的顺序, 可以按插入先后顺序来获取节点的值。 在实现上,它是继承于HashMap的,覆写了其中的部分方法。

1. LinkedHashMap 的构造方法

深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

构造方法基本是和HashMap的方法类似,它的成员变量增加了头节点指针,尾节点指针,是否按访问顺序迭代 这三个成员变量。

/**
     * 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);
        }
    }
 
    private static final long serialVersionUID = 3801124242820219131L;
 
    /**
     * 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
     */
    //是否按访问顺序来迭代,默认为false,也就是默认按插入先后顺序来迭代节点
    final boolean accessOrder;
复制代码

它的Entry<K, V>节点是继承于HashMap的Node, 增加了before指针和after指针, 用于实现双向链表。继承关系如下所示。

深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

2.   链表节点的插入分析

首先调用的也是HashMap的Put相关方法, 只是重写了里面的newNode方法,创建的节点是自身定义的带有双向指针的节点,然后调用了linkNodeLast(p)方法,把节点插入到链表的尾部。

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;
 }
复制代码

然后插入节点,重新修改节点的前驱和后继指针指向。

// link at the end of list
   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;
       }
   }
复制代码
深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

3.   节点的删除

删除节点也是调用HashMap的remove相关方法, 只是在链表或者红黑树中删除节点后,要调整双向链节点的前驱和后继节点的指针指向。

1.  remove

public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
 }
复制代码

2.  removeNode

//HashMap实现
    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) {
                //判断是否为红黑树的节点,是则按红黑树来获取到node
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                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)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //从单链表中删除
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                //调用删除回调方法进行后续操作,LinkedHashMap覆写了该方法,调整了双向链表的节点指向,达到删除的目的
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }
复制代码

3.   afterNodeRemoval

// LinkedHashMap覆写HashMap的方法,用于在双向链表中移除节点
    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为头节点,要把p节点的后继节点作为新的头节点
        if (b == null)
            head = a;
        else
            b.after = a;
        // a为null,表明p为尾节点,要把p节点的前驱节点作为新的尾节点
        if (a == null)
            tail = b;
        else
            a.before = b;
    }
复制代码

双向链表删除过程,其实就是改变节点的指针指向即可,要注意判断当前节点是否为头节点或者尾节点这两种特殊情况,这也是代码要具备鲁棒性的体现。指针调整过程如下图所示。

深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

4. 访问顺序的维护过程

accessOrder 默认为false,按插入顺序来维护双向链表。如果我们把它设为true ,那么就是按访问节点的先后顺序来维护链表的。访问某个节点,就把该节点作为双向链表的最新的尾节点。

//覆写HashMap的方法
    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //如果accessOrder为true,则调用afterNodeAccess 将被访问节点移动到链表的尾部
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
复制代码

调整指针指向,设置尾节点。

//LinkedHashMap中重写
    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 接在链表的最后
                p.before = last;
                last.after = p;
            }
            //把该节点作为最新的尾节点
            tail = p;
            ++modCount;
        }
    }
复制代码

5.  基于LinkedHashMap实现LRU缓存

//插入完成后对节点做移除操作,默认不会执行
  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);
      }
  }
复制代码

这里面removeEldestEntry方法默认返回的是false,所以不会执行删除的逻辑。如果我们重写该方法,节点满足某些条件,就返回true,那么就可以删除节点了。例如节点的过期时间到了,就删除。或者节点数量超过某个值,就删除缓存。

//移除最近最少被访问条件之一,通过覆盖此方法可以实现不同策略的缓存
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
复制代码

6.  总结

LinkedHashMap 在HashMap的基础结构上,通过维护一条双向链表,实现了散列数据结构的有序排列。 LinkedHashMap是线程安全的。当我们希望有顺序地去存取数据时,就可以使用LinkedHashMap了。它解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。

最后

感谢你看到这里,看完有什么的不懂的可以在评论区问我,觉得文章对你有帮助的话记得给我点个赞,每天都会分享java相关技术文章或行业资讯,欢迎大家关注和转发文章!

原文 

https://juejin.im/post/5f1430705188252e431d9ca8

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 深度分析:那些阿里,腾讯面试官都喜欢问的LinkedHashMap源码

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址