最近最少使用LRU（Least Recently Used）算法java实现

最近最少使用LRU（Least Recently Used）算法java实现

• 最近最少使用LRU（Least Recently Used）算法java实现
  • 一.使用linkedHashMap算法实现
  • 二.手撸 LRU 算法实现（Hash表 + 双向链表）
  • 三.总结

最近最少使用LRU（Least Recently Used）算法java实现

LRU 是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。

以上是来自百度百科的介绍，通俗来说，LRU就是一个淘汰算法，例如内存相较于硬盘可以快速的读写，但是内存的空间是有限的，为了有效的利用内存空间，就需要将一些非热点数据给淘汰掉，这里就用到 LRU 算法，它会将内存中最近一段时间没有使用的数据给淘汰掉。

另外 LRU 算法在找工作面试中，经常会被问到，需要能够在短时间内写出来，大家平时还是要勤加练习，下面给出两种算法实现。

动动发财小手，关注 + 点赞 + 收藏不迷路。

一.使用linkedHashMap算法实现

linkedHashMap 底层采用 HashMap + 双向链表，已经实现了 LRU 算法，我们可以直接来使用 linkedHashMap 来实现LRU算法。

以下是 linkedHashMap 构造函数的代码

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

linkedHashMap 构造函数前两个参数在这里就不介绍了，这儿简单介绍一下第三个参数：boolean accessOrder，true 代表按照存取顺序来排序， false 代表按照插入顺序来排序。

以下是使用 linkedHashMap 来实现的 LRU 算法。

package algorithm.lru;

import java.util.Iterator;
import java.util.linkedHashMap;
import java.util.Map;


public class LRUCache extends linkedHashMap {

    private int cacheSize;

    public LRUCache(int cacheSize) {
        super(cacheSize, 0.75f, true);
        this.cacheSize = cacheSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > cacheSize;
    }

    public static void main(String[] args) {
        LRUCache lru = new LRUCache(3);
        lru.put("1", 1);
        lru.put("2", 2);
        lru.put("3", 3);
        lru.put("4", 4);

        lru.printLRU(lru);

        System.out.println();
        lru.get("3");

        lru.printLRU(lru);

    }

    public void printLRU(LRUCache lru) {
        Iterator> iterator = lru.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry entry = iterator.next();
            System.out.println("key = " + entry.getKey() + ", value = " + entry.getValue());
        }
    }

}

输出如下：

key = 2, value = 2
key = 3, value = 3
key = 4, value = 4

key = 2, value = 2
key = 4, value = 4
key = 3, value = 3

可以看到，执行了 lru.put(“4”, 4) 之后，key = 1 就被remove了；当执行 lru.get(“3”) 之后，key = 3被挪到了双向链表的最前面。

二.手撸 LRU 算法实现（Hash表 + 双向链表）

上面的 LRU 算法实现，有点取巧，通常在面试的时候，面试官希望看到具体的算法实现逻辑，而不是使用 linkedHashMap 已有的功能。当然了，在工作当中，还是不要自己来实现了。

package algorithm.lru;

import java.util.concurrent.ConcurrentHashMap;


public class LruCache {

    private static ConcurrentHashMap cacheMap;

    private static volatile int count;

    private static int capacity;

    private Node head = new Node();

    private Node tail = new Node();

    LruCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;
        cacheMap = new ConcurrentHashMap<>();
        this.tail.pre = head;
        this.head.next = tail;
    }

    private static class Node {

        Node() {
        }

        Node(String key) {
            this.key = key;
            this.value = Integer.parseInt(key);
        }

        private String key;

        private int value;

        private Node pre;

        private Node next;

        public String getKey() {
            return this.key;
        }

    }

    public void put(Node node) {
        Node existNode = get(node);

        if (existNode != null) {
            // cacheMap中node存在,先remove节点,再把节点移到链表头部
            removeNode(existNode);
            // 在链表头部插入node
            headAdd(existNode);
        } else {
            // cacheMap中node不存在,则插入node
            if (count == capacity) {
                // 缓存已满,在链表尾部remove
                tailRemove();
                count--;
            }
            headAdd(node);
            count++;
            cacheMap.put(node.getKey(), node);
        }
    }

    public void headAdd(Node node) {
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    public void removeNode(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    public void tailRemove() {
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
    }

    public Node get(Node node) {
        return cacheMap.get(node.getKey());
    }

    public void print() {
        Node node = head;
        System.out.println("========================================");
        while (node.next != null && node.next != tail) {
            System.out.println(node.next.key + " count = " + count);
            node = node.next;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node("1");
        Node node2 = new Node("2");
        Node node3 = new Node("3");
        Node node4 = new Node("4");
        LruCache lruCache1 = new LruCache(3);
        lruCache1.put(node1);
        lruCache1.print();
        lruCache1.put(node2);
        lruCache1.print();
        lruCache1.put(node3);
        lruCache1.print();
        lruCache1.put(node4);
        lruCache1.print();

        System.out.println("");
        System.out.println("###################################################");
        System.out.println("");

        Node node5 = new Node("5");
        Node node6 = new Node("6");
        Node node7 = new Node("7");
        LruCache lruCache3 = new LruCache(3);
        lruCache3.put(node5);
        lruCache3.print();
        lruCache3.put(node6);
        lruCache3.print();
        lruCache3.put(node7);
        lruCache3.print();
        lruCache3.put(node5);
        lruCache3.print();

        System.out.println("");
        System.out.println("###################################################");
        System.out.println("");

        Node node8 = new Node("8");
        LruCache lruCache2 = new LruCache(3);
        lruCache2.put(node8);
        lruCache2.print();
        lruCache2.put(node8);
        lruCache2.print();

    }

}

输出如下：

========================================
1 count = 1
========================================
2 count = 2
1 count = 2
========================================
3 count = 3
2 count = 3
1 count = 3
========================================
4 count = 3
3 count = 3
2 count = 3

###################################################

========================================
5 count = 1
========================================
6 count = 2
5 count = 2
========================================
7 count = 3
6 count = 3
5 count = 3
========================================
5 count = 3
7 count = 3
6 count = 3

###################################################

========================================
8 count = 1
========================================
8 count = 1

三.总结

最好还是能够手写第二种 LRU 的算法实现，就算不能全写出来，也可以写一个大概的思路，面试官主要考察的也就是这个，毕竟在短短的10几分钟内，手撸一个 LRU 还是有点难度的，难免会有一些小bug。

引用:
1.https://baike.baidu.com/item/LRU/1269842?fr=aladdin