面试题一天一题——第一天 · （LRUCache原理）

面试是一场与面试官交心的过程，会遇到一些成熟稳重的大牛、同样也会遇到一些设计挖苦你自以为是的人，这些都不重要，我们能够做到的只有好好掌握知识，一点点的积累。

LRU( Least Recently Used ) 算法，经常会在面试中问到，虽然名字听起来高大上，但是算法其实很简单，最近最少使用的就将其排除在列表之外，以便将最近最常使用的节点放在列表最前面，在取数据的时候方便快捷的拿到数据，提高性能，其实说到这里，聪明的你应该都知道了其中的原理，下面我们通过其中的源码进行分析。

面试题：LRU算法实现原理以及在项目中的应用

上面说到，最近最少使用将排除在列表之外，那这个列表是什么？？ 通过源码得知，jdk中实现的LRU算法内部持有了一个LinkedHashMap:

/**
 *一个基于LinkedHashMap的LRU缓存淘汰算法，
 * 这个缓存淘汰列表包含了一个最大的节点值，如果在列表满了之后再有额外的值添加进来，
 * 则LRU（最近最少使用）的节点将被移除列表外
 * 
 * 当前类是线程安全的，所有的方法都被同步了
 */
public class LRUCache<K, V> {

    private static final float hashTableLoadFactor = 0.75f;
    private LinkedHashMap<K, V> map;
    private int cacheSize;
    
    //...
}

而LinkedHashMap内部节点的特性就是一个双向链表，有头结点和尾节点，有下一个指针节点和上一个指针节点；LRUCache中，主要是put() 与 get () 两个方法，LinkedHashMap是继承至HashMap，查看源码得知LinkedHashMap并没有重写父类的put方法，而是实现了其中另外一个方法，afterNodeInsertion() 接下来分析一下LinkedHashMap中的put() 方法：

    // 由LinkedHashMap 实现回调
    void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

// HashMap.put()
 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();
        // 回调给LinkedHashMap ，evict为boolean
        afterNodeInsertion(evict);
        return null;
    }

可以看到新增节点的方法，是由父类实现，并传递回调函数afterNodeInsertion(evict) 给LinkedHashMap实现：

 void afterNodeInsertion(boolean evict) { // 可能移除最老的节点
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

可以看到 if 中有一个removeEldestEntry(first) 方法，该方法是给用户去实现的，该怎样去移除这个节点，最常用的是判断当前列表的长度是否大于缓存节点的长度：

 this.map = new LinkedHashMap<K, V>(hashTableCapacity, LRUCache.hashTableLoadFactor, true) {
            // (an anonymous inner class)

            private static final long serialVersionUID = 1;

            @Override
            protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                // 返回为true的话可能移除节点
                return this.size() > LRUCache.this.cacheSize;
            }
        };

接下来就是get() 方法了：

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

// afterNodeAccess(e)
 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;
        }
    }

所以在这个方法中，就将我们上面说到的最近最常使用的节点移到最后，而最近最少使用的节点自然就排列到了前面，如果需要移除的话，就从前面删除掉了节点。

总结

说了这么多，又是LRUCache使用，又是LinkedHashMap使用，面试的时候，我跟面试官说这么多源码有啥用啊？ 其实看完源码，我们对原理应该了解得很清晰了，LRU算法就是淘汰算法，其中内置了一个LinkedHashMap来存储数据。

比如我们的图片加载框架Glide，其中大部分算法都是LRU算法；有内存缓存算法和磁盘缓存算法（DiskLRUCache）; 当缓存的内存达到一定限度时，就会从列表中移除图片（当然Glide有活动内存和内存两个，并不是直接删除掉）。

面试的时候，说到LinkedHashMap中的几个HashMap回调方法与其中操作，再联系一些常用的框架及具体实现，相信会事倍功半吧^~