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

image.png

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,如下图 image.png 在每次添加完数据之后都会调用该方法,巧妙的是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;
        }
    }
}

image.png 本篇文章为原创文章,如果需要转载,请加上源链接和评论