手摸手写一个LRU算法

简单的程序员

发布于 2021-03-22 14:51:56

2410

发布于 2021-03-22 14:51:56

文章被收录于专栏：奕仁专栏奕仁专栏

最近看到面经里面有这么一道题，是让你用java手写一个LRU算法，这可给我急坏了，LRU到底是啥玩意……

LRU到底是啥玩意呢？

经过我周密的百度之后，得到了答案，原来就是 “Least Recently Used”的缩写，它的意思是最近最少使用。

LRU如何写

当我看到上面 “最近最少使用”的字眼的时候，我心理其实已经有答案了，LinkedHashMap不是提供了这个功能么？在想到LinkedHashMap的时候，就想起了它的数据结构，它其实是继承的HashMap，但是HashMap存储数据的使用用的是Node单链表，而前者是双向链表，提供了before和after链表。千言万语不如放代码……

HashMap数据结构

首先贴一下HashMap的存储结构，我们大家基本都知道，hashMap底层是数组+链表组成的，而链表则对应下面的结构，它有一个next字段，是链接的下一个节点，所以它是一个单链表

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

LinkedHashMap数据结构

从下面的代码可以看出，它是完全继承的hashMap的结构，并在它基础上加入了before和after节点，即头和尾节点

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

为啥说LinkedHashMap适合做LRU

为啥呢？了解了它的数据结构之后，再看一下它提供的方法，这里需要翻到HashMap的put方法的这一行 afterNodeInsertion，如下图

在每次添加完数据之后都会调用该方法，巧妙的是LinkedHashMap重写了HashMap的afterNodeInsertion方法，然后做了一些“骚操作”，我们把它粘下来

void afterNodeInsertion(boolean evict) { 
//从这个骚注释其实大概就能看得出这个操作了吧，意思是 可能删除最早的数据
// possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
//如果头节点不为空 并且 removeEldestEntry执行为true 就删除first节点的数据 
 if (evict && (first = head) != null && removeEldestEntry(first)) {
     K key = first.key;
     removeNode(hash(key), key, null, false, true);
    }
}

removeEldestEntry

//这tm永远都是false？ 对，因为这个需要让程序猿自己去重写的
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
   return false;
}

需要注意的一点是在集成LinkedHashMap的时候，构造方法要使用传入accessOrder的那个，为什么呢？就在下面这行代码↓ 它其实就是说，如果当前节点不等于尾结点的时候，将当前节点改为尾结点，于是新加的数据肯定是最活跃的，first肯定是最不活跃的

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

有了上面那一步就好办了，这不就好办了嘛，我们自己去手写实现一个Lru算法

import java.util.LinkedHashMap;
import java.util.Map;

public class LruTest {


    public static void main(String[] args) {
        LRU map = new LRU(3);
        map.put("first", "a");
        map.put("second", "b");
        map.put("first", "d");
        map.put("third", "c");
        map.put("fifth", "e");
        map.put("sixth", "f"); 
    } 

    static class LRU extends LinkedHashMap {
        private int cacheSize;

        public LRU(int cacheSize) {
            /**
             * 这里需要调用LinkedHashMap的顺序排序
             * 顺序排序的作用是 当节点覆盖原有的节点的时候 对应的first节点也会推移
             * ex： 1,1 -->  2,2 --> 1,1-->3,3-->4,4  最终会输出2,2而不是1,1 符合预期
             */
            super(cacheSize, 0.75f, true);
            this.cacheSize = cacheSize;
        }
	//重写该方法，当前size > 数据的缓存size 就删除最不活跃的数据，也就是first节点，于是完美解决Lru问题
        @Override
        protected boolean removeEldestEntry(Map.Entry eldest) {
            return size() > getCacheSize();
        }

        public int getCacheSize() {
            return cacheSize;
        }
    }
}