美文网首页Java 杂谈
面试官:如何用LinkedHashMap实现LRU

面试官:如何用LinkedHashMap实现LRU

作者: zy_think123 | 来源:发表于2019-08-16 17:26 被阅读2次

    上一篇文章分析了HashMap的原理,有网友留言想看LinkedHashMap分析,今天它来了。

    LinkedHashMap是HashMap的子类,在原有HashMap数据结构的基础上,它还维护着一个双向链表链接所有entry,这个链表定义了迭代顺序,通常是数据插入的顺序。

    LinkedHashMap结构

    上图我只画了链表,其实红黑树节点也是一样的,只是节点类型不一样而已

    也就是说我们遍历LinkedHashMap的时候,是从head指针指向的节点开始遍历,一直到tail指向的节点。

    源码

    public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
    {
      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);
        }
    
        // 双向链表头节点
        transient LinkedHashMap.Entry<K,V> head;
    
        // 双向链表尾节点
        transient LinkedHashMap.Entry<K,V> tail;
    
        // 指定遍历LinkedHashMap的顺序,true表示按照访问顺序,false表示按照插入顺序,默认为false
        final boolean accessOrder;
      }
    
    }
    

    从LinkedHashMap的定义里面可以看到它单独维护了一个双向链表,用于记录元素插入的顺序。这也是为什么我们打印LinkedHashMap的时候可以按照插入顺序打印的支撑。而accessOrder属性则指明了进行遍历时是按照什么顺序进行访问,我们可以通过它的构造方法自己指定顺序。

    public LinkedHashMap(int initialCapacity,float loadFactor,
                       boolean accessOrder) {
      super(initialCapacity, loadFactor);
      this.accessOrder = accessOrder;
    }
    

    当accessOrder=true,访问顺序的输出是什么意思呢?来看下下面的一段代码

    LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>(8, 0.75f, true);
    
    map.put(1, 1);
    map.put(2, 2);
    map.put(3, 3);
    
    map.get(2);
    
    System.out.println(map);
    
    

    输出结果是

    {1=1, 3=3, 2=2}
    

    可以看到get了的数据被放到了双向链表尾部,也就是按照了访问时间进行排序,这就是访问顺序的含义。

    在插入的时候LinkedHashMap复写了HashMap的newNode以及newTreeNode方法,并且在方法内部更新了双向链表的指向关系。

    同时插入的时候调用了afterNodeAccess()方法以及afterNodeInsertion()方法,在HashMap中这两个方法是空实现,而在LinkedHashMap中则有具体实现,这两个方法也是专门给LinkedHashMap进行回调处理的。

    afterNodeAccess()方法中如果accessOrder=true时会移动节点到双向链表尾部。当我们在调用map.get()方法的时候如果accessOrder=true也会调用这个方法,这就是为什么访问顺序输出时访问到的元素移动到链表尾部的原因。

    接下来来看看afterNodeInsertion()的实现

    // evict如果为false,则表处于创建模式,当我们new HashMap(Map map)的时候就处于创建模式
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
      LinkedHashMap.Entry<K,V> first;
    
      // removeEldestEntry 总是返回false,所以下面的代码不会执行。
      if (evict && (first = head) != null && removeEldestEntry(first)) {
          K key = first.key;
          removeNode(hash(key), key, null, false, true);
      }
    }
    

    看到这里我有一个想法,可以通过LinkedHashMap来实现LRU(Least Recently Used,即近期最少使用),只要满足条件,就删除head节点。

    public class LRUCache<K,V> extends LinkedHashMap<K,V> {
        
      private int cacheSize;
      
      public LRUCache(int cacheSize) {
          super(16,0.75f,true);
          this.cacheSize = cacheSize;
      }
    
      /**
       * 判断元素个数是否超过缓存容量
       */
      @Override
      protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
          return size() > cacheSize;
      }
    }
    
    

    就这样一个简单的LRU Cache就实现了,以后面试官如果喊你给它实现一个LRU,你就这样写给他,如果他让你换一种方式,你就用链表使用同样的思维给他实现一个,然后你就可以收割offer了。

    对于删除,LinkedHashMap也同样是在HashMap的删除逻辑完成后,调用了afterNodeRemoval这个回调方法来更正链表指向关系。

    其实你只要看了上一篇文章再也不怕面试官问我JDK8 HashMap,再记得LinkedHashMap只是多维护了一个双向链表之后,再看LinkedHashMap中关于链表操作的代码就非常简单了。

    相关文章

      网友评论

        本文标题:面试官:如何用LinkedHashMap实现LRU

        本文链接:https://www.haomeiwen.com/subject/xkvqsctx.html